9장. 스택, 큐

스택과 큐

스택 : LIFO
큐 : FIFO

리스트와 deque

• 리스트는 스택과 큐의 모든 연산을 지원함
• deque를 쓰는것이 훨씬 효율적이다

스택

주요 연산

스택은 다음과 같은 2가지 주요 연산을 지원하는 컬렉션으로 사용되는 추상 자료형이다.

• push : 요소를 컬렉션에 추가
• pop : 가장 최근에 삽입된 요소를 제거

스택 구현

• 연결 리스트로 구현됨
• ADT 는 스택의 연산을 지원하기 위해 각 요소가 접시 쌓듯 차곡차곡 쌓이겠지만, 실제로 연결 리스트로 구현하게 된다면 물리 메모리 상에는 순서와 관계 없이 여기저기에 무작위로 배치되고 포인터로 가리키게 된다.

*(ADT : 자료형의 연산을 정의한 것. 쉽게말해, 실제 구현과 달리 알아보기 쉽게 구현을 정의한 것)

스택 ADT 구현 코드

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

class stack:
  def __init__(self):
    self.last = None
  
  # "None <- 1(last)" 이런 링크드 리스트에 stack.push(2)를 하면 
  # "None <- 1 <- 2(last)" 가 되고, last 포인터는 노드 1을 가리키다가 노드 2를 가리킨다. 
  def push(self,data):
    self.last = Node(data,self.last)
 
  # stack.pop() 을 하면, "None <- 1 <- 2(last)" 인 링크드 리스트인 경우 
  # "None <- 1(last) <- 2" 가 된다. 즉 last 포인터가 한 칸 앞으로 이동하고 last 포인터가 가리키는 노드의 값인 1을 리턴한다.
  def pop(self):
    data = self.last.data
    self.last = self.last.next
    return data

s = stack() # None(last)
s.push(1) # None <- 1(last)
s.push(2) # None <- 1( <- 2(last)
s.push(3) # None <- 1 <- 2 <- 3(last)
s.push(4) # None <- 1 <- 2 <- 3 <- 4(last)

for _ in range(2):
  print(s.pop())
# None <- 1 <- 2 <- 3(last) <- 4
# None <- 1 <- 2(last) <- 3 <- 4()