스택 다루기

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software Engineer

스택

  • LIFO: 후입선출
    • 마지막에 삽입된 항목이 가장 먼저 제거됨

책 더미 그림.

Python으로 배우는 자료구조와 알고리즘

스택

  • LIFO: 후입선출
    • 마지막에 삽입된 항목이 가장 먼저 제거됨
  • 상단에만 추가 가능
    • 스택에 푸시

스택 상단에 새 책이 추가된 책 더미 그림.

Python으로 배우는 자료구조와 알고리즘

스택

  • LIFO: 후입선출
    • 마지막에 삽입된 항목이 가장 먼저 제거됨
  • 상단에만 추가 가능
    • 스택에 푸시
  • 상단에서만 꺼내기 가능
    • 스택에서 팝

스택 상단에서 책을 꺼내는 책 더미 그림.

Python으로 배우는 자료구조와 알고리즘

스택

  • LIFO: 후입선출
    • 마지막에 삽입된 항목이 가장 먼저 제거됨
  • 상단에만 추가 가능
    • 스택에 푸시
  • 상단에서만 제거 가능
    • 스택에서 팝
  • 마지막 요소만 읽기 가능
    • 스택 피크

스택의 맨 위 책을 가리키는 화살표가 있는 책 더미 그림.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 실행 취소 기능

요소가 하나인 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 실행 취소 기능
    • 각 키 입력을 push

스택 상단에 새 요소가 추가된 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 실행 취소 기능
    • 각 키 입력을 push

스택 상단에 새 요소가 추가된 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 실행 취소 기능
    • 각 키 입력을 push

스택 상단에 새 요소가 추가된 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 실행 취소 기능
    • 각 키 입력을 push

스택 상단에 새 요소가 추가된 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 실행 취소 기능
    • 각 키 입력을 push
    • 마지막 키 입력을 pop

스택 상단에서 요소가 제거된 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 기호 검사기: ( [ { } ] )
    • 여는 기호를 push

여는 기호가 있는 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 기호 검사기: ( [ { } ] )
    • 여는 기호를 push

스택 상단에 새 여는 기호가 추가된 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 기호 검사기: ( [ { } ] )
    • 여는 기호를 push

스택 상단에 새 여는 기호가 추가된 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 기호 검사기: ( [ { } ] )
    • 여는 기호를 push
    • 닫는 기호를 check

여는 기호들과 "check "}"" 텍스트가 있는 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 기호 검사기: ( [ { } ] )
    • 여는 기호를 push
    • 닫는 기호를 check
    • 대응하는 여는 기호를 pop

스택 상단에서 여는 기호가 제거된 스택.

Python으로 배우는 자료구조와 알고리즘

스택 - 실제 활용

  • 함수 호출
    • 메모리 블록을 push
    • 실행 종료 후 pop
Python으로 배우는 자료구조와 알고리즘

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

연결 리스트로 표현된 스택.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None
Python으로 배우는 자료구조와 알고리즘

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

노드 구성 요소 이름이 표시된 연결 리스트 형태의 스택.

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

class Stack:
  def __init__(self):
    self.top = None
Python으로 배우는 자료구조와 알고리즘

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

스택의 상단을 가리키는 "TOP" 표시가 있는 연결 리스트 형태의 스택.

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

class Stack:
  def __init__(self):
    self.top = None
Python으로 배우는 자료구조와 알고리즘

스택 - push

빈 스택과 요소가 있는 스택의 표현.

def push(self, data):
Python으로 배우는 자료구조와 알고리즘

스택 - push

새 노드가 삽입될 위치를 나타내는 빈 스택과 요소가 있는 스택의 표현.

def push(self, data): 
  new_node = Node(data)

  if self.top:
Python으로 배우는 자료구조와 알고리즘

스택 - push

새 노드가 스택 상단 요소와 연결된 빈 스택과 요소가 있는 스택의 표현.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top
Python으로 배우는 자료구조와 알고리즘

스택 - push

새 노드가 삽입된 빈 스택과 요소가 있는 스택의 표현.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node
Python으로 배우는 자료구조와 알고리즘

스택 - pop

def pop(self):

  if self.top is None:

    return None

  else:

스택 상단 노드를 가리키는 "TOP" 표시가 있는 스택의 표현.

Python으로 배우는 자료구조와 알고리즘

스택 - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

스택 상단 노드를 가리키는 "popped_node" 표시가 있는 스택의 표현.

Python으로 배우는 자료구조와 알고리즘

스택 - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

"popped_node"가 상단 노드를, "TOP"이 두 번째 노드를 가리키는 스택의 표현.

Python으로 배우는 자료구조와 알고리즘

스택 - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

"popped_node"가 스택에서 분리된 노드를, "TOP"이 스택 상단 노드를 가리키는 표현.

Python으로 배우는 자료구조와 알고리즘

스택 - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

스택 상단 노드를 가리키는 "TOP" 표시가 있는 스택의 표현.

Python으로 배우는 자료구조와 알고리즘

스택 - peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None
Python으로 배우는 자료구조와 알고리즘

Python의 LifoQueue

  • LifoQueue:
    • Python의 queue 모듈
    • 스택처럼 동작
import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True
Python으로 배우는 자료구조와 알고리즘

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘

Preparing Video For Download...