1. 스택(stack)
선입후출 객체 (Last In First Out, LIFO)
별도 모듈 없이 리스트로 사용
스택 내부 표현은 동적 배열로, 연산 구현은 리스트 함수를 래핑하는 방법으로 추상화
→ 프로그래머들은 리스트가 동적 배열로서 리스트인지 스택으로서 리스트인지 분석할 필요가 있다.
출처: https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D
1-1. 스택의 활용
OS가 관리하는 메모리 영역 중 지역변수가 할당되는 스택 메모리
트리에서의 데이터 순회
깊이 우선 탐색
1-2. 스택 구현
-
empty(): 스택이 비어있으면 True, 아니면 false 반환 -
push(data): data를 스택의 맨 위(마지막)에 삽입 -
pop(): 스택의 맨 위 데이터 삭제, 반환 -
peek(): 스택의 맨 위 데이터 반환
class Stack:
def __init__(self):
self.container = list()
def empty(self):
if not self.container:
return True
else:
return False
def push(self, data):
self.container.append(data)
def pop(self):
if self.empty():
return None
return self.container.pop()
def peek(self):
if self.empty():
return None
return self.container[-1]
2. 큐(queue)
선입선출 객체 (First In First Out, FIFO)
2-1. 큐의 활용
- OS 스케줄링 (태스크 큐): 여러 프로그램에서 작업을 요청받아 큐에 담아 정해진 알고리즘에 따라 큐에서 태스크를 꺼내 실행
2-2. 큐 구현
동적 배열을 사용한 구현
-
is_empty(): 큐가 비어있으면 True, 아니면 False 반환 -
is_full(): 큐가 가득 찼으면 True, 아니면 False 반환 -
enqueue(data): 큐의 맨 뒤에 데이터 삽입 -
dequeue(): 큐의 맨 처음 데이터를 삭제, 반환- 동적 배열의 맨 처음 데이터를 삭제 → O(n)
-
peek(): 큐의 맨 처음 데이터 반환
class Queue:
def __init__(self):
self.container = list()
def empty(self):
if not self.container:
return True
else:
return False
def enqueue(self, data):
self.container.append(data)
def dequeue(self):
return self.container.pop(0)
def peek(self):
return self.container[0]
2-3. 원형 큐 구현 (circular queue)
선형으로 이어져있는 동적 배열을 원형처럼 사용하는 방법
맨 마지막의 다음을 가리키는rear→ 원형 큐가 비어있을 때와 가득 찼을 때를 구분 가능하게 함
__step_forward(x): front나 rear를 뒤로 이동했을 때 동적 배열을 벗어난다면 동적 배열의 맨 처음으로 이동시키는 편의 함수
class CQueue:
MAXSIZE = 10 # 동적 배열 크기 설정
def __init__(self):
self.container = [None for _ in range(CQueue.MAXSIZE)]
self.front = 0
self.rear = 0
def if_empty(self):
if self.front == self.rear:
return True
return False
# 편의 함수
def __step_forward(self, x):
x += 1
if x >= CQueue.MAXSIZE:
x = 0
return x
def if_full(self):
next = self.__step_forward(self.rear)
if next == self.front:
return True
return False
def enqueue(self, data):
if self.is_full():
raise Exception("The queue is full")
self.container[self.rear] = data
self.rear = self.__step_forward(self.rear)
def dequeue(self):
if self.is_empty():
raise Exception("Tue queue is empty")
ret = self.container[self.front]
self.front = self.__step_forward(Self.front)
return ret
def peek(self):
if self.is_empty():
raise Exception("The queue is empty")
return self.container[self.front]
3. 데크(double-ended queue, deque)
front, rear에서 입출력 모두 가능
collections의deque사용
인덱스로 양 끝에 접근할 때는 O(1), 중간 데이터에 접근할 경우 O(n) → 이중 연결 리스트를 이용하여 구현함을 유추할 수 있음
from collections import deque
deque_test = deque()
# 값 삽입하기
deque_test.append(1)
deque_test.appendleft(2)
# 값 삭제, 반환
deque_test.pop()
deque_test.popleft()
