[자료구조] 스택, 큐, 덱

오늘은 스택, 큐, 덱에 대해 알아보자.
셋 다 모두 선형(Linear) 자료구조라는 것에 공통점이 있다.

---

1. 스택 : STACK

• 후입선출
• 가장 나중에 들어온 값(데이터)이 가장 먼저 나가는 LIFO 자료구조
• 스택의 값 추가, 삭제는 한 방향에서만 이루어진다.
  • Top : 스택에 가장 마지막에 들어온 값
  • Push : 스택에 데이터 삽입
  • Pop : 스택에 가장 마지막으로 들어온 값 삭제

Python 구현 예시

def push(stack, value):
	stack.append(value)
    
def pop(stack):
  	stack.pop()

top = stack[-1]

JavaScript 구현 예시

function push(stack, value) {
	stack.push(value);
}

function pop(stack) {
	stack.pop();
}

var top = stack[stack.length - 1];

• 스택은 삽입에 O(1), 탐색에 O(n)의 시간복잡도를 가진다.

---

2. 큐 : QUEUE

• 선입선출
• 가장 먼저 들어온 값(데이터)가 가장 먼저 나가는 FIFO 자료구조
• 큐는 한 방향으로 값이 추가되고, 나머지 한 방향으로 값이 삭제된다.
  • Front : 큐의 가장 먼저 들어온 값, [0]을 의미하며, 가장 먼저 삭제될 값이다.
  • Rear : 큐의 마지막, 추가될 새로운 데이터의 위치
  • Enqueue : 데이터 삽입
  • Dequeue : 데이터 삭제

Python 구현 예시

def enqueue(queue, value):
	queue.append(value)

def dequeue(queue):
	queue.pop(0)

front = queue[0]

JavaScript 구현 예시

function enQueue(queue, value) {
	queue.push(value);
}

function deQueue(queue) {
	queue.shift();
}

var front = queue[0];

• 큐 역시, 삽입과 삭제에 O(1), 탐색에 O(n)의 시간복잡도를 가진다.

---

3. 덱 : DEQUE

• 큐 2개를 겹쳐놓은 것과 같다. 따라서, Double ended Queue라고 부른다.
• 양쪽에서 데이터의 입, 출력이 모두 가능한 자료구조

Python 구현 예시

from collections import deque

queue = deque([]) # deque 선언
queue.append(value)		# [-1] 위치에 value 추가
queue.appendleft(value)	# [0] 위치에 value 추가
queue.popleft()			# [0] 위치의 값 제거
queue.pop()				# [-1] 위치의 값 제거
# 다음과 같이 양방향에서 입출력이 모두 가능하다.

JavaScript 구현 예시

let queue = new Array();
queue.push(value);		// [queue.length-1] 위치에 value 추가
queue.unshift(value);	// [0] 위치에 value 추가
queue.shift();			// [0] 위치의 값 제거
queue.pop();			// [queue.length-1] 위치의 값 제거

• 스택, 큐와 같이 데이터 삽입, 삭제에 O(1)의 시간복잡도를 가진다.
• 파이썬에서 queue.pop(0) 보다, queue.popleft()가 좀 더 빠르게 실행된다.