스택, 큐¶

스택은 Last-In-First-Out (LIFO)

큐는 First-In-First-Out (FIFO)

파이썬에서 리스트는 큐와 스택의 모든 연산을 지원하지만 큐의 연산은 비효율적이다.

따라서 Deque 를 이용하면 좋은 성능을 낼 수 있다.

스택¶

스택은 다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다.
- push(): 요소를 컬렉션에 추가한다.
- pop(): 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다.

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

In [1]:

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

In [3]:

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

In [5]:

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

In [6]:

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