# 5 자료구조&알고리즘 Stack

Linear Structure

Stack, Queue, deque and data collections list

위의 구조들은 아이템이 추가될 때 다른아이템 이전에 오는지 이후에 오는지에 따라 구별된다.

선형구조는 끝을 가지고 있는데,
제거(remove)와 추가(add) 과정에서 끝(end)를 선택하는 방식에 따라 데이터 구조가 달라진다.

이러한 구조들은 많은 알고리즘과 함께 다양한 문제를 해결하는데 쓰인다

Stack ( or push-down stack )

아이템의 추가와 제거가 Top에서 이루어지는것 ( Top 의 반대는 Base라 한다)

따라서 LIFO ( last - in first-out ), 후입선출이라고 하기도 하는데
최신의 아이템이 Top, 오래된 아이템이 Base에 가까운 구조이다

이러한 구조는 책이 쌓여 있는 모양과도 같으며 다른 책을 확인하기 위해서는 Top position의 책을 제거해야한다

따라서 책을 쌓기 시작한 순서와 책이 제거되는 순서는 반대인데 이러한 아이디어가 Stack의 핵심이다.
(예를 들어보면 1번책 2번책 3번책 순으로 쌓았으면 제거는 3번책 2번책 1번책)

==> 삽입순서와 제거순서가 서로 역순의 관계이다.

     e.g) 컴퓨터에서 이러한 특징은 web page의 back 버튼으로 알수있는데
           page이동이 stack으로 저장되어 지금 보고 있는 page가 Top,
           처음 본 페이지가 Base에 위치하게 된다.

Stack Operations

    - Stack()      : 빈 스택을 생성                       parameter : X       return X

    - push(item) : 새로운 item을 top으로 넣는다.   parameter : item   return X

    - pop()        : top으로 부터 item을 제거한다.   parameter : X      return : item

    - peek()       : top의 item을 확인, 제거아님      parameter : X      return : item

    - isEmpty()   : stack이 비어있는지 확인한다.     parameter : X      return : boolean

    - size()        : stack의 item갯수를 return         parameter : X      return : integer

Stack 의 구현

여느 OOP와 마찬가지로 stack의 ADT 구현은 class의 생성으로 할수 있고

stack의 operation은 method로 구현할수 있다. 

우리는 강력하고 단순한 python의 collections, list를 이용해서 구현해보도록 하자

class Stack:

def __init__(self):

self.object = [] #여기서 self.object는 Stack을 객체변수로 설정해 준것

def isEmpty(self):

return self.object == []

def push(self, item):

self.object.append(item)

def pop(self):

return self.object.pop()

def peek(self):

return self.object[-1]

def size(self):

return len(self.object)

a = Stack() #빈 Stack의 생성

print(a) # <__main__.Stack object at 0x000001F31F821860>

a.push(10) #Stack에 10이라는 item을 넣어줌

print(a.isEmpty()) # False

a.push(20)

print(a.size()) #10,20 push 했으므로 2

print(a.peek()) #top에 20이 위치해 있으므로 20

print(a.size()) #peek 메서드를 사용했으므로 size에는 변화없다 2

print(a.pop()) #top에 위치한 20이 제거된다

print(a.size()) #20이 제거되고 Stack에는 10만 남게 된다.

논리적인 특성을 유지하면서 다른 방법으로 stack을 구현할수 있는데
똑같이 작동한다 해도 성능에서 차이가 날 수 있으므로 효율적인 구현을 하는게 좋다.

e.g )

     1. list의 end부분을 top으로 사용하는 경우 ==> pop() 과 append()가 모두 O(1)의 복잡도

     2. list의 first 부분을 top으로 사용하는 경우== > pop(0) 과 insert(0)은 O(n)의 복잡도

     따라서 같은 논리적 작업을 한다해도 1번의 구현이 훨씬 더 효율적이게 된다.