스택(Stacks)
추가된 원소를 꺼내고자 할 때, 마지막에 넣은 원소부터 넣은 순서까지(즉, 역순으로) 꺼내게 되는 자료 구조를 스택(Stack)이라고 한다.
이와 같이, 마지막에 넣은 요소를 가장 먼저 꺼내야 하는 성질 때문에 Stack을 후입선출(LIFO: Last-In First-Out) 자료구조라고도 부른다.
스택은 다음과 같은 연산을 제공한다.
-
size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함
-
isEmpty(): 현재 스택이 비어 있는지를 판단 (size() == 0?)
-
push(x): 데이터 원소 x 를 스택에 추가
-
pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환)
-
peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음
from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
class LinkedListStack:
def __init__(self):
self.data = DoublyLinkedList()
def size(self):
return self.data.getLength()
def isEmpty(self):
return self.size() == 0
def push(self, item):
node = Node(item)
self.data.insertAt(self.size() + 1, node)
def pop(self):
return self.data.popAt(self.size())
def peek(self):
return self.data.getAt(self.size()).data