백준 스택 단계 문제를 풀던 중에 "시간초과"로 문제를 풀지 못했다.
스택의 개념에 대해, 그리고 구현하는 방법에 대해 공부를 해야겠다는 생각이 들어서 무작정 구글에 "python stack"이라고 검색했고 아래 사이트를 발견했다.
GeeksforGeeks
위를 참고하면 되겠다!
그럼 이제 Stack에 대해 알아보자.
💡 Stack이란?
스택이란 선형 자료 구조(linear data structure)로 데이터를 LIFO(Last-in/First-Out) 또는 FILO(First-In/Last-Out) 형태로 저장한다.
"Insertion and Deletion happen on same end"
즉, 삽입(insertion)과 Deletion(삭제)가 동일한 위치에서 일어난다.
✨Stack과 관련된 함수는?
- empty(): 스택이 비었는지 참/거짓을 반환한다.
- size(): 스택의 사이즈, 크기를 반환한다.
- top(): 스택의 마지막 요소(Last in)의 reference를 반환한다. 즉, 제거하지 않고 반환한다.
- push(a): 'a'를 스택의 top에 삽입한다.
- pop(): 스택의 마지막 요소(Last in, top)을 반환하고 제거한다.
위의 함수는 모두 시간 복잡도(Time Complexity) 가 O(1) 이다.
✨Python으로 Stack을 구현할 수 있는 방법은?
- list
- Collections.deque
- queue.LifoQueue
📌list를 활용하여 Stack 구현하기
파이썬의 내장된 자료구조인 list 자체로 stack으로 사용될 수 있다.
push() 연산을 append() 함수로 수행할 수 있고, pop()로는 LIFO 구조로 stack의 요소를 제거할 수 있다.
하지만, list는 몇 개의 단점이 있다. 가장 큰 문제는 list의 크기가 커질수록 속도 문제(speed issues) 가 발생한다는 점이다. list안의 요소들은 메모리 안에 이웃하여 저장되기 때문에, 스택의 크기가 커질수록 메모리의 많은 공간을 차지하게 된다. 이로 인해 append() 호출이 훨씬 오래 걸리는 문제가 발생할 수 있다.
# 스택을 리스트로 구현
stack = []
# 스택의 push 연산을 append()로 구현
stack.append('a')
print("push(a) in to stack: ", stack)
stack.append('b')
print("push(b) in to stack: ", stack)
stack.append('c')
print("push(c) in to stack: ", stack)
# 스택의 pop 연산 수행
stack.pop()
print("\npop() from the stack: ", stack)
stack.pop()
print("pop() from the stack: ", stack)
stack.pop()
print("pop() from the stack: ", stack)
출력되는 결과는 아래와 같다.
push(a) in to stack: ['a']
push(b) in to stack: ['a', 'b']
push(c) in to stack: ['a', 'b', 'c']
pop() from the stack: ['a', 'b']
pop() from the stack: ['a']
pop() from the stack: []📌collections.deque를 활용하여 Stack 구현하기
collections 모듈의 deque 클래스를 사용하여 stack을 구현할 수 있다.
상황에 따라 list보다 Deque를 사용하는 경우가 있다.
- 컨테이너의 앞뒤, 두 구멍에서 append와 pop을 수행함으로써 더 빠른 연산이 필요할 때이다.
deque는 append()와 pop() 연산을 하는 데 시간복잡도가 O(1) 이다.
이와 비교했을 때, list는 시간복잡도가 O(n)이다.
# 스택을 collections.deque 로 구현
from collections import deque
stack = deque()deque의 append() 연산과 pop() 연산은 list와 동일하다.
⏳ ‼ 그럼 여기서 질문.. ‼
그래서 deque가 구체적으로 어떻게 list 보다 연산을 빠르게 한다는거지?? 똑같은 append 연산인데도 deque로 구현했을 때 연산이 빠르게 진행된다는 건가?
⬇ 이건 번외편인 것 같아서 따로 포스팅했다. ⬇
📌linked list 구조로 Stack 구현하기
linked list는 두 가지 메소드가 있다. addHead(item)과 removeHead()이다.
- getSize(): 스택에 있는 요소들의 개수를 반환한다.
- isEmpty(): 스택이 비어있으면 True를, 아니면 False를 반환한다.
- peek(): 스택의 top을 반환한다. 스택이 비어있다면 exception이 발생한다.
- push(value): 스택의 head에 value를 삽입한다.
- pop(): 스택의 head의 value를 반환하는 동시에 제거한다. 스택이 비어있다면 exception이 발생한다.
# 스택을 linked list 로 구현
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
# 스택을 초기화
def __init__(self):
self.head = Node("head")
self.size = 0
def __str__(self):
cur = self.head.next
out = ""
while cur:
out += str(cur.value) + "->"
cur = cur.next
return out[:-2]
# 현재 스택의 size를 반환
def getSize(self):
return self.size
# 스택이 비어있는지 확인
def isEmpty(self):
return self.size == 0
# 스택의 top item을 반환
def peek(self):
# 비어있는 스택을 peeking하는 건 아닌지 확인
if self.isEmpty():
raise Exception("Peeking from an empty stack")
return self.head.next.value
# 스택에 value를 push
def push(self, value):
# push할 Node 생성
node = Node(value)
node.next = self.head.next
self.head.next = node
self.size += 1
# 스택의 top value를 제거하고 반환
def pop(self):
if self.isEmpty():
raise Exception("Popping from an empty stack")
remove = self.head.next
self.head.next = self.head.next.next
self.size -= 1
return remove.value
if __name__ == "__main__":
stack = Stack()
for i in range(1, 11):
stack.push(i)
print(f"Stack: {stack}")
for _ in range(1, 6):
remove = stack.pop()
print(f"Pop: {remove}")
print(f"Stack: {stack}")출력은 아래와 같다.
Stack: 10->9->8->7->6->5->4->3->2->1
Pop: 10
Pop: 9
Pop: 8
Pop: 7
Pop: 6
Stack: 5->4->3->2->1