[Python] 스택 / 큐

스택(Stack) 구현

리스트 자료형 이용

• append() : 가장 오른쪽에 원소를 삽입
• pop() : 가장 오른쪽의 원소를 꺼냄
• append(), pop() 의 시간 복잡도 : 상수시간 O(1) 으로, 스택 자료구조를 사용하기에 적합

# 리스트 자료형 선언
stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력

실행결과

[1, 3, 2, 5]
[5, 2, 3, 1]

 

큐(Queue) 구현

deque(덱) 라이브러리 이용 (스택, 큐 라이브러리의 장점을 합친 자료구조)

• append() : 가장 오른쪽에 원소를 삽입
• popleft() : 가장 왼쪽의 원소를 꺼냄
• append(), popleft() 의 시간 복잡도 : 상수시간 O(1)

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)    # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue)    # 나중에 들어온 원소부터 출력

실행결과

deque([3, 7, 1, 4])
deque([4, 1, 7, 3])