스택 & 큐
전체적인 설명전에 이해를 위해 아래 그림을 먼저 살펴보겠습니다.
스택(Stack)
- 나중에 넣은 데이터를 먼저 반환하도록 설계한 메모리 구조
- Last In First Out(LIFO) / 후입선출
1 | a = [1, 2, 3, 4, 5] |
2 | |
3 | a.append(6) # a에 6 추가 |
4 | a.append(7) # a에 7 추가 |
5 | print(a) # [1, 2, 3, 4, 5, 6, 7] |
6 | |
7 | a.pop() # 7 |
8 | a.pop() # 6 |
9 | print(a) # [1, 2, 3, 4, 5] |
큐(Queue)
- 먼저 넣은 데이터를 먼저 반환하도록 설계 된 메모리 구조
- First In First Out(FIFO) / 선입선출
- 스택과 반대되는 개념
1 | b = [8, 9, 10, 11, 12] |
2 | |
3 | b.append(13) # b에 13을 추가 |
4 | b.append(14) # b에 14를 추가 |
5 | print(b) # [8, 9, 10, 11, 12, 13, 14] |
6 | |
7 | b.pop(0) # 8 |
8 | b.pop(0) # 9 |
9 | print(b) # [10, 11, 12, 13, 14] |
위의 코드를 봤을때 가볍게 생각한다면 “앞에서 하나 뺀다.”라는 쉬운 개념이지만 실제로는 아래와 비슷한 일이 일어 납니다.
[8] - [9] - [10] - [11] - [12] - [13] - [14]
[Null] - [9] - [10] - [11] - [12] - [13] - [14]
[9] - [10] - [11] - [12] - [13] - [14] - [ ? ]
앞에서 하나를 비우고 뒤에 있는 모든 데이터들을 한칸씩 앞으로 당기는 작업을 하므로, 가장 앞에 있는 데이터를 꺼내는데 걸리는 시간 복잡도는 O(1)이 아닌 O(N)이 되는 현상이 벌어집니다.
실제로 퍼포먼스가 떨어지기 때문에 collections의 deque를 사용해봅니다.
1 | from collections import deque |
2 | c = deque() |
3 | c.append(1) |
4 | c.append(2) |
5 | print(c) #[1, 2] |
6 | |
7 | c.popleft() # 1 |
8 | c.popleft() # 2 |
9 | print(c) # [] |
이렇게 한다면 퍼포먼스 차이가 말도 안될 정도로 차이가 납니다.
스택 큐 코드 구현
Stack
- is_empty() -> boolean
- push -> insert: push(data)
- pop -> delete: pop return맨위 값을 리턴하고 동시에 삭제
- peek -> 데이터보기: 맨 위 값을 반환만 함
Queue
- is_empty() -> boolean
- enqueue -> insert
- deqeue -> delete
- peek -> 데이터보기: 맨 위 값을 반환만 함
참고자료: 초보몽키의 개발공부로그