[자료구조] 스택(Stack)과 큐(Queue)
1. 스택(Stack)
- LiFo(Last in First out) : 마지막에 들어온 사람이 먼저 나간다.
- Keywords
- 삽입(Push)
- 추출(Pop)
- 현재 위치(Top)
- 마지막 데이터 확인(Peek)
- 비어있는 지 확인(Empty)
클래스로 이해하기
stack.py
class Stack:
def __init__(self,n):
self.n = n # stack의 저장공간
self.top = -1 # 처음 위치
self.stack = [None for _ in range(self.n)] # stack 만들기
# 원소 삽입
def push(self, data):
if self.top == self.n - 1:
return '더 이상 push할 공간이 없습니다.'
self.top += 1
self.stack[self.top] = data
return self.stack
# 원소 추출
def pop(self):
if self.top == -1:
return 'pop할 원소가 없습니다.'
self.stack.pop(self.top)
self.stack.append(None)
self.top -= 1
return self.stack
# 마지막 원소 확인
def peek(self):
if self.top == -1:
print('stack이 비었습니다.')
return None
return self.stack[self.top]
# 비어있는지 확인
def empty(self):
if self.top == -1:
return 1
return 0
# stack.py를 실행하면 진행
if __name__ == "__main__":
stack = Stack(5)
for i in range(7):
print(f'push {i} > {stack.push(i)}')
if i == 3:
print(f'peek > {stack.peek()}')
for i in range(7):
print(f'pop > {stack.pop()}')
if i == 2:
print(f'peek > {stack.peek()}')
print(f'empty > {stack.empty()}')
Output
## push 0 > [0, None, None, None, None]
## push 1 > [0, 1, None, None, None]
## push 2 > [0, 1, 2, None, None]
## push 3 > [0, 1, 2, 3, None]
## peek > 3
## push 4 > [0, 1, 2, 3, 4]
## push 5 > 더 이상 push할 공간이 없습니다.
## push 6 > 더 이상 push할 공간이 없습니다.
## pop > [0, 1, 2, 3, None]
## pop > [0, 1, 2, None, None]
## pop > [0, 1, None, None, None]
## peek > 1
## pop > [0, None, None, None, None]
## pop > [None, None, None, None, None]
## pop > pop할 원소가 없습니다.
## pop > pop할 원소가 없습니다.
## empty > 1
2. 큐(Queue)
- FiFo(First in First out) : 먼저 온 사람이 먼저 나간다.
- keywords
- 삽입(EnQueue)
- 추출(DeQueue)
- 머리(Front)
- 꼬리(Rear)
클래스로 이해하기
- 선형 큐의 경우, 앞 자리는 비는데 뒷 공간이 다 차서 공간 부족이 나타날 수 있다.
이를 해결하기 위해front
는 항상 0으로 두고, dequeue가 되면None
을 삽입한다.
class Queue:
def __init__(self,n):
self.n = n # queue의 저장공간
self.rear = -1 # 마지막 위치
self.queue = [None for _ in range(self.n)] # queue 만들기
# 원소 삽입
def enqueue(self, data):
if self.rear == self.n - 1:
return '더 이상 endeque할 공간이 없습니다.'
self.rear += 1
self.queue[self.rear] = data
return self.queue
# 원소 추출
def dequeue(self):
if self.rear == -1:
return 'dequeue할 원소가 없습니다.'
self.queue.pop(0)
self.queue.append(None)
self.rear -= 1
return self.queue
# 마지막 원소 확인
def rearvalue(self):
if self.rear == -1:
print('queue이 비었습니다.')
return None
return self.queue[self.rear]
# 비어있는지 확인
def empty(self):
if self.rear == -1:
return 1
return 0
if __name__ == "__main__":
queue = Queue(5)
for i in range(7):
print(f'enqueue {i} > {queue.enqueue(i)}')
if i == 3:
print(f'rear value > {queue.rearvalue()}')
for i in range(7):
print(f'dequeue > {queue.dequeue()}')
if i == 2:
print(f'rear value > {queue.rearvalue()}')
print(f'empty > {queue.empty()}')
Output
## enqueue 0 > [0, None, None, None, None]
## enqueue 1 > [0, 1, None, None, None]
## enqueue 2 > [0, 1, 2, None, None]
## enqueue 3 > [0, 1, 2, 3, None]
## rear value > 3
## enqueue 4 > [0, 1, 2, 3, 4]
## enqueue 5 > 더 이상 endeque할 공간이 없습니다.
## enqueue 6 > 더 이상 endeque할 공간이 없습니다.
## dequeue > [1, 2, 3, 4, None]
## dequeue > [2, 3, 4, None, None]
## dequeue > [3, 4, None, None, None]
## rear value > 4
## dequeue > [4, None, None, None, None]
## dequeue > [None, None, None, None, None]
## dequeue > dequeue할 원소가 없습니다.
## dequeue > dequeue할 원소가 없습니다.
## empty > 1
3. deque() 이용하기
위에서는 리스트를 이용하여 스택과 큐를 설명했다. 하지만, 실제 코딩테스트를 하다보면 시간복잡도에서 pass하지 못하는 경우가 많이 발생한다. 이 경우 from collections import deque
를 이용하여 빠르고 쉽게 코딩할 수 있다. deque()
를 사용해서 만들어진 형태를 덱(deque)이라고 한다. 가장 많이 쓰이는 함수만 소개한다.
code | description |
---|---|
append(data) | 오른쪽에 원소 data(하나)를 추가한다. |
appendleft(data) | 왼쪽에 원소 data(하나)를 추가한다. |
extend(data) | 오른쪽에 원소 data(여러 개|문자열, 리스트 등)를 추가한다. |
extendleft(data) | 왼쪽에 원소 data(여러 개|문자열, 리스트 등)를 추가한다. |
pop() | 가장 오른쪽 원소를 제거한다. 제거값을 반환함. |
popleft() | 가장 왼쪽 원소를 제거한다. 제거값을 반환함. |
index(data) | data의 위치를 반환한다. |
insert(i,data) | i 위치에 data를 삽입한다. |
clear() | 모든 data를 제거하고, 길이를 0으로 만든다. |
reverse() | data의 순서를 뒤집는다. |
rotate(n) | 뒤에서 n번째부터 순환한다. |
Examples
## deque > []
## append 0 > [0]
## appendleft 1 > [1, 0]
## extend abc > [1, 0, 'a', 'b', 'c']
## extendleft [5,6,7] > [7, 6, 5, 1, 0, 'a', 'b', 'c']
## pop > [7, 6, 5, 1, 0, 'a', 'b']
## popleft > [6, 5, 1, 0, 'a', 'b']
## reverse > ['b', 'a', 0, 1, 5, 6]
## rotate 1 > [6, 'b', 'a', 0, 1, 5]
## clear > []
4. 실전 문제 풀어보기(난이도 순)
시간 복잡도를 고려하여 deque()
를 이용해야만 풀 수 있는 문제들을 난이도별로 나열하였다. 각 문제의 옆을 드래그하면 Hint를 볼 수 있다.
스택(stack)
- Bronze II, 백준 17608. 막대기 Hint. new보다 큰 친구들만 남길 때까지 pop을 해야 한다.
- Silver IV, 백준 3986. 좋은 단어 Hint. 괄호 쌍 찾기 문제와 같다.
큐(queue)
- Silver V, 백준 2161. 카드1 Hint. rotate 함수를 이용하면 빠르다.
댓글남기기