[자료구조] 스택(Stack)과 큐(Queue)

스택(Stack)

스택(Stack)이란

스택은 이름 그대로 차곡차곡 쌓아 올린 형태의 자료 구조를 나타낸다.

스택의 특징

스택은 기본적으로 push 작업과 pop 작업이 있다. push는 새로운 데이터를 스택에 삽입하는 것이고, pop은 스택의 자료를 삭제하는 것이다.
push와 pop 작업은 스택의 맨 위에서만 수행되고, 이 스택의 맨 위를 top이라 부른다. 즉, 가장 늦게 들어온 자료가 가장 먼저 삭제되는 후입 선출(LIFO, Last-In-First-Out)의 구조를 가진다.
이 push와 pop 작업은 스택의 top에서만 이루어지기에 O(1)의 시간 복잡도를 가진다.

스택의 장단점

장점
1. 스택은 구현이 간단하다.
2. 삽입 / 삭제의 연산 속도가 빠르다.
3. 되돌리기(Undo)와 같은 작업에 최적화 되어 있다.
단점
1. 중간 데이터에 접근하기 어렵다.
2. 크기가 고정된 경우, 이미 다 차있는 스택에 삽입시에 StackOverflow가 발생한다.

큐(Queue)

큐(Queue)란

큐는 데이터를 차례대로 처리하기 위한, 일종의 대기줄(Queue) 형태의 자료구조이다.

큐의 특징

큐는 enqueue와 dequeue 작업이 있다. enqueue는 큐에 새로운 데이터를 삽입하는 작업이고, dequeue는 큐에 데이터를 삭제하는 과정이다.
큐가 스택과 다른 점은 스택과 달리 삽입/삭제의 수행 위치가 다르다는 것이다. 큐는 선입 선출(FIFO, First-In-First-Out)로 가장 먼저 들어온 데이터가 가장 먼저 삭제되는 구조이다.
여기서 데이터가 삽입되는 부분을 rear, 데이터가 삭제되는 부분이 front라고 한다.
enqueue와 dequeue는 단순히 rear에 데이터를 추가하고, front에서 데이터를 삭제하는 연산이기에 각 작업의 시간 복잡도는 O(1)이다.

원형 큐(Circular Queue)

원형 큐는 큐의 일종으로, rear가 끝까지 도달하면 다시 front로 돌아가는 순회하는 구조의 큐이다.
순회하지 않는 일반적인 선형 큐에서는 삭제 연산시에 rear가 계속 front쪽으로 오게 되면서 앞의 공간을 재사용할 수 없게 되기에 공간 낭비가 발생한다.
위와 같은 문제때문에 큐는 주로 원형 큐로 구현하여 사용한다.(혹은 배열이 아닌 연결 리스트로 구현한다.)

우선순위 큐(Priority Queue)

일반 큐와 달리, 데이터가 들어온 순서가 아니라 우선순위(priority) 에 따라 삭제된다.
각 원소는 (key, element) 형태로 구성되며, key 값이 높은(또는 낮은) 원소가 먼저 제거된다.
주로 힙(Heap) 구조를 이용하여 구현된다.

데큐(Deque, Double-Ended Queue)

양쪽 끝(front, rear)에서 모두 삽입과 삭제가 가능한 큐이다.
스택과 큐의 특성을 모두 가지고 있어 양방향 처리나 캐시 구현 등에 활용된다.

큐의 장단점

장점
1. 삽입 / 삭제의 연산 속도가 빠르다.
2. 차례대로 데이터를 처리하는데 최적화되어 있다.(CPU 스케줄링 등)
단점
1. 중간 데이터에 접근하기 어렵다.
2. 크기가 고정된 경우, 이미 다 차있는 큐에 삽입시에 Overflow가 발생한다.

PREVIOUS[자료구조] 스택(Stack)과 큐(Queue)