Stack

스택이란?

스택은 자료 구조형의 일종으로, LIFO 형식을 따르는 구조이다.

LIFO?

큐와는 반대로, 스택을 설명할 때 가장 많이 쓰는 말 중 하나는 'LIFO'다. LIFO란, Last In First Out이란 뜻이다.

영어 표기법대로, '나중에 들어간 놈이 먼저 나온다'는 뜻이다. 즉 가장 늦게 입력된 원소가 가장 먼저 출력된다는 것을 의미한다.

 

스택의 필수요소들

스택도 큐와 같이 자료 구조이다. 따라서 자료들을 넣고 뺄 수 있어야 하며, 스택의 상태도 조사할 수 있어야 한다.

• Push e: 스택의 가장 앞에 원소 e를 삽입한다.
• Pop: 스택의 가장 앞에 있는 원소를 빼서 return한다. 스택이 비어 있으면 에러를 return한다.
• Top: 스택의 가장 앞에 있는 원소의 값을 return한다. 빼지는 않는다.
• Empty: 스택이 비었으면 True, 아니면 False를 return한다.
• Length: 스택의 길이를 return한다.

실제 큐의 예시

빈 스택 S를 하나 만들자...

명령어	return	스택의 상태
Push a		a
Push b		a, b
Pop	b	a
Push c		a, c
Enqueue d		a, c, d
Length	3	a, c, d
Empty	False	a, c, d
Pop	d	a, c
Top	c	a, c
Pop	c	a
Pop	a
Empty	True
Pop	Error

스택의 구현

스택 역시 배열로 구현할 수 있다.

class Stack:
  def __init__(self):
    self.s=[]
  def length(self):
    return len(self.s)
  def empty(self):
    return not self.length()
  def Push(self, e):
    self.s=[e]+self.s
  def Pop(self):
    if self.empty():
      raise Empty()
    else:
      x=self.s[0]
      self.s=self.s[1:]
      return x
  def Top(self):
    if self.empty():
      raise Empty()
    else:
      return self.s[0]