CWN(CHANGE WITH NEWS) - 자료구조 어디까지 알고 있니? #3. 스택, 큐, 덱

스택(Stack)
모든 원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조로 삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 한쪽 끝을 bottom이라 한다. 스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, 가장 최근에 삽입된 원소를 의미하는 스택의 top으로부터 한 원소를 제거하는 것을 pop이라 한다.

스택은 제한된 용량을 가지도록 구현된다. 따라서 만약 스택이 가득 찬 상태에서 새로운 요소를 삽입 연산을 통해 스택에 추가하려고 하면 오버플로우 상태로 간주한다. 제거 연산이 스택의 맨 위에서부터 요소를 제거하면, 제거된 요소 아래에 있던 요소가 맨 위에 위치한다. 또, 스택이 비게 되면 언더플로우 상태가 된다.

큐(Queue)
마트의 계산대에서는 계산대에 먼저 도착한 고객이 먼저 계산하고 나가는 것처럼 한쪽으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조를 큐라고 한다.

이와 같은 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO : First-In First-Out)구조라고도 한다.

덱(Deque)
삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다. 스택과 큐의 장점만 따서 구성한 것으로서, 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과 입력은 양쪽에서 일어나고 출력은 한곳에서만 이루어지는 출력 제한이 있다.

[저작권자ⓒ CWN(CHANGE WITH NEWS). 무단전재-재배포 금지]