[자료 구조] 스택(stack), 큐(queue), 덱(deque)

0. 스택, 큐, 덱이란?

• 스택, 큐, 덱 모두 데이터를 저장하는 선형 자료 구조 (linear data structure)이다.
• 데이터를 변경(추가, 제거)하는 연산이 제공되지만 제한적인 규칙을 따른다.

1. 스택(stack)

• 가장 먼저 들어간 값이 가장 나중에 나오는 FILO(First-In-Last-Out)의 규칙을 가진 자료구조이다.
  • 상단의 원소를 추가/제거하는 연산 - \(O(1)\)
  • 상단의 원소를 확인하는 연산 - \(O(1)\)
  • 원칙적으로는 상단의 원소가 아닌 다른 원소들의 확인/변경이 불가능

2. 큐(queue)

• 가장 먼저 들어간 값이 가장 먼저 나오는 FIFO(First-In-First-Out)의 규칙을 가진 자료구조이다.
  • 제일 앞/뒤의 원소를 추가/제거하는 연산 - \(O(1)\)
  • 제일 앞/뒤의 원소를 확인하는 연산 - \(O(1)\)
  • 원칙적으로는 제일 앞/뒤의 원소가 아닌 다른 원소들의 확인/변경이 불가능

3. 덱(deque)

• 양쪽 끝에서 모두 입력하고 출력이 가능한 자료구조이다.
• Double Ended Queue를 줄여서 deque라고 한다.
  • 제일 앞/뒤의 원소를 추가/제거하는 연산 - \(O(1)\)
  • 제일 앞/뒤의 원소를 확인하는 연산 - \(O(1)\)
  • 원칙적으로는 제일 앞/뒤의 원소가 아닌 다른 원소들의 확인/변경이 불가능