[자료 및 알고리즘] 4. 스택 (파이썬)

스택이란?

 

후입선출 (Last-In First Out)의 자료구조이다.

열린 곳을 스택 상단(Top)이라고 부른다.

삽입과 삭제는 상단으로만 할 수 있고,

중간에는 항목을 삽입하거나 삭제할 수 없다.

 

스택의 추상 자료형

 

데이터 : 후입선출의 접근 방법을 유지하는 항목들의 모음

 

연산  (리스트와 다르게 위치에 대한 정보를 매개변수로 받지 않음)

- push(e) : 요소 e를 스택의 맨 위에 추가한다.

- pop() : 스택의 맨 우에 있는 요소를 꺼내 반환한다.

- isEmpty() : 스택이 비어있으면 True를 아니면 False를 반환한다.

- isFull() : 스택이 가득 차 있으면 True를 아니면 False를 반환한다.

- peek() : 스택의 맨 위에 있는 항목을 삭제하지 않고 반환한다.

 

스택의 오류 상황

 

오버플로우 (OverFlow) :

스택이 꽉 차있는 경우, push()가 수행되면 더 이상 들어갈 수 없게 되는 상황이다.

 

언더플로우 (UnderFlow) :

스택이 비어있는 경우, pop()이나 peek() 연산이 수행되면, 삭제나 참조가 불가능하기 때문에,

오류가 나는 상황이다.

 

배열을 이용한 스택의 클래스 구현

 

class ArrayStack :
	def __init__(self, capacity) :
        self.capacity = capacity
        self.array = [None]*self.capacity
        self.top = -1
    
    def isEmpty(self) :
        return self.top == -1
        
    def isFull(self) :
        return self.top == self.capacity-1
        
    def push(self,e) :
        if not self.isFull() :
            self.top += 1
            self.array[self.top] = e
        else : pass
        
    def pop(self):
        if not self.isEmpty():
            self.top -= 1
            return self.array[self.top+1]
        else : pass
    
    def peek(self):
        if not self.isEmpty():
            return self.array[self.top]
        else: pass