스택(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