스택(Stack)과 큐(Queue)

1. 스택 (Stack)

스택은 Last In, First Out (LIFO) 구조를 가진 자료구조입니다. 즉, 마지막에 들어간 데이터가 가장 먼저 나오는 구조입니다. 적용 예시로는 웹 브라우저의 방문기록, undo와 같은 실행 취소가 있습니다.

 

스택에서는 주로 다음과 같은 연산을 수행합니다:

• push: 스택의 가장 위에 새로운 요소를 추가합니다.
• pop: 스택의 가장 위에 있는 요소를 제거하고 반환합니다.
• peek: 스택의 가장 위에 있는 요소를 반환하지만, 제거하지는 않습니다.
• isEmpty: 스택이 비어 있는지 확인합니다.
• size: 스택에 있는 요소의 개수를 반환합니다.

* Python 예시 코드

파이썬에서는 일반적인 List를 스택으로 사용합니다.

stack = []

# 요소 추가 (push)
stack.append(1)  # 스택: [1]
stack.append(2)  # 스택: [1, 2]

# 요소 제거 및 반환 (pop)
print(stack.pop())  # 출력: 2, 스택: [1]

# 가장 위에 있는 요소 확인 (peek)
print(stack[-1])  # 출력: 1

# 스택이 비어 있는지 확인
print(len(stack) == 0)  # 출력: False (peek은 요소를 제거하지 않는다)

 

 

---

2. 큐 (Queue)

큐는 First In, First Out (FIFO) 구조를 가진 자료구조입니다. 즉, 가장 먼저 들어간 데이터가 가장 먼저 나오는 구조입니다. 적용 예시로는 줄 서기,프린터의 출력 처리가 있습니다.

 

큐에서는 주로 다음과 같은 연산을 수행합니다:

• enqueue: 큐의 가장 뒤에 새로운 요소를 추가합니다.
• dequeue: 큐의 가장 앞에 있는 요소를 제거하고 반환합니다.
• front: 큐의 가장 앞에 있는 요소를 반환하지만, 제거하지는 않습니다.
• rear: 큐의 가장 뒤에 있는 요소를 반환하지만, 제거하지는 않습니다.
• isEmpty: 큐가 비어 있는지 확인합니다.

* Python 예시 코드

파이썬에서는 deque를 사용해 큐를 구현합니다.

from collections import deque

queue = deque()

# 요소 추가 (enqueue)
queue.append(1)  # 큐: deque([1])
queue.append(2)  # 큐: deque([1, 2])

# 요소 제거 및 반환 (dequeue)
print(queue.popleft())  # 출력: 1, 큐: deque([2])

# 가장 앞에 있는 요소 확인 (front)
print(queue[0])  # 출력: 2

# 큐가 비어 있는지 확인
print(len(queue) == 0)  # 출력: False

 

리스트의 경우 앞 요소를 제거할 때 O(n)의 시간 복잡도를 갖는 반면에 deque의 경우 요소 추가, 제거에 O(1)의 시간 복잡도를 가지기 때문에, 큐 구현에 더 적합합니다. 또한 양쪽에서 접근하여 사용이 가능합니다.