Stack (LIFO, 순차적자료구조)

스택 자료구조란, 하나씩 쌓아올린 형태의 자료구조 이며, 그림과 같이 정해진 방향(한방향)으로만 쌓을 수 있다.

스택의 Push(), Pop() 원리

Stack은 보통 세가지 연산 삽입(push), 삭제(pop) 그리고 지우지 않고 스택의 가장 위 값을 알려주는 (top)이 있다.

 

후에 나올 Queue와 반대 구조인 후입선출(Last-In-First-Out) 구조이다.

 

스택의 기본구조와 세가지 함수를 간단하게 구현해보았다.

class Stack:
    def __init__(self):
        self.items=[]
    def push(self, val):
        self.items.append(val)
    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("스택이 비었습니다.")
    def top(self):
        try:
            return self.items[-1] #스택의 가장 윗부분을 return
        except IndexError:
            print("스택이 비었습니다.")
    def __len__(self):  #print(len(S))를 했을때 이 스택의 길이를 출력하기 위한 함수
        return len(self.items)

push, pop, top 함수 외의 __len__은 스택 클래스의 객체(S)를 생성하였을 때 이 객체의 길이를 len(S)를 통해 

 

구할 수 있도록 만들어 놓은 함수이다. 이렇게 클래스를 정의해놓고 이제 객체를 생성한뒤 간단하게 스택을 만들어보자,

S = Stack()
S.push(5)
S.push(3)
S.push(1)

print(S.pop())
print(S.top())
print(S.top())

스택을 생성하였고 5, 3, 1 을 차례대로 push 했으므로 아래서부터 [5, 3, 1]의 값을 가진 스택이 생성되었다.

 

그 후 pop을 통해 [5, 3] 스택이 되었고, top()은 아무리 호출하더라도 값은 받아올 수 있지만

 

스택의 구조에는 변함이 없다.

 

스택의 개념에 대해서 간단히 알아보았으며, 다음시간에는 스택을 이용하여 전위,중위,후위 계산기를 만들어보자.