[CS50] 스택, 큐, 딕셔너리

오늘은 이전까지 공부했던 내용 중에 다뤘던 자료이기도 하지만 많이 쓰이는 데이터 구조 3가지를 더 자세히 알아볼 텐데요 메모리 구조인 큐, 스택부터 해시 테이블로 구현할 수 있는 딕셔너리에 대해 공부해보도록 하겠습니다.

 

 

큐(Queue)

큐는 메모리 구조에서 잠깐 언급했지만 값이 아래로 쌓이는 구조를 가지고 있습니다.

값을 뺄 때는 FIFO(First In First Out), 즉 선입선출방식으로 가장 먼저 들어온 값이 가장 먼저 나가게 됩니다.

Queue의 사전적 정의를 보면 (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것이라고 나와있습니다. 만약 은행에서 줄을 설 때 먼저 줄을 선 사람이 먼저 업무를 처리하는 것과 같다고 보시면 됩니다.

큐는 배열이나 연결리스트를 통해 구현이 가능합니다.

 

 

스택(Stack)

스택은 큐와 반대로 위로 쌓이는 구조를 가지고 있습니다.

값을 뺄때 LIFO(Last In First Out), 즉 후입 선출방식으로 가장 나중에 들어온 값이 가장 먼저 나가게 됩니다.

Stack은 쌓다(포개다), 쌓이다, 채우다 라는 사전적 정의를 가지고 있습니다. 만약 식당에서 접시를 쌓아뒀을 때 사람들이 가장 위에 있는 접시부터 사용하게 되는 것과 같다고 보시면 됩니다.

스택 역시 배열이나 연결 리스트를 통해 구현이 가능합니다.

 

 

딕셔너리(Dictionary)

딕셔너리는 키와 값이라는 요소로 이루어져 있습니다.

키와 값은 연결되어있어 키에 해당하는 값을 저장하고 읽어오게 되는데 이때 키를 어떻게 정의할지가 중요합니다. 대학교에서 학번에 따라 학생이 결정되는 것과 같다고 보시면 됩니다.

딕셔너리는 일반적인 의미에서 해시 테이블과 동일한 개념이라고 볼 수 있습니다.

기존의 배열이나 리스트와 다른점은 리스트나 배열에서는 숫자 인덱스로 값(value)을 정했지만

딕셔너리는 문자로도 값을 정할 수 있다는 점입니다.

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.