나중에 들어간 데이터가 가장 먼저 나오는 자료구조이다.
웹브라우저의 뒤로가기, DFS(깊이 우선 탐색), 후위 연산자의 연산(계산기) 등 에서 활용된다.
파이썬에서는 스택 자료형을 별도로 제공하지는 않지만 리스트가 스택의 모든 연산을 지원한다.
class stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
self.items.pop()
def isEmpty(self):
return not self.items
class Node:
def __init__(self, item, next):
self.item = item
self.next = next
class Stack_by_LinkedList:
def __init__(self):
self.top = None
def push(self, item):
self.top = Node(item, self.top)
"""
Node 1개, self.top = {item:val1, next:self.top}
Node 2개, self.top = {item:val2, next:{item:val1, next:self.top}}
Node 3개, self.top = {item:val3, next:{item:val2, next:{item:val1, next:self.top}}}
. . .
"""
def pop(self):
if self.top is None:
return None
node = self.top
self.top = self.top.next
return node.item
def is_empty(self):
return self.top is None