알고리즘&자료구조/Data Structure

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

백엔드 개발자 - 젤리곰 2024. 2. 17. 12:47
728x90

1. 문제

 

10828번: 스택

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

www.acmicpc.net

 

 

10845번: 큐

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

www.acmicpc.net

 

 

10866번: 덱

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

www.acmicpc.net

⭐포인트

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

 

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)

 

728x90