[자료구조] 파이썬 Stack

Stack이란

Last In Frist Out(LIFO) 방식: 가장 나중에 넣은 데이터가 가장 먼저 빼낼 수 있는 데이터구조
python에서는 list로 구현이 되어있다.

list사용법

a_list.append(1): 요소를 리스트 맨 뒤에 넣는다.

a_list = [1,2,3]
a_list.append(1)
=> [1,2,3,1]

a_list.pop(): 리스트의 맨 뒤의 요소를 꺼내고 리스트에서 삭제한다.

a_list = [1,2,3]
a_list.pop()
=> [1,2]

Stack구현

class Stack:
    #리스트를 이용한 스택 구현
    def __init__(self):
        self.top = []
    #스택 크기 반환
    def __len__(self) -> bool :
        return len(self.top)

    #구현함수
    #스택에 원소 삽입
    def push(self, item):
        self.top.append(item)
    #스택 가장 위에 있는 원소를 삭제하고 반환   
    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)
        else:
            print("Stack underflow")
            exit()
    #스택 가장 위에 있는 원소를 반환
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]
        else:
            print("underflow")
            exit()
    #스택이 비어있는 지를 bool값으로 반환
    def isEmpty(self) -> bool :
        return len(self.top)==0

Stack 라이브러리

파이썬 내장모듈에서는 따로 스택 라이브러리가 존재하지 않기에 보통 덱 라이브러리를 import해서 스택 대신으로 사용하는 경우도 있다.

from collections import deque

dq=deque() # 덱 생성
dq.append() # 덱의 가장 오른쪽에 원소 삽입
dq.popleft() # 가장 왼쪽 원소 반환
dq.appendleft() # 덱의 가장 왼쪽에 원소 삽입
dp.pop() # 가장 오른쪽 원소 반환
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) #x와 같은 원소의 개수를 계산
'''공식문서 : https://docs.python.org/3.8/library/collections.html#collections.deque'''

Stack 문제

https://www.acmicpc.net/problem/10828

[10828번: 스택

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net](https://www.acmicpc.net/problem/10828)

스택 기본문제로

stack 기본문제

문제는 다음과같다

기본 스택을 구현해 보는 문제로 나의 풀이는 다음과 같다

import sys
n = int(sys.stdin.readline())

stack = [];
for i in range(n):
  command = sys.stdin.readline().split()
  if(command[0] == 'push'):
    stack.append(int(command[1]))
  if(command[0]=='pop'):
    if(len(stack) == 0):
      print(-1)
    else:
      print(stack.pop())
  if(command[0]=='size'):
    print(len(stack))
  if(command[0]=='empty'):
    print(1 if len(stack)==0 else 0)
  if(command[0]=='top'):
    if(len(stack) == 0):
      print(-1)
    else:
      print(stack[-1])

참고

https://velog.io/@yeseolee/Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack