파이썬 스택, 큐 deque (with 백준 18258)

스택

파이썬에서 스택은 리스트 객체를 사용한다.

☞ 리스트 (배열)에 대한 내용은 이전 글 참고

파이썬 리스트 배열 list (with 백준 5597, 10250)

스택 vs 큐

상황에 맞게 스택, 큐 방식을 선택하여 사용한다.

• 스택은 선입후출/후입선출 (LIFO : Last in First Out) 방식으로 나중에 들어간 놈이 먼저 나오는 방식
• 큐는 선입선출(FIFO : First In First Out) 방식으로 먼저 들어간 놈이 먼저 나오는 방식

큐 사용법

파이썬에서 큐는 덱(deque) 을 사용하며, 백준 알고리즘 문제에서도 시간제한으로 인해 deque를 사용해야 하는 경우가 있다.

 

● deque 사용 방법

collections 클래스의 deque 객체 사용한다. ( from collections import deque )

 

● deque 주요 메서드

1. append(x) : 덱의 오른쪽에 원소 x를 추가한다.
2. appendleft(x) : 덱의 왼쪽에 원소 x를 추가한다.
3. clear() : 덱의 모든 요소를 제거하고 길이를 0으로 만든다.
4. copy() : 덱의 얕은 복사를 만든다. ( 얕은 복사, 깊은 복사란? 링크 )
5. extend(iterable) : iterable 인자에서 온 요소를 추가하여 덱의 오른쪽을 확장한다.
6. extendleft(iterable) : iterable 인자에서 온 요소를 추가하여 덱의 왼쪽을 확장. 일련의 왼쪽 추가는 iterable 인자에 있는 요소의 순서를 뒤집는 결과를 준다.
7. insert(i, x) : x를 덱의 i 위치에 삽입한다.
8. pop() : 덱의 오른쪽에서 요소 제거후 반환. 없으면 IndexError 발생
9. popleft() : 덱의 왼쪽에서 요소 제거 후 반환. 없으면 IndexError 발생
10. reverse() : 덱의 요소들을 제자리에서 순서를 뒤집는다.
11. rotate(n=1) : 덱을 n단계 오른쪽으로 회전한다. n이 음수이면 왼쪽으로 회전한다.

from collections import deque

"""
deque 에 maxlen 미지정, 지정 차이점
"""
x = [1,2,3,4,5]
#maxlen 미지정
x = deque(x)
print(x) # deque([1, 2, 3, 4, 5])
x.append(6)
print(x) # deque([1, 2, 3, 4, 5, 6])
x.appendleft(0) 
print(x) # deque([0, 1, 2, 3, 4, 5, 6])
x.append([7,8]) # ==> list 로 추가된다.
print(x) # deque([0, 1, 2, 3, 4, 5, 6, [7, 8]])
x.pop()
print(x)
x.extend([7,8]) # ==> 리스트의 값을 오른쪽에 추가
print(x) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])
x.extendleft([9,10]) # ==> 리스트의 값을 왼쪽에 추가, 요소 순서 뒤집어짐
print(x) # deque([10, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8])
x.popleft()
x.popleft()
x.pop()
x.pop()
print(x)

##maxlen 지정
y = [1,2,3,4,5]
y = deque(y,5)
print(y) # deque([1, 2, 3, 4, 5], maxlen=5)
y.append(6)
# 제한된 길이의 덱이 가득 차면, 새 항목이 추가될 때, 해당하는 수의 항목이 반대쪽 끝에서 삭제된다.
print(y) # deque([2, 3, 4, 5, 6], maxlen=5) -> 기존 1이 삭제됨
y.appendleft(0)
print(y) # deque([0, 2, 3, 4, 5], maxlen=5) -> 기존 6이 삭제됨

"""
deque 주요 메서드
"""
# x = deque([0, 1, 2, 3, 4, 5, 6])
x.pop() # 덱의 맨 오른쪽 원소 삭제
print(x) # deque([0, 1, 2, 3, 4, 5])
x.popleft() # 덱의 맨 왼쪽 원소 삭제
print(x) # deque([1, 2, 3, 4, 5])
x.reverse()
print(x) # deque([5, 4, 3, 2, 1])
x.rotate(1) # 맨 오른쪽에 있는 원소를 맨 왼쪽으로 이동
print(x) # deque([1, 5, 4, 3, 2])
x.rotate(-1) # 맨 왼쪽에 있는 원소를 맨 오른쪽으로 이동
print(x) # deque([5, 4, 3, 2, 1])

 

▶ deque 연습 백준 문제 풀이

https://www.acmicpc.net/problem/18258

import sys
from collections import deque
N = int(sys.stdin.readline().rstrip())
cmd = [sys.stdin.readline().rstrip().split(" ") for _ in range(N)]
queue = deque()

for i in range(0, N):
    #print(cmd[i][0])
    if (cmd[i][0] == 'push'):
        x = cmd[i][1]
        queue.append(x)
    elif cmd[i][0] == 'pop':
        if (len(queue) > 0):
            x = queue.popleft()
            print(x)
        else:
            print(-1)
    elif cmd[i][0] == 'size':
        x = len(queue)
        print(x)
    elif cmd[i][0] == 'empty':    
        if (len(queue) == 0):
            print(1)
        else:
            print(0)
    elif cmd[i][0] == 'front':
        if (len(queue) > 0):
            print(queue[0])
        else:
            print(-1)
    elif cmd[i][0] == 'back':
        if (len(queue) > 0):
            print(queue[-1])
        else:
            print(-1)

 

☞ 파이썬 자습서 참고 사이트

https://docs.python.org/ko/3/library/collections.html#deque-objects

collections — Container datatypes