개념
정의
접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조
특징
- 후입선출(Last-In, First-Out, LIFO) 리스트
- 가장 최근에 들어온 데이터가 가장 먼저 나감
- top(peek) 이라고 하는 한쪽 끝에서 모든 삽입, 삭제 연산이 일어나는 순서 리스트
파이썬
- 파이썬에서 스택을 이용할 땐 별도의 라이브러리를 사용할 필요가 없다.(파이썬 에서는 list [] 로 이미 구현되어있다.)
- 리스트 자료형을 사용하여 스택을 구현한다.
- append() - 리스트의 가장 뒤쪽에 데이터를 삽입
- pop() - 리스트의 가장 뒤쪽에서 데이터를 꺼냄
- 파이썬 내에서의 stack은 보통 deque를 활용해서 구현한다.
필기
-
개념을 이해하기 위해서는 백준 10828문제를 푸는게 좋다.
https://www.acmicpc.net/problem/10828
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.실제로 문제에 적혀있는 조건들인데, 스택형 구조는 저 5가지의 명령어를 이해하는 선에서 대부분 정리된다. 나는 top을 peek으로 배웠던 기억이 있는데, 실제로 두 용어를 혼용해서 많이 사용하는것 같다. -
이전에 c를 통해서 구현했을땐 각각의 기능을 직접 구조체로 작성해서 공부 했었는데, 파이썬 에서 구현 할때도 마찬가지로 함수를 만들어서 구현할 수 있고, 큐 에서도 사용하는 deque 리스트를 활용해서 구현할 수 있다.
-
공부 참고자료:
코드
백준 10828 풀이
#https://www.acmicpc.net/problem/10828
#스택
#10828
import sys
input = sys.stdin.readline
n_list = []
n = int(input())
for i in range(n):
a = input().split()
# print(a)
if a[0] =='top':
# n_list.top()
if len(n_list) == 0:
print(-1)
else:
print(n_list[-1])
elif a[0] =='size':
# n_list.size()
print(len(n_list))
elif a[0] =='pop':
# n_list.pop()
if len(n_list) == 0:
print(-1)
else:
print(n_list.pop())
elif a[0] =='empty':
# n_list.empty()
if len(n_list) == 0:
print(1)
else:
print(0)
#push()
else:
n_list.append(a[1])
# print(n_list)클래스를 활용한 파이썬 스택구현
## Stack Class
class stack:
def __init__(self): # 스택 객체 생성
self.items = []
def push(self, item): # 스택 요소 추가 push(.append())
self.items.append(item)
def pop(self): # 스택 맨 뒤 요소 삭제하고 리턴 pop()
return self.items.pop()
def peek(self): # 스택 맨 뒤 요소 리턴
return self.items[-1]
def isEmpty(self): # 스택이 비었는지 확인(비었으면 True 리턴)
return not self.items
stk = stack() # stack 객체 생성
print(stk) # stack object 생성 확인
print(stk.isEmpty()) # 처음에는 아무것도 들어있지 않으므로 True 출력
stk.push(7) # stk 에 7 넣음 : [7]
stk.push(8) # stk 에 8 넣음 : [7,8]
stk.push(9) # stk 에 9 넣음 : [7,8,9]
print(stk.items) #= > [7, 8, 9]
print(stk.pop()) # stk 맨 마지막 값을 꺼내온다. 9를 꺼냈으니 출력 : 9
print(stk.items) # [7, 8] 꺼내지고 남은 값들
print(stk.peek()) # stk 맨 마지막 값을 꺼내지 않고 출력만한다 출력 : 8
print(stk.items) # [7, 8] 아무 값도 사라지지 않은걸 알 수 있다
print(stk.pop()) # stk 마지막 값 8 꺼내지면서 출력 : 8
print(stk.pop()) # stk 마지막 값 7 꺼내지면서 출력 : 7
print(stk.isEmpty()) # 객체에 아무것도 들어있지 않으므로 True 출력
print(stk.items) # 비어 있으므로 [] 출력
해보자! 게임 클라 개발자!