[자료구조] 스택(stack) 정의 및 사용법

스택: 요소의 컬렉션으로 사용되는 추상 자료형이다. 주요 연산으로 push( )와 pop( )이 있다.

 

스택은 LIFO(Last-In-First-Out) 후입선출 구조를 가진다. 이는 쌓아둔 접시를 떠올리면 쉽게 알 수 있다. 접시는 가장 위에 있는, 즉 가장 나중에 쌓아올린 접시부터 꺼내 사용한다. 프링글스를 가장 나중에 들어간 것부터 먹는 거랑 같은 원리.

리스트가 스택의 모든 연산을 지원한다.

 

 

<연결리스트를 이용한 스택 ADT(abstract data type) 구현>

연결리스트를 아용하여 스택을 구현할 수 있지만, 리스트가 스택의 모든 연산을 지원하기 때문에 리스트를 그냥 쓰면 된다.

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)
 
for _ in range(3):
    print(stack.pop())
 
3
2
1


######### Stack using list ##########

lst = []
lst.append(1)
lst.append(2)
lst.append(3)

for _ in range(3):
    print(lst.pop())
    
3
2
1