🚶‍♂️Road to 코테(4) - 스택

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬 편

스택

한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조.
구조적으로 먼저 들어간 원소가 제일 나중에 나오는데 이를 FILO(First In Last Out) 자료구조라고 한다.
큐나 덱도 특정 위치에서만 원소를 넣거나 빼기 때문에 세 개를 묶어서 Restricted Structur라고 부르기도 한다.

성질

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 상단의 원소 확인이 O(1)
  배열의 끝에서 원소를 추가 및 제거하는 것과 똑같다.
• 제일 상단이 아닌 나머지 원소들의 확인 및 변경이 원칙적 불가능.
  나머지 원소들에 대한 기능은 스택에서 제공하지 않는다.
  

구현

• 배열 혹은 연결리스트를 이용해 구현할 수 있고 배열이 더 쉽다.

stack=[]
MAX_SIZE=10
pos=0

def top(stack):
  return stack[pos-1]

def  isFull(stack):
  return len(stack)==MAX_SIZE

def isEmpty(stack):
  return len(stack)==0

def push(stack,item):
  if isFull(stack):
    print("스택이 가득 찼습니다.")
  else:
    stack.append(item)
    print("데이터 추가")

def pop(stack):
  if isEmpty(stack):
    print('스택이 비어있습니다.')
    return None
  else:
    print(f'{top(stack)}이 나가집니다.')
    return stack.pop()
  
  

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼냄
top_element = stack.pop( ) 
next_element = stack.pop( ) 

# 스택의 크기를 구함
stack_size = len(stack)
print(stack)

사실 굳이 push,pop 구현 안하고 append,pop써도 되긴 한다.

연습문제 - 백준 10828

import sys

stack=[]

def top(stack):
  if len(stack) == 0:
    return print(-1)
  else:
    return print(stack[-1]) 


def empty(stack):
  if len(stack)==0:
    return print(1)
  else:
    return print(0)

def push(stack,item):
  stack.append(item)

def size(stack):
  return print(len(stack))

def pop(stack):
  if len(stack) == 0:
    return print(-1)
  else:
    return print(stack.pop())

N=int(sys.stdin.readline())
for _  in range(N):
    a=sys.stdin.readline().split()
    if a[0]=='push':
      push(stack,a[1])
    elif a[0]=='pop':
      pop(stack)
    elif a[0]=='size':
      size(stack)
    elif a[0]=='empty':
      empty(stack)
    elif a[0]=='top':
      top(stack)

자꾸 하나씩 빼먹어서 런타임에러가 뜨니 주의하자