10. 선형 자료 구조 - 스택

 스택과 큐는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나로, 그중에서도 스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조이다. LIFO(last in first out_후입선출), 큐는 FIFO(first in first out_선입선출)로 처리된다. 

 

 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다. 큐 또한 마찬가지다. 리스트는 큐의 모든 연산을 지원한다. 다만 리스트는 동적 배열로 구혀노디어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐를 위해서는 데크라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다.

 

 연결 리스트를 이용한 스택 ADT 구현

class Node:
    def __init__(self,item,next):
        self.item=item
        self.next=next

class Stack:
    def __init__(self):
        self.last=None

    def push(self,item):
        self.last=Node(item,self.last)

    def pop(self):
        item=self.last.item
        self.last=self.last.next
        return item

stack=Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)

for _ in range(5):
    print(stack.pop())