[CS] Stack 과 Queue 를 알아보자

Stack과 Queue란?

스택과 큐는 데이터를 집어 넣을 수 있는 선형 자료형인 동시에 추상적 자료 구조(ADT - Abstract Data Type)다.

ADT란 자료 구조의 방법이 어떤 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 것을 말한다.

즉 기능의 구현 부분이 없어서 설명하는 규칙만 이해한다면 스택과 큐라는 자료 구조를 만들 수 있다.

스택과 큐는 배열의 형태로 쉽게 표현할 수 있다. (이번 글에서는 직접 구현해보진 않지만 앞으로는 구현을 해보겠다. 진짜.)

---

1. Stack

📌 스택은 '팬케이크' 같은 모습이다.

팬케이크를 만들면 한 장 두 장 아래에서 위로 쌓아 올리고, 먹을 때는 가장 위부터 아래로 내려간다.

이런 것처럼 데이터도 아래에서 위로 쌓아 올리고, 데이터를 사용할 때는 가장 위에 있는 데이터를 먼저 사용한다.

 

그림처럼 배열이 수직으로 쌓여 있는 형태로, 데이터를 push해서 아래로 밀어 넣고, pop으로 위부터 꺼낸다.

이러한 자료 구조의 특성을 LIFO(Last In - First Out)이라고 한다.

 

스택이 꽉 차서 더 이상 자료를 넣을 수 없는 경우를 스택 오버플로우라고 하고,

스택이 비어 자료를 꺼낼 수 없을 떄는 스택 언더플로우라고 한다.

이 개념은 큐에도 동일하게 적용된다.

 

stack.pop() : 스택의 가장 위 데이터(오른쪽)를 삭제한다. 스택이 비어 있다면 연산은 정의 불가하다.

stack.push() : 스택의 가장 위 데이터(오른쪽)에 데이터를 삽입한다.

stack.top() : 스택의 가장 위 데이터(오른쪽)을 반환한다. pop과 마찬가지로 스택이 비어 있다면 정의 불가하다.

stack.empty() : 스택이 비어 있다면 1을 반환하고 그렇지 않다면 0을 반환한다.

 

📌 스택의 시간 복잡도

삽입 O(1)

삭제 O (1)

검색 O(n)

 

삽입과 삭제는 모두 가장 위에서 진행되기 때문에 데이터가 몇 개든 상관 없이 1이다.

반면 검색을 할 때는 스택 안의 데이터를 모두 뒤져야 하기 때문에 O(n)의 시간 복잡도를 가지게 된다.

 

📌 스택의 활용도

웹의 뒤로가기 버튼, 실행 취소, 되돌리기 등

---

2. Queue

📌 큐는 '줄' 같은 모습이다.

실제로도 Queue의 사전적 의미는 줄을 서서 기다리는 것을 의미한다고 한다. 

예를 들어 버스를 타기 위해 줄을 선 사람들이 있을 때, 먼저 기다린 사람이 먼저 버스를 타러 들어간다.

 

 

이처럼 먼저 들어간 데이터가 먼저 나오는 자료 구조의 특성을 FIFO (First In - First Out) 이라고 한다.

아래에서 위로 쌓아 올려 위부터 나가는 스택과는 반대되는 개념으로 큐에서는 양 쪽에서 작업이 이뤄진다. 

 

이 때 삭제를 하는 아래쪽을 front, 삽입을 하는 위쪽을 rear라고 하며

프론트에서 이뤄지는 삭제 연산을 Dequeue, 리어에서 이뤄지는 삽입 연산을 Enqueue라고 한다.

 

큐의 경우에는 push와 shift를 사용한다.

 

queue.shift() : 큐의 가장 아래 데이터(왼쪽)를 삭제한다. 큐가 비어 있다면 연산은 정의 불가하다.

queue.push() : 큐의 가장 위 데이터(오른쪽)에 데이터를 삽입한다.

 

📌 큐의 시간 복잡도

삽입 O(1)

삭제 O (1)

검색 O(n)

 

큐도 스택과 동일하다. 삽입을 할 때는 맨 위에서 이뤄지고 삭제를 할 때는 맨 아래에서 이뤄지기 때문에 항상 삽입/삭제는 1이다.

반면 검색의 경우에는 모든 데이터를 다 탐색해야 하므로 데이터의 크기만큼 시간 복잡도를 가지게 된다.

 

단, 큐에서 삭제를 할 때는 시간 복잡도가 O(n)이 될 수 있다.

가장 맨 앞의 것을 삭제한다면 (shift) 이후에 나머지 것들을 한 칸씩 앞으로 당겨야 한다.

이러한 문제점을 해결하기 위해 나온 것이 원형 큐(환형 큐)와 링크드 리스트다. 

이 부분은 추후 추가하도록 하겠다... 진짜로...

 

📌 큐의 활용도

푸쉬 알림 기능, 쇼핑몰에서 주문을 처리하는 방식, 순차적으로 해야 하는 작업을 저장하는 버퍼 등

---

 

참고 사이트

[CS] Stack과 Queue

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

큐, 스택, 트리 | JavaScript로 만나는 세상