[CS50] 자료구조 - 스택, 큐, 딕셔너리

우리가 여태껏 배운 배열, 연결 리스트, 해시 테이블, 트라이 외에도 많은 자료 구조들이 있다.

 

위의 자료 구조를 기반으로 문제를 해결하는 데 적합한 새로운 자료 구조를 만들 수도 있다.

 

아래와 같이 세 가지의 대표적인 자료 구조를 간단하게 알아보겠다.

 

 

큐 (Queue)

큐는 메모리 구조에서 값이 아래로 쌓이는 구조다.

 

값을 넣고 뺄 때 '선입 선출'(FIFO: First In First Out) 방식을 따른다. 가장 먼저 들어온 값이 가장 먼저 나가는 것이다.

 

은행에서 줄을 설 때 가장 먼저 줄을 선 사람이 가장 먼저 업무를 처리하게 되는 것과 동일하다.

 

큐는 배열이나 연결 리스트를 통해 구현할 수 있다.

 

 

스택 (Stack)

스택은 값이 위로 쌓이는 구조다. 값을 넣고 뺄 때 '후입 선출'(LIFO: Last In First Out) 방식을 따른다.

 

가장 나중에 들어온 값이 가장 먼저 나가는 것이다.

 

뷔페에서 접시를 쌓아 뒀을 때 사람들이 가장 위에 있는 접시를 가장 먼저 들고 가는 것과 동일하다.

 

스택도 배열이나 연결 리스트를 통해 구현할 수 있다.

 

 

딕셔너리 (Dictionary)

딕셔너리는 '키'와 '값'이라는 요소로 이루어져 있다. '키'에 해당하는 '값'을 저장하고 읽어오는 것이다.

 

마치 대학교에서 '학번'에 따라서 '학생'이 결정되는 것과 동일하다.

 

일반적인 의미에서 '해시 테이블'과 동일한 개념이라고도 볼 수 있다.

 

딕셔너리에서는 '키'를 어떻게 정의할 것인지가 중요하다.

 

 

References

모두를 위한 컴퓨터 과학 (CS50 2019)

모두를 위한 컴퓨터 과학 (CS50 2019)