[파이썬] 자료구조 - 스택, 큐, 덱(Stack, Queue, Dequeue)

스택, 큐, 덱이란

• 데이터 값을 저장하는 기본적인 구조
• 일차원의 선형(linear) 자료구조

스택(Stack)

• 가장 최근에 저장된 값 다음에 저장되고, 가장 최근에 저장된 값이 먼저 나간다.
  -> LIFO (Last In First Out) 원칙

• 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다.

큐(Queue)

• 스택과 동일하게 가장 최근에 저장된 값 다음에 새로운 값이 저장되지만, 가장 오래전에 저장된 값부터 나간다는 점에서 차이가 있다.
  -> FIFO (First In First Out) 원칙

• 스택과 마찬가지로 리스트가 큐의 모든 연산을 지원하지만, 리스트는 동적 배열로 구현되어 큐의 연산을 수행하기에 효율적이지 않다. 따라서 파이썬에서 큐를 구현할 때는 덱을 이용한다.

스택 vs 큐

큐를 list로 사용하지 않는 이유는,
pop()의 시간 복잡도는 O(1)이고, pop(0)의 시간 복잡도는 O(N)이기 때문이다. (첫번째 원소를 삭제한 후, 모든 원소를 앞으로 이동시키기 때문에)
list를 큐로 사용할 경우 시간이 오래 걸린다.

덱(Dequeue)

• Stack + Queue
• Double-ended Queue
• 오른쪽과 왼쪽 모두에서 삽입과 삭제가 가능한 큐이다.
• 파이썬 collections 모듈에 deque란 클래스로 덱이 구현되어 있다.
• 양 끝의 요소의 추가/삭제가 O(1)이다.

주요 함수

1. append() : deque의 right end에 요소 추가
2. appendleft() : deque의 left end에 요소 추가
3. pop() : deque의 right end의 요소 삭제
4. popleft() : deque의 left end의 요소 삭제