🍔stack & queue & deque

🧜‍♀️stack / queue / deque 모두 특정 위치에서만 원소를 넣거나 뺄 수 있는 restricted structure

1. stack

🧜‍♀️ 스택이란, 한 쪽으로만 데이터를 빼고 넣을 수 있는 자료구조로, 한 쪽만 구멍이 뚫려 있는 프링글스 통을 생각하면 된다. 먼저 들어온 데이터가 나중에 나가는 형식 - 즉 나중에 들어온 데이터가 먼저 나가는 형식(선입후출 FILO)의 자료구조. 입구와 출구가 동일한 형태로 매우 간단한 두 연산(원소 추가 O(1), 원소 제거 O(1))이 제공된다. 제일 상단의 원소 확인은 O(1), 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다. 항상 스택 상단에만 초점이 되어 있음. 따라서 삽입할 때에도 가장 최근에 삽입한 원소 바로 위에 삽입이 되고, 삭제할 때도 가장 최근에 삽입한 원소가 삭제된다. 따라서 스택은 제일 상단에 원소 추가 & 제일 상단 원소 제거 & 제일 상단 원소 확인 - 이렇게 3가지 연산이 주가 된다. 따라서 스택 활용 문제는 제일 상단이 아닌 나머지 원소들의 확인/변경은 필요 x.

(좌) C를 상단에 넣고 상단에 뺌 / (우) 30을 상단에 넣고 12를 상단에 넣고 12를 뺌

 

🧜‍♀️ python으로의 구현은 list를 활용해서 가능. 제일 상단을 list의 오른쪽 끝이라 보고, 제일 상단에 원소 추가는 append(), 제일 상단 원소 제거는 pop(), 제일 상단 원소 확인은 arr[-1]을 활용해서 가능 - 모두 시간복잡도 O(1)로 매우 빠른 시간 내에 operation 수행 가능. 예를 들어 삽입 5 - 삽입 2 - 삽입 3 - 삽입 7 - 삭제 - 삽입 1 - 삽입 4 - 삭제 순으로 stack 연산을 구현한다면 아래와 같다.

stack = []

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 from the topmost [1, 3, 2, 5]
print(stack) #print from the bottommost [5, 2, 3, 1]

2. queue

🧜‍♀️ 큐(queue)는 스택과 다르게 먼저 들어온 데이터가 먼저 나가는 형식(선입선출 FIFO)의 자료구조이다. 이는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 아래와 같이 시각화할 수 있다. 예를 들어 먼저 들어온 사람이 먼저 처리되는 대기열을 구현할 때 큐라는 자료구조를 사용할 수 있다. 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조. 한 쪽 원소 추가 O(1), 그 반대쪽 원소 제거 O(1), 또한 제일 앞과 뒤 원소 각각 확인은 O(1)이며 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다. 스택과 다르게 나가고 들어오는 입구/출구가 다르지만, 공통점은 모두 출/입 관련 없는 원소들의 확인/변경은 불가능하다는 점. 

(좌) 3 4 5 순 먼저 한쪽에 들어가고 나올 때는 1 2 순 다른쪽에서 나간다 (우) 30이 한 쪽에 들어가고 먼저 들어가 있던 26이 다른쪽으로 나간다.

 

🧜‍♀️ python으로의 구현은 collections 모듈의 deque() 함수를 활용해서 가능. 오른쪽 뒤쪽에서 원소를 넣을 때는 append(), 왼쪽 앞쪽에서 원소를 뺄 때는 popleft()(그 반대로 앞쪽에서 원소를 넣고 싶다면 appendleft(), 오른쪽 뒤쪽에서 원소를 빼고 싶다면 pop() 사용 가능. 다만, queue는 들어오고 나가는 방향의 화살표가 동일하다는 점) append(), appendleft(), pop(), popleft() 모두 시간복잡도 O(1). 예를 들어 삽입 1 - 삽입 2 - 빼기 1 - 빼기 2 - 삽입 3 - 삽입 4 - 삽입 5 순서는 아래와 같이 코드로 구현할 수 있다.

from collections import deque

queue = deque()

queue.appendleft(1)
queue.appendleft(2)
queue.pop()
queue.pop()
queue.appendleft(3)
queue.appendleft(4)
queue.appendleft(5)
print(queue) #deque([5, 4, 3])

3. deque

🧜‍♀️ 덱(deque)이란, 큐와 다르게 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조. Double-Ended queue의 줄임말. 원소의 추가 / 제거 모두 O(1), 제일 앞/뒤의 원소 확인은 O(1), 제일 앞/뒤가 아닌 모든 원소는 원칙적으로 변경/접근 불가능. 이 때 queue와 다른 점은 양쪽 끝 모두에서 자유롭게 넣고 뺄 수 있다는 점. 

(우) 왼쪽에서 17 삽입 - 오른쪽에서 86 제거 - 오른쪽에서 30 삽입 - 왼쪽에서 17 제거

 

🧜‍♀️ python으로의 구현은 위 queue와 마찬가지로 collections의 deque() 활용. 위 queue()와 동일하게 append(), appendleft(), pop(), popleft() 사용 가능하다. 평소 list의 함수로 많이 쓰는 index(), insert(), remove(), count(), reverse() 사용 가능. 1개가 아닌 2개 이상의 원소를 동시에 넣는 extend(), extendleft()도 사용 가능하며 지정한 칸 만큼 움직이는 rotate() 함수도 있다. 예를 들어 deque([1, 2, 3, 4, 5])가 있다면 rotate(2)를 할 경우 왼쪽에서 오른쪽으로 2칸 움직이고 오른쪽에서 빠진 원소는 돌아서 왼쪽으로 들어간다. deque([5, 4, 1, 2, 3])이 된다. 반대 방향은 rotate(-2)이고 시간 복잡도는 O(k) (k개의 원소 움직인다면) 예를 들어 86과 23, 17을 차례대로 왼쪽에 넣고, 오른쪽에서 86을 뺀 뒤 오른쪽에서 30을 넣고 왼쪽에서 17을 빼는 과정은 아래와 같이 코드로 구현할 수 있다.

from collections import deque

deque = deque()

deque.appendleft(86)
deque.appendleft(23)
deque.appendleft(17)
deque.pop()
deque.append(30)
deque.popleft()
print(deque) #deque([23, 30])

 

🧜‍♀️ array와 deque을 비교하자면 array는 중간에 있는 모든 원소들도 O(1)에 랜덤 접근 가능. 하지만 deque은 양 끝의 원소 1개씩의 deletion, insertion이 O(1)인 자료구조(하지만 array는 삽입과 빼내기 연산 모두 O(n)). 하지만 deque의 특정 원소 접근은 O(n). 따라서 deque은, deque에 어떤 원소가 들어갔는지 상관하지 않고 특정 순서대로 데이터를 집어넣고 빼내는 연산을 원할 때 많이 쓰임.

---

이코테 2021

BaaarkingDog