자료구조 기본 - Stack, Queue, Deque

1. Stack

스택은 List의 append(), pop() 메서드로 구현된다. 배열이 아닌 리스트를 사용하기 때문에 배열의 크기를 지정하거나 변경하는 작업이 필요하지 않다. 아래의 문제를 보자.
>> 백준 10773번

가장 최근에 쓴 수를 지운다는 내용에서 Stack 자료구조를 연상할 수 있어야 한다. 이와 같은 문제는 append()와 pop()만으로 손쉬운 구현이 가능하다.

import sys
input = sys.stdin.readline

K = int(input())
arr = []
for i in range(K):
    num = int(input())
    if num == 0:
        arr.pop()
    else:
        arr.append(num)

print(sum(arr))

2. Queue

큐를 구현할 때에도 List의 append(), pop() 메서드가 사용된다. 다만, 스택과 달리 리스트의 앞에서 pop이 일어나야 하므로, pop() 대신 pop(0)를 사용한다.

아래의 문제를 보자.
>> 백준 1158번

단방향 큐는 회전하는 배열 관련 문제를 처리하기에 매우 적합한 자료구조이다. 그 이유는 front에서 pop한 값을 rear에 append하는 방식으로 회전하는 효과를 낼 수 있기 때문이다.

N, K = map(int, input().split())

lst = []
for i in range(N):
    lst.append(i+1)

result = []
for i in range(N):
    for j in range(K-1):
        lst.append((lst.pop(0)))
    
    result.append(lst.pop(0))

print('<' + ', '.join(map(str, result)) + '>')

3. Deque

pop(0)와 pop()은 언뜻 비슷해보이지만, 성능 면에서 큰 차이를 보인다. pop()은 O(1) 시간에 실행되지만, pop(0)는 원소를 삭제하는 데에 O(n)의 시간이 필요하다. 이러한 문제점을 해결하기 위해 사용할 수 있는 것이 바로 데크이다. Deque는 append(), appendleft(), pop(), popleft() 메서드를 제공하며, 모든 메서드가 O(1)의 시간 복잡도를 갖는다.

Deque는 스택과 큐의 상위호환이기 때문에 Deque를 이용하여 스택과 큐를 구현하는 것이 가능하며, 큐로 풀 수 있는 문제는 모두 데크로 더 효율적으로 풀 수 있다. 실행시간이 중요한 문제라면, 큐보다는 데크를 사용하는 편이 좋다.

Deque는 Stack이나 Queue와 달리, import 해야 하는 라이브러리가 있다.

from collections import deque 
deq = deque()

위에서 큐를 이용해 풀었던 문제를 데크로 더 효율적으로 풀이할 수 있다.

from collections import deque

N, K = map(int, input().split())

deq = deque([x for x in range(1, N + 1)])

result = []
for i in range(N):
    for j in range(K-1):
        deq.append((deq.popleft()))
    
    result.append(deq.popleft())

print('<' + ', '.join(map(str, result)) + '>')

아래의 문제도 풀어보자.
>> 백준 2164번

1을 버린다는 내용(popleft)과 2를 제일 아래로 옮기다는 내용(순환하는 배열)을 통해 데크를 이용해 문제를 풀어야 함을 알 수 있을 것이다.

from collections import deque

N = int(input())

deq = deque([x for x in range(1, N + 1)])

while len(deq) > 1:
    deq.popleft()
    deq.append(deq.popleft())

print(deq.pop())