일반적인 의미: 물건이 쌓여있는 더미(Stack)
자료구조에서의 의미: 자료 더미 + LIFO 방식(동적인 특징)
LIFO(Last-In-First-Out): 후입선출 방식을 말한다.
스택 생성
: 스택을 생성한다. push
: 새로운 자료를 추가하는 연산스택오버플로우(Stack Overflow)
: 용량 제한으로 더 이상 원소를 추가하지 못할 때 발생한다.pop
: 가장 늦게 들어온 자료(최상위 자료)를 제거하는 연산peek
: 가장 늦게 들어온 자료(최상위 자료)를 읽은 후 이를 반환하는 연산 (제거 x) 스택 삭제
: 스택을 제거한다.# 파이썬의 리스트(list)를 이용하여 스택을 구현
class Stack:
# 빈 리스트로 스택 생성
def __init__(self):
self.data = []
# 스택 크기 반환
def __len__(self):
return len(self.data)
# 스택의 내부 자료를 문자열로 변환하여 반환
def __str__(self):
return str(self.data[::1])
# 스택이 비어있는지 체크
def is_empty(self):
return len(self.data) == 0
# 스택에 새로운 자료 추가
def push(self, item):
self.data.append(item)
# 스택의 최상위 자료 제거
def pop(self):
# 스택이 비어있는지 반드시 체크
if self.is_empty():
print("Stack Underflow")
exit()
# 비어있지 않으면 최상위 자료를 제거 후 반환
return self.data.pop(-1)
# 스택의 최상위 자료 읽기(제거 x)
def peek(self):
# 스택이 비어있는지 반드시 체크
if self.is_empty():
print("Stack Underflow")
exit()
# 비어있지 않으면 최상위 자료를 읽은 후 반환
return self.data[-1]
# 스택에 자료가 포함되어 있는지 여부 반환
def contains(self, item):
return item in self.data
# 스택 클리어
def clear(self):
self.data = []
# 스택 생성
stack = Stack()
# 스택 크기 출력
# 0
print(len(stack))
# 스택 비어있는지 여부 출력
# True
print(stack.is_empty())
# 스택에 자료 추가
stack.push(1)
stack.push(2)
# 스택 출력
# [1, 2]
print(stack)
# 스택에 자료 포함되어 있는지 여부 출력
# True
print(stack.contains(1))
# 최상위 자료 제거
stack.pop()
# 스택 출력
# [1]
print(stack)
# 최상위 자료 읽기
# 1
print(stack.peek())
# 스택 클리어
stack.clear()
# 스택 비어있는지 여부 한 번 더 확인
# True
print(stack.is_empty())
자료구조 | 동작 | 코드 | 설명 |
---|---|---|---|
스택 | 초기화 | stack = [] | 빈 리스트를 만듦 |
자료 추가(push) | stack.append(data) | 리스트의 맨 뒤에 자료를 추가 | |
자료 삭제(pop) | data = stack.pop() | 리스트의 맨 뒤에서 자료를 꺼냄 | |
큐 | 초기화 | queue = [] | 빈 리스트를 만듦 |
자료 추가(enqueue) | queue.append(data) | 리스트의 맨 뒤에 자료를 추가 | |
자료 삭제(dequeue) | data = queue.pop(0) | 리스트의 맨 앞(0번 위치)에서 자료를 꺼냄 |