스택: 데이터를 차곡차곡 쌓기

들어가기 앞서

스택과 큐는 쓰임새가 많아요. OS 내부의 많은 시스템이 스택과 큐를 기반으로 하며 그래프와 트리순회도 결국에는 스택과 큐로 하게 되요. 깊이 우선 탐색은 스택을 이용하는 순회이며, 너비 우선 탐색은 큐를 기반으로 합니다. 

 

스택

마지막에 들어온 데이터가 가장 먼저 나가게 되요. 

LIFO(Last In First Out)

 

ADT

Stack

- Object

  : LIFO 객체

- Operation

1. empty() -> Boolean
   : 스택이 비어 있으면 True or False
2. push(data)
   : data를 스택의 맨 위에 삽입
3. pop() -> element
   : 스택의 맨 위에 있는 데이터를 삭제하며 반환
4. peek() -> element
   : 스택의 맨위에 이쓴 데이터를 반환만 함

 

동적 배열을 이요하여 스택 구현

 

class Stack:

    def __init__(self):

        self.container = list() # 내부표현(representation): 실제로 데이터를 담을 객체는 동적 배열

    def empty(self):

        if not self.container:

            return True

    def push(self, data):

        self.container.append(data) # 맨 마지막 요소가 top 동적 배열의 맨 마지막 요소를 축라하는 것은

    def pop(self):

        if self.empty():

            return None

        return self.container.pop()

    def peek(self):

        if self.empty():

            return None

        return self.container[-1]

    

s = Stack()

s.push(1)

s.push(2)

s.push(3)

s.push(4)

s.push(5)

   

while not s.empty():

    print(s.pop(), end= ' ')

 

 > 5 4 3 2 1