카테고리 없음
스택(Stack)
진공청소ㄱl
2024. 9. 16. 05:25
스택(Stack)이란?
스택(Stack)은 자료구조의 한 형태로, 후입선출(Last In First Out, LIFO)의 원칙에 따라 데이터를 관리한다. 쉽게 말하면 가장 마지막에 쌓은 데이터를 가장 먼저 꺼내 사용하는 방식이다. 스택은 일상생활에서도 쉽게 찾아볼 수 있는 구조다. 예를 들어, 책을 쌓아 올린 더미에서 맨 위의 책을 먼저 꺼내는 것과 같다.
실제 스택의 사용 사례로는 웹 브라우저 방문기록(뒤로가기)와 Ctrl+Z 가 있다.
구현 방법은 연결리스트와 매우 유사하지만, 연결리스트의 head 속성에 해당하는 것을 스택에서는 top 이라 한다.
스택을 구현할 때 만들 메서드는 아래와 같다.
- push(x): 자료 x를 넣는 작업, 연결 리스트의 append와 같다.
- pop(): 자료를 꺼내는 작업, 연결 리스트의 pop와 같다.
- peek(): 마지막에 넣은 자료를 확인하는 작업으로 pop과 비슷하지만, 값을 제거하지 않음
- is_empty(): 빈 스택인지 확인하는 작업
스택(Stack)의 구현 순서
노드 구현
연결리스트와 마찬가지로, 데이터를 담을 노드를 구현한다. 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.
- val은 현재 데이터, next는 다음 데이터를 의미
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
스택(Stack) 구현
스택 클래스는 스택의 가장 마지막에 들어온 데이터를 가리키는 top를 가지고 있고, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.
push()
- 스택에 데이터를 넣는 작업
- 처음의 스택에는 아무런 값도 없을 것이기 때문에 top에 None을 넣어주었다.
- push()를 할 때 노드를 생성해서 넣어주는데, 가장 마지막에 들어온 데이터이므로 top으로 지정한다.
class Stack:
def __init__(self):
self.top = None
def push(self, value):
self.top = Node(value, self.top)
pop()
- 데이터를 꺼내는 작업
- 후입선출 구조이기 때문에 top을 꺼내고 self.top의 다음 데이터인 self.top.next가 top이 된다.
def pop(self):
if self.top is None:
return None
node = self.top
self.top = self.top.next
return node.val
peek()
- 마지막에 넣은 자료를 확인하는 작업 (값 제거X)
- self.top만 리턴해준다
def peek(self):
if self.top is None:
return None
return self.top.val
is_empty()
- 빈 스택인지 확인하는 작업
def is_empty(self):
return self.top is None