[자료구조] Stack(스택)

stack(스택)이란?

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 FILO(First In Last Out, 선입후출)를 가진 자료구조이다.

스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가진다.

데이터를 넣는 push()와 데이터 꺼내는 pop() 등의 작업을 할 수 있다.

 

예시

웹 브라우저의 뒤로가기 버튼

DFS(깊이 우선 탐색)

후위 연산자의 연산 (즉, 계산기)

문서 작업의 Ctrl+Z

 

용어 설명

push: 스택에서 데이터를 삽입하는 연산이다.

pop: 스택에서 데이터를 꺼내는 연산이다. 빼낸 데이터를 Return 받는다.

top: 스택의 가장 윗 데이터를 반환한다.

empty: 스택이 비어있는 상태를 말한다.

stack overflow: 스택의 저장공간이 꽉 차있어 더 이상 push 할 수 없는 경우인데도 push하는 경우

stack underflow: 스택의 저장공간이 비어있어 더 이상 pop을 할 수 없는 경우인데도 pop할 수 없는 경우

Stack

Stack 구현하기

MAX_STACK_SIZE=3
class Stack:
    def __init__(self):
        self.stack = []
        self.top = -1
        
    def isEmpty(self):
        if self.top < 0:
            return True
        else:
            return False
            
    def isfull(self):
        if self.top>=MAX_STACK_SIZE-1:
            return True
        else:
            return False
            
    def push(self, data):
        if self.isfull():
            print("Stak is Full")
        else:
            self.stack.append(data)
            self.top+=1

    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        else:
            value=self.stack.pop()
            self.top-=1
            return value

    def top(self):
        if self.isEmpty():
            return "Stack is empty"
        else:
            return self.stack[-1]