[Python] 자료구조: 스택(Stack) / LIFO

1. 기본 개념 

스택(Stack)이란 쌓아 올린다는 의미가 있다. 차곡차곡 쌓여있는 접시들을 생각해보자.

접시를 쌓을 때 위로 하나씩 올리고 뺄 때도 위에서부터 하나씩 뺀다. 중간에 있는 접시를 빼면 무너지고 만다. 여기서 순서로 생각해보면 가장 마지막에 올린 접시가 뺄 때는 가장 먼저 나간다는 것을 알 수 있다. 이것을 LIFO(Last in, First out)이라고 한다. 

 

또 다른 예시로 구멍이 하나인 통이 있다고 생각해보자. 빨강부터 보라색까지 무지개 색으로 7개의 마카롱이 있고 빨간색부터 통에 넣는다 생각하자. 마지막으로 들어가는 마카롱은 보라색인데, 꺼낼 때는 마지막으로 들어간 보라색 마카롱을 마카롱을 제일 먼저 꺼내고 제일 먼저 들어간 빨간 마카롱이 제일 마지막에 나온다. 이처럼 새로운 개체의 입력과 기존 개체의 출력이 하나의 gate에서 이뤄지되 나올 때는 들어간 순서의 반대가 유지되면 stack 구조라 할 수 있다.

 

즉, stack 구조 = LIFO 구현 이라고 생각하면 되겠다.

 

따라서 다음의 특징이 있다.

 

reversal property: 들어가는 것의 순서가 나올 때는 반대가 된다. 이를 이용하면 아이템들의 순서를 뒤집을 때 사용할 수 있다.

 

---

2. 코드

 

파이썬에는 stack에 관련된 library 또는 내장 함수는 없지만 list를 이용하여 이를 구현할 수 있다.

좀 복잡하게 보일 수 있으나 Class로 작성해보겠다.  위에서 예시로 든 마카롱 상황을 생각하며 코드를 보자.

 

 

class Stack:
    def __init__(self):
        self.box = []

    def push(self, item):
        self.box.append(item)

    def pop(self):
        return self.box.pop()

    def top(self):
        return self.box[-1]

    def size(self):
        return len(self.box)


s = Stack()
macaron = ['red','orange','yellow','green','blue','navy','purple']

s.push(macaron[0])
s.push(macaron[1])
s.push(macaron[2])
s.push(macaron[3])
print(s.top())
print(s.pop())
print(s.pop())
print(s.size())

결과를 보기 전에 우선 Class 안에 있는 함수들의 기능부터 살펴보자.

 

__init__은 Class 객체가 생성되면 자동으로 실행되는 함수다.

s = Stack()에서 클래스 객체인 s가 생성되고 s의 box가 빈 list로 생긴다. 

 

push는 새로운 item을 box에 넣되, 맨 끝(위)에 넣는다.

 

pop는 box의 맨 끝(위)에 있는 item을 꺼낸다

 

top은 box의 맨 끝(위)에 있는 item을 return한다

 

size는 box에 item이 몇 개 있는지를  return한다.

 

눈 여겨볼 것은 push와 pop이다. item이 어디서 들어오고 어디서 빠지는가?

바로 list의 맨 끝이다. 하나의 gate에서 새로운 개체의 삽입과 기존 개체의 출력이 이뤄지고 있다.

 

push를 insert(0, item), pop을 pop(0)으로 하여 list의 왼쪽에서 삽입과 출력이 이뤄지게 해도 stack구조이긴 하지만

item의 길이가 많을 경우 기존에 있던 item들의 index들을 한칸씩 미뤄야하므로 O(n)에 가까워진다. 오른쪽에서 해결할 경우 O(1)이므로 더 효율적이므로 위와 같이 구현하는 것이 좋다.

 

그림으로는 위와 같이 나타낼 수 있다.

 

 

---