자료구조 및 실습 - [6] 스택 Stack (파이썬으로 스택 구현) (1)

스택 ADT

스택 ADT는 임의의 개체를 저장하는 하나의 추상 자료형이다.

스택의 중요한 특징으로는 LIFO (Last - In First - Out), 후입선출이다. 후입선출이란 말 그대로 가장 마지막에 들어온 것을 가장 먼저 꺼내는 것이다. 이는 드럼통에 자주 비유되곤 한다.

스택에서 데이터의 삽입과 삭제는 스택의 top이라 불리는 위치에서 수행된다.

스택

스택 ADT 메서드

스택 ADT의 메서드를 알아보자.

- 주요 스택 메서드
  push : 원소를 삽입한다.
  element pop : 가장 최근에 삽입된 원소를 삭제하여 반환한다.

- 보조 스택 메서드
  element top() : 가장 최근에 삽입된 원소를 (삭제하지 않고) 반환
  integer size() : 저장된 원소의 수를 반환
  boolean isEmpty() : 아무 원소도 저장되어 있지 않고 비어 있는지 여부를 반환
  iterator elements() : 스택 원소 전체를 반환

- 예외
  emptyStackException() : 비어 있는 스택에서 삭제나 top을 시도할 경우 발령
  fullStackException() : 만원 스택에서 삽입을 시도할 경우 발령
 

 

스택 ADT 구현

스택 ADT도 다른 것과 마찬가지로 배열과 연결리스트를 이용하여 구현할 수 있다.

 

파이썬에서는 리스트로 스택을 손쉽게 흉내낼 수 있다.

>>> a = []
>>> a.append(1) # 1 추가
>>> a.append(2) # 2 추가
>>> print(a)
[1,2]

>>> a.pop() # 2 꺼냄
>>> print(a) 
[1]

 

연결리스트에 기초한 스택

단일 연결리스트를 사용하여 스택을 구현할 수 있다. 이때 삽입과 삭제가 특정위치인 top에서만 수행되므로 헤더노드는 필요없다.

 

초기화

초기에는 아무 노드도 없다.

단일연결리스트를 이용한 스택 초기화 의사코드

삽입

 

단일연결리스트를 이용한 스택 삽입 의사코드

삽입 후 top의 관리를 잘해야 한다.

 

삭제

 

단일연결리스트를 이용한 스택 삭제 의사코드

삭제 또한 삽입과 마찬가지로 top의 관리를 잘해야 한다.

 

이를 파이썬 코드로 구현하면 다음과 같다.

#단일연결리스트에 기초한 스택
class Node:
  def __init__(self,data,next=None):
    self.data = data
    self.next = next

class stack:
  def __init__(self,N): #초기화
    self.top = None
    self.full = N
    self.stacksize=0

  def push(self,data): # 삽입
    newnode = Node(data,self.top)
    self.top = newnode
    self.stacksize +=1

  def isEmpty(self): # isEmpty
    if self.top == None:
      return True
    else:
      return False
  
  def pop(self): # pop
    if self.isEmpty():
      print("Stack Empty")
    elem = self.top.data
    p = self.top
    self.top = self.top.next
    del(p)
    self.stacksize -=1
    # print("pop :",elem) #pop한 원소를 출력
    return elem
  
  def printstack(self): # 스택print
    target = self.top
    if self.isEmpty():
      print("None")
    else:
      while (target.next != None):
        print(target.data,end = ",")
        target = target.next
      print(target.data)
  
  def peek(self): # top에 있는 원소 출력
    if self.top == None:
      print("Stack Empty")
    else:
      print(self.top.data)
  
  def duplicate(self): # pop후 같은 원소 두번 push
    new = self.pop()
    if self.stacksize ==self.full:
      print("Stack Full")
    else:
      self.push(new)
    if self.stacksize ==self.full:
      print("Stack Full")
    else:
     self.push(new)

>>> a = stack(5)
>>> a.push('C')
>>> a.push('B')
>>> a.push('A')
>>> a.printstack()
A,B,C
>>> a.pop() #A를 삭제하고 출력
A
>>> a.peek() # pop과 달리 삭제하지 않고 top에 저장된 원소 출력
B
>>> a.duplicate() # 복사
>>> a.printstack()#print
B,B,C