스택(stack)
데이터를 임시 저장할 때 사용하는 자료구조이며 데이터 입력과 출력 순서는 후입선출(LIFO)이다.
스택에서 데이터 입력을 push라 하며 데이터 꺼내는 작업을 pop이라 한다.
고정길이 스택 구현
함수 : len, push, pop, peek, clear, isEmpty, isFull, find, count, contains, dump
from typing import Any
class Stack:
def __init__(self, capacity: int):
self.stk = [None] * capacity
self.ptr = 0
self.capacity = capacity
def __len__(self) -> int:
return self.ptr
class Empty(Exception):
pass
class Full(Exception):
pass
def push(self, val: Any) -> None:
if self.isFull():
raise self.Full
self.stk[self.ptr] = val
self.ptr += 1
def pop(self) -> None:
if self.isEmpty():
raise self.Empty
self.ptr -= 1
self.stk[self.ptr] = None
def peek(self) -> None:
if self.isEmpty:
raise self.Empty
return self.stk[self.ptr - 1]
def clear(self) -> None:
self.stk = [None] * self.capacity
self.ptr = 0
def isEmpty(self) -> bool:
return self.ptr == 0
def isFull(self) -> bool:
return self.ptr == self.capacity
def find(self, val: Any) -> Any:
for i in range(self.ptr-1, -1, -1):
if self.stk[i] == val:
return i
return -1
def count(self, val: Any) -> int:
cnt = 0
for i in range(self.ptr):
if self.stk[i] == val:
cnt += 1
return cnt
def __contains__(self, val: int) -> bool:
for i in range(self.ptr - 1, -1, -1):
if self.stk[i] == val:
return True
return False
def dump(self) -> None:
if self.isEmpty():
print("isEmpty")
else:
print(self.stk[:self.ptr])
stack = Stack(10)
stack.push(5)
print(stack.find(5))
stack.dump()
큐(queue)
스택과 같이 데이터를 임시 저장하는 자료구조이며 데이터 입력과 출력 순서는 선입선출(FIFO)이다.
큐에서 데이터 입력을 enqueue라 하며 데이터 꺼내는 작업을 dequeue라 한다.
그리고 꺼내는쪽을 front, 넣는쪽을 rear라 한다.
링 버퍼로 큐 구현하기
링 버퍼란 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조이다.
함수 : len, enque, deque, peek, clear, isEmpty, isFull, find, count, contains, dump
from typing import Any
class Queue:
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.que = [None] * self.capacity
self.rear = 0
self.front = 0
self.cnt = 0
def __len__(self):
return self.cnt
class Empty(Exception):
pass
class Full(Exception):
pass
def isEmpty(self):
return self.cnt == 0
def isFull(self):
return self.cnt == self.capacity
def enqueue(self, val: Any) -> None:
if self.isFull():
raise self.Full
self.que[self.rear] = val
self.rear += 1
if self.rear == self.capacity:
self.rear = 0
self.cnt += 1
def dequeue(self):
if self.isEmpty():
raise self.Empty
self.que[self.front] = None
self.front += 1
if self.front == self.capacity:
self.front = 0
self.cnt -= 1
def peek(self):
if self.isEmpty():
raise self.Empty
return self.que[self.front]
def clear(self):
self.que = [None] * self.capacity
self.rear = 0
self.front = 0
self.cnt = 0
def find(self, val: Any):
if self.rear < self.front:
for i in range(self.rear, self.capacity):
if self.que[i] == val:
return i
for i in range(self.front):
if self.que[i] == val:
return i
else:
for i in range(self.rear, self.front):
if self.que[i] == val:
return i
return -1
def count(self, val: Any):
cnt = 0
if self.rear < self.front:
for i in range(self.front, self.capacity):
if self.que[i] == val:
cnt += 1
for i in range(self.rear):
if self.que[i] == val:
cnt += 1
else:
for i in range(self.front, self.rear):
if self.que[i] == val:
cnt += 1
return cnt
def __contains__(self, val) -> bool:
if self.rear < self.front:
for i in range(self.front, self.capacity):
if self.que[i] == val:
return True
for i in range(self.rear):
if self.que[i] == val:
return True
else:
for i in range(self.front, self.rear):
if self.que[i] == val:
return True
return False
def dump(self):
if self.isEmpty():
print("비었음")
else:
print(self.que)
print(self.rear, self.front)
if self.rear < self.front:
print(self.que[self.front:self.capacity] + self.que[:self.rear])
else:
print(self.que[self.front:self.rear])
알면 좋은 것
- 양방향 대기열 자료구조는 덱(deque)이라 한다.
- 우선순위 큐는 인큐할 때 데이터에 우선순위를 부여하여 추가하고 디큐할 때 우선순위가 가장 높은 데이터를 꺼내는 방식이다. 파이썬에서는 heapq모듈에서 제공한다.
참고) Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편