[Data Structure] 스택(Stack) 과 큐(Queue)

스택과 큐는 가장 자주 활용되는 자료구조 중 하나이다. 

 

✨ 스택(Stack)

먼저 들어온 데이터가 나중에 나가는 형식의 자료구조이며, 입출구가 하나이다.

후입선출 (LIFO; Last in First Out) 의 구조를 가지고 있다.

삽입과 삭제가 일어나는 위치를 Top 이라고 한다.

비어있는 스택에서 원소를 추출하려고 할 때는 stack underflow, 스택이 넘치는 경우는 stack overflow 이다.

 

✨스택 예시

모바일 화면의 경우, 사용자가 현재 보고 있는 화면이 Top 이다. 

다음 화면 클릭 시, 새 화면을 Stack 에 추가하고 이동한다.

이전 화면으로 돌아갈 시, 현재 화면을 Stack 에서 지우고 이동한다. 

 

✨ 큐(Queue)

먼저 들어온 데이터가 먼저 나가는 형식의 자료구조이며, 입출구가 병렬하여 두개이다.

선입선출 (FIFO; First in First Out) 의 구조를 가지고 있다.

데이터 입력은 enQueue 라고 부르며, 입력이 일어나는 위치는 꼬리/Rear 이다.

데이터 출력은 deQueue 라고 부르며, 출력이 일어나는 위치는 머리/Front 이다.

 

✨큐 예시

게임 매칭 시스템의 경우, deQueue로 유저들이 입장한다.

정해진 인원만큼 순서대로 끊어서 매칭이 되며, 이들은 enQueue 로 퇴장한다. 

 

Stack, Queue

 

✨ 구현 (Python)

스택: 

stack = [0, 1, 2, 3]

stack.append(4) # 데이터 삽입
print(stack) # [0, 1, 2, 3, 4]

stack.pop() # 4, 데이터 삭제
print(stack) # [0, 1, 2, 3]

# top 순서대로 출력하고 싶을 경우:
# 방법 1)
print(stack[::-1]) # 3, 2, 1, 0
# 방법 2)
stack.reverse() 
print(stack) # [3, 2, 1, 0]

 

큐:

from collections import deque

temp = [0, 1, 2, 3]
queue = deque(temp) 
print(queue) # deque([0, 1, 2, 3])

queue.append(4) # 데이터 삽입
print(queue) # deque([0, 1, 2, 3, 4])

queue.popleft() # 0, 데이터 삭제
print(queue) # deque([1, 2, 3, 4])

# 비어있는 queue 만들고 싶을 경우:
queue = deque()

 

✨ 데크(Deque) 란? 

Double-ended queue로, python 의 Collections 모듈에 있는 객체이다.

Stack/queue 알고리즘에 자주 활용된다. 

queue = deque([0,1,2,3])

# 알아두면 좋을 추가 메서드들

# rotate()
queue.rotate(1) # [3, 0, 1, 2]
queue.rotate(2) # [2, 3, 0, 1]
queue.rotate(-1) # [1, 2, 3, 0]

# extend(), extendleft()
queue.extend('ab') # [0, 1, 2, 3, a, b]
queue.extendleft('ab') # [b, a, 0, 1, 2, 3]

# clear()
queue.clear() # []