자료구조 ③ 스택과 큐 (+ 백준 10828, 10845)

스택

• 가장 마지막에 삽입된 data가 가장 먼저 나오는 구조
  • 후입선출 구조 : Last in, First out
  • 삽입과 삭제가 한쪽에서만 일어난다
    • 재귀함수 알고리즘 원리와 일맥상통
    • 삽입 및 삭제 위치 : top
• 연산
  • append : 데이터 삽입
  • pop : 데이터를 삭제하고 삭제되는 데이터 출력
  • s[-1] : top 위치에 있는 데이터를 단순 확인
• 깊이 우선 탐색 DFS, 백트래킹 종류의 코딩 테스트에 효과적
• 백준 10828번 풀이(python)

• 프로세스
  • 명령 개수 입력 받기 : input 재정의할 것
  • 리스트로 스택 구현
  • 반복문을 통해 명령 입력 받기
    • 입력받은 명령을 명령과 데이터로 분할하기
    • 명령에 따라서 데이터 처리하기
• 숫자 출력 시 print를 사용하지 않으면 오답으로 처리된다
• 코드

import sys #백준 10828번
N = int(sys.stdin.readline()) #명령 개수
stack = list() #stack은 선입선출

for i in range(N):
    commend = sys.stdin.readline().split() #명령 받기
    if commend[0] == 'push': 
        stack.append(commend[1]) #데이터 추가

    elif commend[0] == 'pop': 
        print(-1) if len(stack) == 0 else print(stack.pop())

    elif commend[0] == 'size': # 스택에 있는 정수 개수
        print(len(stack))

    elif commend[0] == 'empty':
        print(1) if len(stack) == 0 else print(0)

    elif commend[0] == 'top': #print 미 사용 시 오답 처리가 된다
        print(-1) if len(stack) == 0 else print(stack[-1])

큐

• 먼저 삽입된 data가 가장 먼저 나오는 구조
  • 선입선출 구조 : First in, First out
  • 삽입과 삭제가 양방향에서 일어난다
    • 추가 : 큐의 rear에서 이뤄진다
    • 삭제 : 큐의 front에서 이뤄진다
• 파이썬에서는 주로 deque로 구현한다
  • list로도 구현이 가능하지만, deque의 시간복잡도가 list의 시간복잡도보다 낮다
  • deque는 큐의 스택의 특성을 모두 가지는 자료구조로, 양쪽에서 삽입 및 삭제가 가능하다
• 연산
  • append : 데이터 삽입
  • popleft : front 의 데이터를 삭제하고 삭제되는 데이터를 출력한다
  • s[0] : front 위치에 있는 데이터를 단순 확인할 때 사용한다.
• 너비 우선 탐색 BFS에서 자주 사용한다
• 우선순위 큐
  • 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
  • 삽입 : put
  • 삭제 : get
  • 우선순위 : 기본적으로는 값을 기준으로 한다
    • 우선순위 기준을 변경하기 위해서는 put((우선순위1, 우선순위2…)) 순으로 입력해야 한다.
• 백준 10845번 풀이(python)

• 프로세스
  • 명령 개수 입력 받기 : input 재정의할 것
  • deque로 큐 구현
  •  반복문을 통해 명령 입력받기
    • 입력받은 명령을 명령과 데이터로 분할하기
    • 명령에 따라서 데이터 처리하기
• 숫자 출력 시 print를 사용하지 않으면 오답으로 처리된다
• 코드

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
mydeq = deque()

for _ in range(N):
    commend = input().split() #명령받기
    if commend[0] == 'push':
        mydeq.append(commend[1])

    elif commend[0] == 'front':
        if len(mydeq) == 0:
            print(-1)
        else:
            print(mydeq[0]) #가장 앞에 있는 정수 출력

    elif commend[0] == 'back':
        if len(mydeq) == 0:
            print(-1)
        else:
            print(mydeq[-1]) #가장 뒤에 있는 정수 출력

    elif commend[0] == 'size':
        print(len(mydeq))

    elif commend[0] == 'empty':
        if len(mydeq) == 0:
            print(1)
        else:
            print(0)

    elif commend[0] == 'pop':
        if len(mydeq) == 0:
            print(-1)
        else:
            print(mydeq.popleft())