스택과 큐, 덱

오늘은 선형 자료구조에 해당하는 자료구조 중 대표적인 스택, 큐, 덱 3가지의 자료구조에 대해서 알아보겠습니다.

스택 (Stack)

스택은 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out) 구조입니다.
스택은 한쪽 방향에서만 데이터의 삽입과 삭제가 가능합니다.

스택 용어

• top(peek): 가장 최근에 저장된 데이터이자 먼저 삭제 될 데이터입니다. 그림상에서 요소 4가 해당됩니다.
• push: 데이터를 삽입하는것을 말하며 삽입 된 데이터는 삭제시 가장 먼저 삭제 될 데이터가 됩니다.
• pop: 데이터를 삭제할 때 사용하며 가장 최근에 저장된 데이터가 삭제됩니다.

사용되는 예

• 브라우저의 뒤로가기
• 실행 취소 (Ctrl + z)
• 재귀 함수
• 역순 문자열 (문자열 거꾸로 뒤집기)

스택의 자료구조는 삽입과 삭제시에 O(1), 탐색에는 O(n)의 시간복잡도를 가지게 됩니다.

큐(Queue)

큐는 위에서 설명한 스택과는 달리 한 쪽에서는 데이터 삽입, 다른 한 쪽에서는 데이터의 삭제만 가능한 선입선출(FIFO, First In First Out) 구조를 가지고 있습니다.

실생활에서는 재료의 선입선출(유통기한이 오래된 것을 가장 앞쪽에 배치), 식당의 줄서기 등이 대표적인 예입니다.

큐 용어

• Enqueue: 데이터 삽입
• Dequeue (JS의 shift): 데이터 삭제
• Front: Dequeue시 삭제되는 데이터 (가장 먼저 저장된 데이터)를 가르킵니다.
• Rear: 추가될 새로운 요소의 위치를 가르킵니다.

사용되는 예

• BFS 알고리즘
• 프로세스 관리 (JS의 콜백 큐)
• 프린터의 대기열

큐에는 우선순위 큐, 원형 큐라는 2개의 종류가 더 있기 때문에 지금 설명하는 큐는 선형 큐(Linear Queue)라고도 부릅니다.

큐는 스택과 마찬가지로 삽입과 삭제에는 O(1), 탐색에는 O(n)의 시간복잡도를 가집니다.

큐의 다른 종류

우선순위 큐 (Priority Queue)

우선순위 큐의 각 요소는 값과 우선순위, 총 2개의 데이터를 가지고 있습니다.

따라서 선형큐와는 달리 우선순위가 높은 요소일수록 먼저 삭제되는 특징을 가지고 있으며 우선순위가 같은 데이터일 경우 삽입순서를 따릅니다.

삽입 및 삭제 시 우선순위에 따라 요소들을 정렬 해야하기 때문에 주로 힙(Heap)이라는 자료구조로 구현되며
실생활에서 병원의 응급실에서는 응급 환자가 우선 순위가 높으므로 먼저 진료를 받고 일반 환자는 순서가 뒤로 밀리는것과 같은 맥락입니다.

우선순위 큐는 어떻게 구현하느냐에 따라 시간복잡도가 달라지지만 힙을 기준으로 한다면 삽입과 삭제에는 O(logn), 우선순위가 가장 높은 요소를 탐색할 때는 O(1)만큼의 시간복잡도를 가집니다.

원형 큐 (= 환형 큐, Circular Queue, Ring Buffer)

출처: https://www.geeksforgeeks.org/

원형 큐는 선형 큐의 단점을 보완하기 위해 나왔습니다.

큐는 사이즈가 고정되어있고 데이터의 삽입과 삭제시 나머지 요소들은 이동하지 않습니다.
따라서 데이터의 삽입과 삭제가 반복되면 언젠가 Rear는 큐의 마지막 인덱스를 가르키게 되고 이전에 삭제 작업을 진행하여 앞에 빈 공간이 있더라도 활용하지 못하게 됩니다.

따라서 선형 큐는 빈 공간을 활용하기 위해 현재 요소들을 앞으로 재배치하는 별도의 작업이 필요합니다.

하지만 원형큐의 경우 Front와 Rear가 아래 그림처럼 순환하기 때문에 빈 공간을 사용하기 위한 별도의 작업이 필요하지 않습니다.

출처: https://www.geeksforgeeks.org/

위의 사진에서 Front와 Rear의 움직임을 보면 Front와 Rear가 계속해서 돌고 있는 모습을 볼 수 있습니다.

이러한 움직임을 만들어내기 위해서 원형 큐에서는 Enqueue 및 Dequeue시에 아래와 같은 작업을 합니다.

function enqueue() {
  // ...
  rear = (rear + 1) % queue_size;
}

function dequeue() {
  // ...
  front = (front + 1) % queue_size;
}

예를 들어, 큐의 전체 사이즈가 5이고 현재 Rear가 마지막 인덱스인 4를 가르키고 있다고 가정해보겠습니다.

여기서 Enqueue를 하게되면 Rear의 인덱스는 5가 될텐데 여기에 큐의 전체사이즈를 나눈 나머지를 구합니다.
5 % 5 = 0이므로 이 값을 Rear에 할당하여 인덱스가 다시 0을 가르킬 수 있도록 합니다.

이렇게 하면 정렬과정 없이 Front와 Rear가 순환하는 형태를 만들 수 있습니다.

덱 (Deque, Double-ended Queue)

덱은 큐 2개를 겹쳐놓은것과 같기 때문에 Double ended Queue라고 부르며 Deque이라는 명칭은 이를 축약형으로 부르는 것입니다.

이 자료구조는 이름처럼 양쪽에서 데이터의 입, 출력이 모두 가능한 자료구조입니다.

JS에서는 배열의 내장메소드로 모두 구현되어있으며
스택, 큐와 마찬가지로 front와 rear라는 포인터가 있으며 이들은 각각 가장 앞, 뒤에 있는 데이터를 가르킵니다.

다만, 스택과 큐의 Rear는 다음 요소가 삽입 될 위치를 가르키는 반면
덱의 Rear는 마지막 요소를 가르키고 있게 됩니다.

스택, 큐와 같이 데이터의 삽입과 삭제에 O(1)의 시간복잡도를 가집니다.