1. 스택
- 스택이란?
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 반대로 FILO(First In Last Out)라고 하기도 한다.
- 파이썬으로 구현
append() 메소드와 pop()메소드만 사용할 수 있으면 간단히 리스트로도 구현할 수 있다. 아래의 예시를 보자
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)
stack.pop()
stack.append(6)
stack.append(7)
stack.append(8)
stack.pop()
stack.pop()
print(stack)
print(stack[::-1])
- 결과값
>> [1, 2, 3, 4, 6] # 하단에서부터 출력
>> [6, 4, 3, 2, 1] # 상단에서부터 출력- 처음의 pop에서는 제일 나중에 들어온 값인 5가 나갔다.
- 다음의 pop에서는 맨 위에 위치한 8과 7이 차례로 반환되었다.
2. 큐
- 큐란?
줄을 서는 것을 의미하는 단어이다. 말 그대로 먼저 온 사람이 먼저 들어가는 것이다.
스택과는 다르게 FIFO(First In First Out) 구조이다.
- 파이썬으로 구현
리스트형식으로도 구현할 수 있지만 데크(Deque)나 큐(Queue) 모듈을 이용하는 것을 추천한다.
리스트로 구현하면 시간복잡도가 더 높아져 비효율적일 수 있기 때문이다.
pop()을 사용하면 스택과 같은 방식이니, popleft()를 통해 삭제해야한다.
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)
queue.popleft()
queue.append(6)
queue.append(7)
queue.append(8)
queue.popleft()
print(queue)
print(queue[0])
print(queue[1])
# print(queue[::-1]) 불가능
- 결과값
>> deque([3, 4, 5, 6, 7, 8])
>> 3
>> 4- 제일 먼저 들어온 1, 2가 삭제된 것을 확인할 수 있다.
- deque객체는 슬라이싱이 불가능하니 알아두자.