Stack 과 Queue

---

Stack

• LIFO (Last In First Out) 후입선출
• example) 쌓아둔 접시 - 접시는 순서대로 쌓고 꺼낼때는 마지막꺼부터
• 스택은 2가지 연산을 지원하는 추상자료형이다.
  • push() : 요소를 추가한다.
  • pop() : 가장 최근에 입력된 요소를 제거한후 출력
    
    

Queue

• FIFO (First In First Out) 선입선출
• example) 가게앞에 줄서는 사람들 - 먼저 줄선 사람이 먼저 간다
• 상대적으로 스택에 비해 쓰임새가 적으나 데크나 우선순위 큐와 가튼 변형들은 여러 분야에서 유용하게 쓰임
• 이외에도 우선 탐색 (Breadth-First Search) BFS 나 캐시등을 구현할때도 널리 사용
  
  
  

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

---

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

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

    # 요소 추가하면서 포인터인 cur은 추가한 요소를 바라보게하고, 추가하기 이전 값은 next로 바라보게한다.
    def push(self, item):
        self.cur = Node(item, self.cur)

    # 마지막 아이템을 꺼내고, 그이전 값으로 포인터인 cur을 변경
    def pop(self):
        item = self.cur.item
        self.cur = self.cur.next
        return item
        
        
stack = Stack()

stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)

print(stack.pop())

# 4