Stack

공부한 내용을 스스로 보기 쉽게 정리한 글입니다.

Stack 의 특징

1. 접시를 쌓듯이 데이터를 쌓아 올리는 모양의 데이터 구조
2. LIFO : Last In First Out == 후입선출 or 선입후출
3. top index 가 항상 Stack의 가장 윗부분을 가리키고 있어, 우리는 top 위치만 볼 수 있다.
4. 단점 : stack 의 top 이 외에 밑에 쌓여져있는 데이터의 Search 가 안된다.

ADT

1. empty() 라는 메소드로 Stack 에 data가 있는지 없는지 확인하게 한다. empty 이면 True, not empty 이면, False 를 return 한다.
   

Stack.empty() returns Boolean
2. Stack의 top 위치에 데이터를 쌓는다.

Stack.push(data) returns None

3. Stack의 top 위치에 있는 데이터를 삭제하면서 반환한다.
   

Stack.pop() returns data
4. Stack의 top 위치에 있는 데이터를 반환하지만, 삭제하지 않는다. 어떤 데이터가 있는지 just 확인.

Stack.peek() returns data

구현 1 : by python list

• Stack 구조를 Python에 내장 되어 있는 list를 container 로 삼아 구현하게 되면, 그 구현은 매우매우 쉽다.
• Python의 List 자료형의 대단함을 그만큼 느낀다.
• 이 때 List 의 index가 큰 쪽이 top 방향이다.

  class Stack:
    def __init__(self):
      self.container=list()
  
    def empty(self):
      # ADT 를 따라서, 비어 있으면 return True 비어있지 않으면 return False
      if not self.container:
        return True
  
      return False
  
    def push(self, data):
      # list 를 활용했으므로, list.append(data)를 활용할 수 있다.
      self.container.append(data)
  
    def pop(self):
      # pop 역시 list.pop()을 활용할 수 있다.
      return self.container.pop()
  
    def peek(self):
      # peek은 단지 top 에 어떤 데이터가 있는지 확인 하는 것 뿐이므로, 현재 리스트의 가장 마지막에 append 되어 있는 data를 확인하면 된다.
      return self.container[-1]

구현 2 :