🌈 스택(Stack) & 큐(Queue)
🔥 스택(Stack)이란?
🔥 큐(Queue)란?
🔥 스택(Stack) 예제 풀이
🔥 큐(Queue) 예제 풀이
1. 스택(Stack)이란?
- 스택은 후입선출(LIFO)의 데이터의 입출력 방식의 자료구조
- 후입선출 방식(LIFO)이란 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다는 의미임
- 박스 쌓기를 하는 것처럼 스택을 쌓는다고 할 때, 데이터를 쌓아올리는 과정이 푸시(push)이고, 스택에서 데이터를 제거하는(꺼내는) 작업이 팝(pop)임
- 이렇게 push하고 pop하는 맨 윗부분을 꼭대기(top)이라 하고, 아랫부분을 바닥(bottom)이라 지칭
- 즉, push한 데이터는 스택에 꼭대기(top) 계속해서 쌓아 올리고, pop을 하면 꼭대기(top)에 위치한 데이터가 꺼내지기 때문에 pop을 하면 마지막에 push한 데이터를 꺼낼 수 있음
- 또한 스택의 크기(capacity)란 스택에 쌓을 수 있는 데이터의 최대 갯수를 의미함
- 스택의 포인터(ptr)은 데이터의 갯수를 나타내는 정수값으로 스택이 비어있으면 0이 되고, 스택이 가득차 있으면 capacity와 같은 값이 됨
- 스택 배열(stk)은 push한 데이터를 저장하는 list형 배열이며, 가장 먼저 푸시하여 데이터를 저장한 곳을 stk[0] 이라함
✍🏻 스택 구현 예제1
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]) # [1, 3, 2, 5] print(stack) # [5, 2, 3, 1]
✍🏻 스택 구현 예제2
def stack_push(stack, value): stack.append(value) def stack_pop(stack): last = stack.pop() return last # 배열 생성 stack = [] # push stack_push(stack, 5) stack_push(stack, 6) stack_push(stack, 7) stack_push(stack, 8) print(stack) # [5, 6, 7, 8] # pop last = stack_pop(stack) print(last) # 8 print(stack) # [5, 6, 7]
2. 큐(Queue) 란?
- 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 자료 구조
- 예를 들어 은행 창구나, 마트에서 계산을 기다리는 대기열 방식의 입출력 방식을 가짐
- 큐에 데이터를 추가하는 작업은 인큐(enqueue), 데이터를 꺼내는 작업은 디큐(dequeue)라 함
- 또한 데이터를 꺼내는 쪽인 맨 앞을 프런트(front), 넣는 쪽인 맨 끝을 리어(rear)라 지칭
- 큐 자료구조는 모든게 뚤려있는 터널과 같은 자료 구조로 상상해볼 수 있음
- python에서 큐를 구현하는 방법으로
Array.pop(0)도 가능하나 시간 복잡도가 높기 때문에 덱(deque) 라이브러리를 사용Array.pop(0)은 배열의 첫번째 요소를 꺼낸 뒤, 공백으로 만든 후 한칸씩 앞으로 요소를 옮겨 마지막 빈 요소의 공간을 최종적으로 제거하기 때문에 O(N)의 복잡도 가짐- 큐는는 DFS 구현할 때 자주 사용함
✍🏻 pop함수로 큐 구현
queue = [] queue.append(5) queue.append(6) queue.append(7) print(queue) # [5, 6, 7] front = queue.pop(0) print(front) # 5 print(queue) # [6, 7] # pop(0)으로 que를 구현했을 때 나타나는 과정 # O(n) 복잡도 # [5, 6, 7] -> [-, 6, 7] -> [6, -, 7] -> [6, 7, -] -> [6, 7]
- 이에 que를 다룰 때는 deque 라이브러리 사용
- deque는 시간복잡도가 O(1)이기 때문에 효율적임
- deque 라이브러리로 처리 한 결과를 list로 캐스팅하면 배열로 반환받을 수 있음
✍🏻 큐 구현 예제1
#que를 구한하기 위해 deque 라이브러리 사용 from collections import deque queue = deque() #deque 객체 생성 queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue) # deque([3, 7, 1, 4]) queue.reverse() print(queue) # deque([4, 1, 7, 3])
✍🏻 큐 구현 예제2
#que를 구한하기 위해 deque 라이브러리 사용 from queue import deque queue = deque() #deque 객체 생성 queue.append(5) queue.append(6) queue.append(7) queue.append(8) print(queue) # deque([5, 6, 7, 8]) front = queue.popleft() print(front) # 5 print(queue) # deque([6, 7, 8]) print(list(queue)) # [6, 7, 8]
✍🏻 큐 구현 예제3
from queue import deque # push def queue_push(q, value): q.append(value) # pop def queue_pop(q): front = q.popleft() return front # 호출 queue = deque() queue_push(queue, 5) queue_push(queue, 6) queue_push(queue, 7) queue_push(queue, 8) front = queue_pop(queue) print(front) # 5 print(list(queue)) # [6, 7, 8]
1) 일반적인 큐(FIFO 정책)
- queue.Queue() 로 Queue 객체 생성
- enqueue 방법 : 🔍 [Queue 객체].put(데이터)
- 삽입할 데이터를 인자로 넣음
- dequeue 방법 : 🔍 [Queue 객체].get()
- 맨 먼저 들어간 데이터를 추출하기 때문에 인자가 들어가지 않음
import queue data_queue = queue.Queue() # Que 생성 data_queue.put('queue') # enqueue(삽입) data_queue.put('python') # enqueue(삽입) data_queue.put(100) # inqueue(삽입) print(data_queue.qsize()) # 3 print(data_queue.get()) # queue 👈 dequeue(추출) print(data_queue.qsize()) # 2
2) LifoQueue(LIFO 정책)
- LifoQueue는 마지막에 들어간 것이 먼저 나오는 LIFO 정책을 사용(stack과 유사)
- get을 통해 dequeue하면, 마지막에 put한 데이터가 반환하고 삭제되는 것을 볼 수 있음
import queue data_queue = queue.LifoQueue() data_queue.put('lifoqueue') data_queue.put('python') data_queue.put(100) print(data_queue.qsize()) # 3 print(data_queue.get()) # 100 print(data_queue.qsize()) # 2
3) PriorityQueue(우선순위 큐)
- 우선순위 큐는 데이터를 삽입할 때 마다 우선순위 번호를 넣어, 우선 순위에 따라 데이터를 추출
- 일반적인 Queue & LifoQueue는 데이터가 enqueque된 시간적 순서와 dequeque가 관련있으나, PriorityQueue는 우선순위에 따라 dequeque가 처리됨
- PriorityQueue enqueue 방법 : 🔍 [Queue 객체].put((순위, 데이터))
import queue data_queue = queue.PriorityQueue() data_queue.put((10, "priorityQueue")) data_queue.put((5, "python")) data_queue.put((1, 100)) # 튜플 형태로 삽입하며, (우선순위, 데이터) 순으로 입력 print(data_queue.qsize()) # 3 print(data_queue.get()) # (1, 100) -> 우선 순위가 높은(번호가 낮은) 것부터 추출 print(data_queue.get()) # (5, 'python')
3. 스택(Stack) 예제 풀이
1) BOJ 9012번 - 괄호
- 대표적인 stack 문제로, 입력받은 문자열(괄호)를 순회하며, '('이 나타나면, stack에 push하고, ')'이 나타나면 pop하는 문제임
- 기준을 '
(' 인 이유는 stack에 '('가 담겨지지 않는 상태에서 ')' 마주하면 대칭을 이루지 못해 VPS가 될수 없기 때문- 위에 stack에 '
('가 담겨지지 않는 상태란, stack이 비어있음(len(stack) == 0)을 의미- 또한 모든 문자열 케이스는 공백이 없이 들어가야하기 때문에 문자열 받을 때, strip()
import sys # push 함수 def stack_push(stack, value): stack.append(value) # pop 함수 def stack_pop(stack): last = stack.pop() return last # T는 케이스 횟수 T = int(sys.stdin.readline()) for j in range(T): stack = [] res = True s = sys.stdin.readline().strip() # 케이스 공백 없이 입력 # 케이스 순회 for i in range(len(s)): if s[i] == '(': # '(' 일때 push stack_push(stack, '(') elif s[i] == ')': # ')' 일때 if len(stack) == 0: # stack이 비어있으며 바로 No res = False break last = stack_pop(stack) if last == '(': continue # stack에서 pop한게 '(' 라면 keep going! # for문 종료됨 if len(stack) != 0: # for문을 완료하였는데, stack에 남아있는게 있다면 res = False # 짝이 없는 '(' 가 stack에 남아있다는 의미이기 때문에 False if res: print('Yes') else: print('No')
2) 위 문제 활용에 {} 와 [] 추가하여 VPS 검증
import sys # push 함수 def stack_push(stack, value): stack.append(value) # pop 함수 def stack_pop(stack): last = stack.pop() return last # T는 케이스 횟수 T = int(sys.stdin.readline()) for j in range(T): s = sys.stdin.readline().strip() stack = [] res = True for i in range(len(s)): if s[i] == '(' or s[i] == '{' or s[i] == '[': stack_push(stack, s[i]) else: # s[i] == ),},] if len(stack) == 0: res = False break last = stack_pop(stack) if s[i] == ')': if last == '(': continue else: # last == {, [ res = False break elif s[i] == '}': if last == '{': continue else: # last == (, [ res = False break else: # s[i] == ']' if last == '[': continue else: # last == (, { res = False break if len(stack) != 0: res = False if res: print('Yes') else: print('No')
4. 큐(Queue) 예제 풀이
1) BOJ 1158번 : 요세푸스 문제
- N은 인원수이고, K는 몇번째 인원을 제거할지에 대한 입력값으로 계속해서 K번째 사람을 제거
- 출력은 몇번째 사람이 제거됬는지에 대한 순서 리스트라고 생각하고 풀면됨
# N이 7이고 K가 3일 때, # 1,2,3,4,5,6,7 ⇢ input값 7과 같음 = 🔥 res = [] # 2,3,4,5,6,7,1 ⇢ 1회 회전(popleft한 뒤, push) # 3,4,5,6,7,1,2 ⇢ 2회 회원(popleft한 뒤, push) # 4,5,6,7,1,2 ⇢ 맨 앞 제거(popleft) = 🔥 res = [3] # 5,6,7,1,2,4 ⇢ 1회 회전(popleft한 뒤, push) # 6,7,1,2,4,5 ⇢ 2회 회전(popleft한 뒤, push) # 7,1,2,4,5 ⇢ 맨 앞 제거(popleft) = 🔥 res = [3,6] # 1,2,4,5,7 ⇢ 1회 회전(popleft한 뒤, push) # 2,4,5,7,1 ⇢ 2회 회전(popleft한 뒤, push) # 4,5,7,1 ⇢ 맨 앞 제거(popleft) = 🔥 res = [3,6,2] # 5,7,1,4 ⇢ 1회 회전(popleft한 뒤, push) # 7,1,4,5 ⇢ 2회 회전(popleft한 뒤, push) # 1,4,5 ⇢ 맨 앞 제거(popleft) = 🔥 res = [3,6,2,7] # 4,5,1 ⇢ 1회 회전(popleft한 뒤, push) # 5,1,4 ⇢ 2회 회전(popleft한 뒤, push) # 1,4 ⇢ 맨 앞 제거(popleft) = 🔥 res = [3,6,2,7,5] # 4,1 ⇢ 1회 회전(popleft한 뒤, push) # 1,4 ⇢ 2회 회전(popleft한 뒤, push) # 4 ⇢ 맨 앞 제거(popleft) = 🔥 res = [3,6,2,7,5,1] # 4 ⇢ 1회 회전(popleft한 뒤, push) # 4 ⇢ 2회 회전(popleft한 뒤, push) # 4 ⇢ 맨 앞 제거(popleft) = 🔥 res = [3,6,2,7,5,1,4]
- 즉, popleft() & push()를 2회 하고, popleft()로 제거된 맨 앞의 수를 list에 추가시키는 문제
- 2회 popleft()와 push()하는 방법은 k-1만큼, for문을 통해 반복
from queue import deque import sys # push 함수 def queue_push(q, value): q.append(value) # popleft 함수 def queue_pop(q): front = q.popleft() return front # n,k 입력 n,k = list(map(int, sys.stdin.readline().split())) # 리스트 생성 queue = deque() for i in range(1, n+1): queue_push(queue, i) # n이 7이라면 -> [1,2,3,4,5,6,7] # [1,2,3,4,5,6,7] 가 존재할 때까지 반복 res = [] while len(queue) != 0: # k-1 반복 : k가 3일때 2번회전하면 되기 때문 for i in range(k-1): front = queue_pop(queue) # popleft 실행 queue_push(queue, front) # popleft한 값을 다시 맨 끝에 삽입 res.append(queue_pop(queue)) # 맨 앞에 있는 것을 res에 추가 print("<", ', '.join(str(i) for i in res), ">", sep="")
Keep Going, Keep Coding!