스택 Stack
LIFO (Last In First Out) 구조
한 쪽에서만 데이터의 삽입 및 삭제가 가능한 자료구조
나중에 삽입된 데이터가 먼저 나오게 되는 구조
특징
top: 가장 마지막에 들어온 데이터push: top 위에 데이터 삽입pop: 가장 위에 있는 데이터 삭제
활용
재귀 알고리즘
DFS
웹 브라우저 뒤로 가기, 실행 취소
괄호 검사, 후위 연산법, 문자열 역순 출력 등
파이썬은 리스트를 활용하면 된다.
1⃣ 데이터 추가 : append()
stack = []
stack.append(1) # [1]
stack.append(2) # [1, 2]
stack.append(3) # [1, 2, 3]2⃣ 데이터 삭제 : pop()
stack.pop() # [1, 2]
stack.pop() # [1]3⃣ 데이터 유무 확인 : isEmpty()
stack.isEmpty()큐 Queue
FIFO (First In First Out) 구조
한 쪽으로 데이터를 삽입하고, 다른 쪽으로 데이터를 삭제할 수 있는 자료구조
먼저 삽입된 데이터가 먼저 나오게 되는 구조
특징
enqueue(): 큐의 한 쪽 끝에 데이터를 삽입하는 연산새로운 큐의 뒤(
rear)로 넣음
dequeue(): 다른 한 쪽 끝으로 데이터를 삭제하는 연산기존 데이터를 큐의 앞(
front)에서 빼냄
파이썬은 collections 모듈에서
deque클래스를 활용한다.활용
BFS(Breadth-First Search)
작업 스케줄링
대기열 관리
웹 서버 요청 처리
1⃣ 큐 생성 : deque()
from collections import deque
queue = deque() # 빈 큐 생성2⃣ 데이터 추가 : append()
queue.append(3) # [3]
queue.append(5) # [3, 5]
queue.append(7) # [3, 5, 7]3⃣ 데이터 삭제 : popleft()
queue.popleft() # [5, 7], 가장 앞에 있는 데이터 3 제거3⃣ 프론트 및 후방 연산
# 프론트(Front)
front = queue[0] # 5
# 후방 (Rear)
rear = queue[-1] # 7원형 큐 (Circular Queue)
일반적인 FIFO 큐의 문제인 공간 낭비를 해결하기 위해 고안된 자료구조
큐의 마지막 위치에 도달하면 다시 처음 위치로 돌아가 데이터를 저장
배열을 원형으로 사용하여 데이터를 순환하면서 저장하는 방식
특징
배열 인덱 스 처리
공간 활용
포인터 사용
class CircularQueue:
def __init__(self, size):
self.size = size # 큐 크기 설정
self.queue = [None] * size # 크기만큼의 리스트를 생성하여 큐를 초기화합니다.
self.front = self.rear = -1 # front와 rear를 초기화합니다.
def is_full(self):
# rear 다음 위치가 front인 경우 큐가 가득 찬 상태입니다.
return (self.rear + 1) % self.size == self.front
def is_empty(self):
# front와 rear가 동일한 경우 큐가 비어 있는 상태입니다.
return self.front == -1
def enqueue(self, data):
if self.is_full():
print("Queue is full")
elif self.is_empty():
self.front = self.rear = 0 # 큐가 비어 있는 경우 front와 rear를 0으로 설정합니다.
self.queue[self.rear] = data
else:
self.rear = (self.rear + 1) % self.size # rear를 다음 위치로 이동합니다.
self.queue[self.rear] = data
def dequeue(self):
if self.is_empty():
print("Queue is empty")
return None
elif self.front == self.rear:
temp = self.queue[self.front]
self.front = self.rear = -1 # 큐에 하나의 요소만 남아 있는 경우 front와 rear를 초기화합니다.
return temp
else:
temp = self.queue[self.front]
self.front = (self.front + 1) % self.size # front를 다음 위치로 이동합니다.
return temp
def front(self):
if self.is_empty():
print("Queue is empty")
return None
return self.queue[self.front]
def rear(self):
if self.is_empty():
print("Queue is empty")
return None
return self.queue[self.rear]
# 사용 예제
cq = CircularQueue(3) # 크기가 3인 환형 큐를 생성합니다.
# 큐에 데이터 삽입
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
# 큐가 가득 찬 상태 확인
print(cq.is_full()) # 출력: True
# 큐에서 데이터 삭제
print(cq.dequeue()) # 출력: 1
# 큐에 데이터 삽입
cq.enqueue(4)
# 큐의 현재 상태 출력
print(cq.queue) # 출력: [4, 2, 3]
# 큐의 front와 rear 요소 확인
print("Front element:", cq.queue[cq.front]) # 출력: Front element: 2
print("Rear element:", cq.queue[cq.rear]) # 출력: Rear element: 4덱 Deque
양방향 큐 (Double-ended queue)
양쪽 (front, rear)에서 삽입과 삭제가 모두 가능한 큐
파이썬에서는 collections 모듈의
deque클래스를 활용한다.
1⃣ 데이터 추가 : append(), appendleft()
append() : Deque의 뒤쪽에 데이터 추가
appendleft() : Deque의 앞쪽에 데이터 추가
from collections import deque
d = deque()
d.append(1) # [1]
d.append(2) # [1, 2]
d.appendleft(3) # [3, 1, 2]2⃣ 데이터 삭제 : pop(), popleft()
pop() : Deque의 뒤쪽에서 요소 제거 및 반환
popleft() : Deque의 앞쪽에서 요소 제거 및 반환
d.pop() # [3, 1]
d.popleft() # [1]