스택과 큐

스택(Stack)

스택(Stack)은 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last In Firist Out) 구조이다.

스택은 한쪽 방향에서만 데이터의 삽입과 삭제가 가능하다.

 

스택 용어

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

사용되는 예

• 브라우저의 뒤로가기
• 실행 취소(Ctrl + z)
• 재귀 함수 : 자기 자신을 호출하는 함수
  
  • 함수를 호출할 때마다 해당 함수의 지역변수, 반환주소, 매개변수 등의 정보를 호출 스택이라는 메모리 영역에 저장
  • 재귀함수가 호출 될 때마다 이러한 정보들이 호출 스택에 계속 쌓이는데, 동작 방식이 후입 선출 원칙에 따름
  • 반환 과정에서 스택의 맨 위 정보부터 꺼내어 처리한다.
• 역순 문자열 (문자열 거꾸로 뒤집기)

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

 

 

큐(Queue)

 

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

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

 

큐 용어

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

사용되는 예

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

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

 

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

 

우선순위 큐(Priority Queue)

 

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

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

 

산입 및 삭제시 우선순위에 따라 요소들을 정렬해야하기 때문에 주로 힙(Heap)이라는 자료구조를 구현되며

실생활에서 병원 응급환자가 있다면 일반환자보다 우선 순위가 높으므로 먼저 진료를 받는 맥락이다.

 

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

 

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

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

 

큐는 사이즈가 고정되어있고, 데이터의 삽입과 삭제시 나머지 요소들은 이동하지 않는다.

따라서 데이터의 삽입과 삭제가 반복되면 언젠가 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가 순환하는 형태로 만들 수 있다.