Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

19. 큐, 덱

큐와 덱을 구현하고 사용해 봅시다.

Java / Python

5. 덱

10866번

덱의 개념을 익히고 실습하는 문제. (입력 크기가 너무 작아서 비효율적인 구현으로도 통과가 되지만, 가급적이면 연산 당 시간 복잡도가 O(1)이도록 구현해 주세요.)

이번 문제는 덱을 구현하는 문제입니다. 덱(deque, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태입니다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있으며, 큐와 스택을 합친 형태로 생각할 수 있습니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;
 
public class Main {
	public static void main(String[] args) throws IOException {
        
		ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
 
		int N = Integer.parseInt(br.readLine());
 
		for (int i = 0; i < N; i++) {
 
			String[] s = br.readLine().split(" ");
 
			switch (s[0]) {
 
				case "push_front": {
					deque.addFirst(Integer.parseInt(s[1]));
					break;
				}
				
				case "push_back": {
					deque.addLast(Integer.parseInt(s[1]));
					break;
				}
 
				case "pop_front": {
					if (deque.isEmpty()) {
						sb.append(-1).append('\n');
					} 
					else {
						sb.append(deque.pollFirst()).append('\n');
					}
					break;
				}
 
				case "pop_back": {
					if (deque.isEmpty()) {
						sb.append(-1).append('\n');
					} 
					else {
						sb.append(deque.pollLast()).append('\n');
					}
					break;
				}
 
				case "size": {
					sb.append(deque.size()).append('\n');
					break;
				}
 
				case "empty": {
					if (deque.isEmpty()) {
						sb.append(1).append('\n');
					} 
					else {
						sb.append(0).append('\n');
					}
					break;
				}
 
				case "front": {
					if (deque.isEmpty()) {
						sb.append(-1).append('\n');
					} 
					else {
						sb.append(deque.peekFirst()).append('\n');
					}
					break;
				}
 
				case "back": {
					if (deque.isEmpty()) {
						sb.append(-1).append('\n');
					} 
					else {
						sb.append(deque.peekLast()).append('\n');
					}
					break;
				}
			}
		}
		System.out.println(sb);
	}
}

• Python

import sys
from collections import deque

N = int(sys.stdin.readline())

dq = deque()

def size():
    return len(dq)

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

for _ in range(N):
    s = list(sys.stdin.readline().split())
    
    if s[0] == 'push_front':
        dq.appendleft(s[1])
    elif s[0] == 'push_back':
        dq.append(s[1])
    elif s[0] == 'pop_front':
        if empty() == 1:
            print("-1")
        else:
            tmp = dq.popleft()
            print(tmp)
    elif s[0] == 'pop_back':
        if empty() == 1:
            print("-1")
        else:
            tmp = dq.pop()
            print(tmp)
    elif s[0] == 'front':
        if empty() == 1:
            print("-1")
        else:
            print(dq[0])
    elif s[0] == 'back':
        if empty() == 1:
            print("-1")
        else:
            print(dq[len(dq)-1])
    elif s[0] == 'size':
        print(size())
    elif s[0] == 'empty':
        print(empty())