파이썬 알고리즘 인터뷰 - 스택, 큐

스택

스택

• 다음과 같이 2가지 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다(LIFO 형태)
• push() : 요소에 컬렉션을 추가한다.
• pop() : 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다.
• 거의 모든 애플리케이션을 만들 때 사용되는 자료구조, 컴퓨터 서브루틴에 대한 정보를 저장하는 자료구조

 

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

 

스택 추상 자료형와 메모리 구현

• 다음 그림은 스택 추상 자료형을 연결 리스트로 구현한 것이다. ADT는 스택의 연산을 지원하기 위해 1~5까지 각 요소를 쌓겠지만 실제로 연결 리스트로 구현하게 되면 물리 메모리 상에는 순서 관계없이 무작위로 배치되고 포인터로 가리키게 된다.

다음과 같이 연결 리스트를 담을 Node 클래스부터 정의한다.

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

초기화 함수 __init__()에서 노드의 값은 item으로, 다음 노드를 가리키는 포인터는 next로 정의한다. 스택의 연산인 push()와 pop()을 담은 Stack 클래스를 다음과 같이 정의한다.

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

push()는 연결 리스트에 요소를 추가하면서 가장 마지막 값을 next로 지정하고, 포인터인 last는 가장 마지막으로 이동시킨다. pop()은 가장 마지막 아이템을 끄집어내고 last 포인터를 한 칸 앞으로 전진시킨다. 즉, 이전에 추가된 값을 가리키게 한다. 이제 다음과 같이 1~5까지 값을 스택에 입력한다.

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

stack은 각각 이전 값을 가리키는 연결 리스트로 구현되어 있으며, 가장 마지막 값은 last 포인터가 가리킨다. 그리고 pop() 메소드로 스택의 값을 차례대로 출력해보자.

for _ in range(5):
  print(stack.pop())
# 5
# 4
# 3
# 2
# 1

LIFO 순으로 출력되는 것을 확인할 수 있다.

 

큐

큐 

• 시퀀스의 한쪽 끝에는 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 컬렉션이다.\
• Enqueue() : 데이터를 입력
• Dequeue() : 데이터를 출력
• FIFO 구조를 하고 있고 BFS나 캐시 등을 구현할 때 널리 사용된다.
• 스택에 비해 쓰임새가 적지만 데크나 우선순위 큐 등 변형들은 여러 분야에 쓰인다.