[자료구조] Stack, Queue, Dequeue

Stack

LIFO (Last In First Out)로 마지막에 삽입된 자료부터 출력 혹은 삭제되는 형태의 자료구조
한쪽 끝에서만 삽입과 삭제가 일어남

Stack 활용

• 웹 브라우저 방문기록 (뒤로가기)
• 실행취소 (undo)
• 역순 문자열 만들기
• 후위 표기법 계산

Queue

FIFO (First In First Out)로 첫번째로 삽입된 자료부터 출력 혹은 삭제되는 형태의 자료구조
한쪽 끝에서는 원소들이 삭제되고 반대쪽 끝에서는 원소들의 삽입만 가능하게 만든 순서화된 리스트

Queue 활용

• 은행 업무
• 대기열 순서와 같은 우선 순위의 작업 예약 등
• 서비스 센터의 대기 시간
• 프로세스 관리
• BFS (너비 우선 탐색) 구현

Dequeue

양쪽에서 삽입과 삭제가 가능한 구조로 스택과 큐의 연산을 모두 지원

---

deque 라이브러리

stack의 경우 파이썬의 리스트를 이용하면 시간 복잡도 O(1)로 간단하게 구현할 수 있지만, 첫번째 값에 대해 동작하는 Queue와 Dequeue의 경우는 그렇지 못하다.

이럴 때 사용할 수 있는 파이썬 라이브러리가 있는데, 바로 deque이다.
deque는 양쪽에서 삽입과 삭제가 모두 가능하므로 stack, queue, dequeue로 모두 활용 가능하다.

deque로 선언한 리스트에서는 일반적인 리스트에서 사용할 수 있는 인덱싱, 슬라이싱 기능을 사용할 수는 없다. 하지만 리스트 양쪽에 데이터 삽입, 삭제에 대해서는 효율적이다.

deque 선언

from collections import deque

data = deque()

from collections import deque를 하게 되면 이제 deque 라이브러리 사용이 가능하다.

data1 = deque([2, 3, 4]) 
data2 = deque('hello')

와 같은 식으로 괄호안에 초기값을 넣어 줄 수도 있다.

deque 메소드

• deque.append(item) : 오른쪽(마지막)에 item 값 추가
• deque.appendleft(item) : 왼쪽(첫번째)에 item 값 추가
• deque.pop(): 가장 오른쪽(마지막) 요소를 가져오는 동시에 deque에서 삭제
• deque.popleft() : 가장 왼쪽(첫번째) 요소를 가져오는 동시에 deque에서 삭제

deque를 stack으로 활용할 때 - LIFO

삽입 : deque.append(item)
삭제 : deque.pop()

deque를 queue로 활용할 때 - FIFO

삽입 : deque.append(item)
삭제 : deque.popleft()

---

관련 백준 문제

stack 뼈대 문제

https://www.acmicpc.net/problem/10828

queue 뼈대 문제

https://www.acmicpc.net/problem/10845

dequeue 뼈대 문제

https://www.acmicpc.net/problem/10866