[백준 10828, 10845, 10866] 스택·큐·덱

1. 문제

10828번: 스택

 

10845번: 큐

 

10866번: 덱

⭐포인트

스택, 큐, 덱 자료구조에 기본 개념을 학습하기 위한 문제다.

 

2. 개념 이해

1️⃣스택(stack)

마지막에 쌓아 올린 자료를 먼저 꺼내므로 후입선출(Last In First Out) 구조라 한다.

파이썬에서는 리스트를 이용하여 스택 자료구조를 구현할 수 있다. 

"""스택"""
N = int(input())
command = []
output = []
for _ in range(N):
    command.append(list(map(str,input().split())))


for cm in command:
    if cm[0] == 'push':
        output.append(cm[1])
    elif cm[0] == 'top':
        if output:
            print(output[-1])
        else:
            print(-1)
    elif cm[0] == 'pop':
        if output:
            print(output.pop())
        else:
            print(-1)
    elif cm[0] == 'size':
        print(len(output))
    elif cm[0] == 'empty':
        print(1 if not output else 0) # <참일 때의 값> if <조건> else <거짓일 때의 값>

 

 

2️⃣큐(Queue)

큐 자료구조는 선입선출! First In First Out 구조다.

파이썬에서는 queue 모듈을 활용할 수 있다.

Queue()로 FIFO 큐를 생성한다.

메서드명	설명
put()	요소 추가
get()	요소 제거 및 반환
qsize()	큐의 현재 요소 수 반환
empty()	큐가 비어있으면 True를 반환
full()	큐가 꽉 차 있으면 True를 반환
join()	큐의 모든 작업이 완료될 때까지 기다린다.

 

"""큐"""
import queue
N = int(input())

q = queue.Queue()

ini_list = []

for _ in range(N):
    ini_list.append(list(map(str,input().split())))

for ini in ini_list:
    if ini[0] == 'push':
        q.put(int(ini[1]))
    elif ini[0] == 'pop':
        if q.qsize() > 0:
            print(q.get())
        else:
            print(-1)
    elif ini[0] == 'size':
        print(q.qsize())
    elif ini[0] == 'empty':
        print(0 if q.qsize() > 0 else 1)
    elif ini[0] == 'front':
        if q.qsize() > 0:
            print(q.queue[0])
        else:
            print(-1)
    elif ini[0] == 'back':
        if q.qsize() > 0:
            print(q.queue[-1])
        else:
            print(-1)

 

3️⃣덱(deque)

 

deque는 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형으로, 스택(stack)처럼 써도 되고 큐(queue)처럼 써도 된다.

메서드명	설명
append(x)	오른쪽 끝에 새로운 아이템 x를 추가
appendleft(x)	왼쪽 끝에 새로운 아이템 x를 추가
clear()	모든 아이템을 제거
count(x)	x 값과 동일한 아이템의 개수를 반환
extend(iterable)	오른쪽 끝에 여러 아이템을 한 번에 추가할 때 사용.
extendleft(iterable)	왼쪽 끝에 여러 아이템을 한 번에 추가할 때 사용.
index(x, start, stop)	x 값을 찾아 첫 번째로 나타나는 위치의 인덱스를 반환 start, stop으로 범위 지정.
insert(i, x)	i번째 위치에 x를 삽입
pop()	오른쪽 끝에서 아이템을 하나 제거하고, 그 아이템을 반환
popleft()	왼쪽 끝에서 아이템을 하나 제거하고, 그 아이템을 반환
remove(x)	value 값을 가진 첫 번째 아이템을 제거
reverse()	역순 정렬
rotate(n=1)	모든 아이템을 n만큼 오른쪽으로 회전

 

"""덱"""
from collections import deque

dq = deque()

N = int(input())

ini_list = []

for _ in range(N):
    ini_list.append(list(map(str,input().split())))

for ini in ini_list:
    if ini[0] == 'push_front':
        dq.appendleft(ini[1])
    elif ini[0] == 'push_back':
        dq.append(ini[1])
    elif ini[0] == 'pop_front':
        if len(dq) != 0:
            print(dq.popleft())
        else:
            print(-1)
    elif ini[0] == 'pop_back':
        if len(dq) != 0:
            print(dq.pop())
        else:
            print(-1)
    elif ini[0] == 'size':
        print(len(dq))
    elif ini[0] == 'empty':
        print(1 if len(dq) == 0 else 0)
    elif ini[0] == 'front':
        if len(dq) != 0:
            print(dq[0])
        else:
            print(-1)
    elif ini[0] == 'back':
        if len(dq) != 0:
            print(dq[-1])
        else:
            print(-1)