[자료구조] 스택(Stack) & 큐(Queue), 그리고 데크(Deque)

Stack - Last in, First out : LIFO
Queue - First in, First out : FIFO

---

스택과 큐는 일렬로 늘어선 자료를 표현한다. 자료구조는 데이터 표현에 따라 선형 자료구조와 비선형 자료구조로 나뉜다. 스택과 큐도 배열이나 리스트처럼 선형 자료구조의 일종이다. 이 두 가지를 나누는 기준은 자료를 어떤 순서로 삽입하고 삭제하냐로 볼 수 있다.

1. Stack

스택
: 후입선출 방식을 사용한다. 가장 늦게 들어온 데이터가 가장 먼저 빠져나간다. 웹 브라우저의 뒤로가기를 예시로 들수있다. 우리가 지나온 순서에 따라 스택에 삽입되고, 뒤로가기 버튼을 통해 직전에 왔던 길을 따라 되돌아간다. 이와 같이 가장 먼저 들어온 것이 제일 마지막에 빠져나가는 방식이 스택이다.

기본 연산

• push - 스택에 데이터 저장, In
• pop - 스택에서 데이터 삭제→ 제일 마지막에 저장된 데이터 삭제, Out
• peek - 가장 마지막으로 저장된 데이터 반환

스택을 설명할 때 대부분 위가 뚫린 통 형태를 사용

2. Queue

큐
: 선입선출 방식을 사용한다. 스택과 달리 먼저 들어온 데이터가 먼저 빠져나간다. 큐에서는 push와 pop처럼 삽입과 삭제에 대한 기본 정의는 따로 없지만 스택과 용어를 통일하여 사용하기도 한다. 스택과 큐를 직접 정의할 때, 스택은 마지막의 위치만 기억하면 되지만 큐는 삽입을 위한 마지막과 삭제를 위한 앞 두가지를 모두 기억해야 한다.

큐는 가로로 긴 통 형태를 사용하여 표현

- 우선순위 큐

일반 큐는 들어오는 순서에 따라 나가는 순서가 결정된다. 우선순위 큐에서 push는 단순히 데이터가 삽입되는 것이고, 데이터가 빠져나가는 것은 삽입 순서와 관계가 없다. 우선순위가 높은 데이터가 먼저 pop되어 일반적으로 생각하는 선입선출의 큐와 다른 모습을 하고 있다. 이 우선순위는 보통 힙(heap)을 통해 구현된다.

3. Deque

데크
: 한 방향으로 데이터를 삽입·삭제 하지 않고, 양 방향에서 데이터에 접근할 수 있다. 데크를 이용하면 스택과 큐를 모두 사용할 수 있다.