[Python] 스택

스택

- 물건을 쌓아 올리듯 자료를 쌓아 올린 자료구조 형태

- 스택에 저장 된 자료는 선형 구조

  선형　 ：1:1 구조 관계 갖음

  비선형  : 1:N 구조

- 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.

- 마지막에 삽입한 자료를 가장 먼저 꺼낸다. (후입 선출)

 

구현을 위한 자료구조, 연산

자료구조 : 자료를 선형으로 저장할 저장소

 - C언어에서는 배열을 사용할 수 있다.

 - 저장소 자체를 스택이라 부르기도 한다. 

 - 스택에서 마지막 삽입된 원소의 위치를 top이라 부른다.

 

연산

 - 삽입 : 저장소에 자료를 저장한다. 보통 push라고 부른다.

 - 삭제 : 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다 . 보통 pop이라 함

 - 스택이 공백인지 아닌지 확인 : isEmpty

 - 스택의 top에 있는 item(원소)을 반환하는 연산. peek

 

과정

push - A

 push - BA

  push- CBA

 pop - BA

 

알고리즘

 - PUSH

def push(item) :

  s.append(item)

 -POP

def pop():

 if len(s) == 0 :

  #underflow

  return

 else :

  return s.pop(-1)