자료구조 with Python : Stack(스택)
스택(Stack)은 마지막에 들어온 데이터가 가장 먼저 나가게 되는 후입선출(LIFO)의 자료구조이다. 스택도 결국에는 리스트의 특별한 케이스일 뿐이다. 입력과 출력이 한 쪽 끝단에서만 이루어진다.
스택의 구조
스택은 가장 위의 데이터를 알리는 top, 스택에 데이터를 삽입하는 push, top의 데이터를 내보내는 pop함수가 기본적인 구성이다. 이 외에도 peak나 is_empty를 구현하기도 하지만 이건 부수적인 것일 뿐이다.
Push(item)
push는 아이템을 스택에 삽입하는 함수이다. top은 1 증가시키고 top이 가리키는 위치에 아이템을 저장한다.
Pop()
pop은 아이템을 스택에서 꺼내는 함수이다. 단순 참조가 아니라 스택에서 아예 나오게 되는 것이다. top이 가리키는 위치의 아이템을 꺼낸 후 top을 1 감소시킨다.
두 함수 모두 시간 복잡도는 O(1)이고 스택은 원하는 아이템을 찾을 때는 top에서 부터 차례대로 찾아야해서 random 접근이 불가능하다.
스택의 예시
스택을 쉽게 설명하기 위해서 스택은 상자, 데이터는 상자와 너비가 같은 책이라고 예시를 든다 (책은 항상 눕혀서 상자에 넣는다). Top은 상자의 위에서 확인하는 것이라 생각한다.
스택이라는 상자에 처음 위에서 바라보면 상자의 밑바닥을 확인할 수 있다. 스택에 처음에는 자료구조라는 책을 넣는다. 상자를 위에서 봤을 때 우리는 자료구조가 있다는 것을 확인할 수 있다. 그 다음 운영체제 책을 넣고 컴퓨터 구조 책을 넣는다. 이 때 상자의 위에서 볼 수 있는 것은 컴퓨터 구조이다. Stack의 Top이 가리키는 것이 컴퓨터 구조라는 의미이다.
상자에서 우리가 꺼낼 수 있는 책은 마지막에 넣은 컴퓨터 구조이고 다른 책을 넣을 수 있는 공간 역시 컴퓨터 구조 위이다. 우리는 상자에서 컴퓨터구조, 운영체제, 자료구조 순으로 꺼낼 수 있으며 위에서 봤을 때 상자의 밑바닥이 보이면 책을 꺼내는 것이 불가능해진다.
상자에 자료구조가 있는 지 확인하려면 컴퓨터 구조 책부터 순서대로 꺼내가면서 확인을 해야한다.
Stack의 구현
이론적인 Stack (list자료형의 append(), pop() 사용하지 않음)
주소에 의한 참조가 가능하다는 조건에서 만들기 위해 dictionary 자료형을 사용했습니다. del 함수는 사전 자료형에서 시간복잡도가 1입니다.
class Stack:
def __init__(self): # 스택의 정의
self.stack = dict()
self.top = -1
def push(self, data):
self.top += 1
self.stack[self.top] = data
def pop(self):
if self.is_empty(): # 스택이 비었으면 pop이 불가능
return "Stack is Empty"
tmp = self.stack[self.top]
del self.stack[self.top]
self.top -= 1
return tmp
def size(self):
return self.top+1
def is_empty(self): # stack이 비어있는지 확인
if self.top == -1:
return True
else:
return False
def peak(self): # top이 가리키는 값
if not self.is_empty():
return self.stack[self.top]
else:
return "Stack is Empty"
def __repr__(self):
return repr(self.stack)확인 코드
stack = Stack()
stack.push("자료구조")
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
stack.push("운영체제")
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
stack.push("컴퓨터구조")
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
print("pop : {}".format(stack.pop()))
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
print("pop : {}".format(stack.pop()))
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
stack.push("알고리즘")
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
print("pop : {}".format(stack.pop()))
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
print("pop : {}".format(stack.pop()))
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))결과
위의 코드는 이론적인 부분을 확인하기 위한 코드로 실제 파이썬에서는 list 자료형의 pop 과 append를 이용하여 구현하는 것이 쉽습니다.
Stack 객체 구현 (list자료형 pop(), append() 사용 )
class Stack:
def __init__(self):
self.stack = []
self.top = -1
def push(self, data):
self.stack.append(data)
self.top += 1
def pop(self):
if self.is_empty():
return "Stack is Empty"
self.top -= 1
return self.stack.pop()
def size(self):
return len(self.stack)
def is_empty(self):
if not self.stack:
return True
else:
return False
def peak(self):
if not self.is_empty():
return self.stack[-1]
else:
return "Stack is Empty"
def __repr__(self):
return repr(self.stack)확인 코드 결과
파이썬에서 스택을 굳이 직접 구현해야하는가?
파이썬의 list자료형은 위의 예제에서 봤듯이 pop()함수가 사용가능하고 push대신 append() 함수를 사용하면 스택처럼 리스트의 사용이 가능하다. 두 함수 모두 시간 복잡도는 O(1)이기 때문에 스택에서의 구현과 동일하다. top 또한 len - 1로, peak 또한 list[-1] 로 구현이 가능한 만큼 제공되는 함수를 사용하는 것이 유리하다고 생각한다.
찾는 item이 있는지 확인하는 부분이 리스트는 앞에서 확인하지만 스택은 뒤에서부터 확인한다는 점이 조금 다르긴 할 것이다.
'프로그래밍 > 자료구조' 카테고리의 다른 글
| [자료구조][Python] : Queue with 2 Stacks(스택으로 큐 구현하기) (0) | 2021.10.03 |
|---|---|
| [자료구조][Python] : Queue(큐) (0) | 2021.10.02 |
