Introduction

stack은 후입선출, queue는 선입선출 자료구조입니다. 그러면 둘을 합친건 없을까요? 바로 둘을 합친 덱(deque)이라는 자료구조를 백준 문제를 풀이하며 설명하겠습니다.

deque

덱(deque)은 double-ended-queue의 줄임말입니다. 즉 양쪽으로 큐의 기능을 하는 자료구조로, 그러다보니 양 끝에서 데이터를 넣고 빼는게 가능합니다. 자연스럽게 스택의 기능까지 도맡아서 하기에 사실상 스택이든 큐든 덱 자료구조 하나만으로 가능합니다.

큐와 같이 덱 역시 두 개의 포인터를 가지며, 연결 리스트로 구현을 하는 형태입니다. 백준 문제를 풀어보면서 덱의 기능에 대해 알아보겠습니다.

구현 및 풀이

해당 백준 문제는 10866번 덱 입니다. 여기에 구현해야 되는 덱에 대한 설명이 나와있습니다.
https://www.acmicpc.net/problem/10866

구현 목록

문제 및 구현해야되는 덱의 기능들은 아래와 같습니다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

기본적으로 큐를 두개 합쳐놓은듯한 기능들을 확인할 수 있습니다.

구현(Before Main)

자료구조가 되는 부분입니다.

class Node {
	int data;
	Node prev;
	Node next;
	
	Node(int data) {
		this.data = data;
		this.prev = null;
		this.next = null;
	}
}

class MyDeque {
	private int size = 0;
	private Node front = null;
	private Node back = null;
	
	public void pushFront(int x) {
		Node node = new Node(x);
		
		if(size == 0) {
			front = node;
			back = node;
			size++;
			return;
		}
		
		node.next = front;
		front.prev = node;
		front = node;
		size++;
	}
	
	public void pushBack(int x) {
		Node node = new Node(x);
		
		if(size == 0) {
			front = node;
			back = node;
			size++;
			return;
		}
		
		node.prev = back;
		back.next = node;
		back = node;
		size++;
	}
	
	public int popFront() {
		if(size == 0) {
			return -1;
		}
		
		Node node = front;
		front = node.next;
		size--;
		return node.data;
	}
	
	public int popBack() {
		if(size == 0) {
			return -1;
		}
		
		Node node = back;
		back = node.prev;
		size--;
		return node.data;
	}
	
	public int size() {
		return size;
	}
	
	public int empty() {
		return (size == 0) ? 1 : 0;
	}
	
	public int front() {
		if(size == 0) {
			return -1;
		}
		return front.data;
	}
	
	public int back() {
		if(size == 0) {
			return -1;
		}
		return back.data;
	}
}

Main

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringBuilder sb = new StringBuilder();
        MyDeque deque = new MyDeque();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
        	String[] command = br.readLine().split(" ");
        	switch(command[0]) {
        	case "push_front":
        		deque.pushFront(Integer.parseInt(command[1]));
        		break;
        	case "push_back":
        		deque.pushBack(Integer.parseInt(command[1]));
        		break;
        	case "pop_front":
        		sb.append(deque.popFront()).append("\n");
        		break;
        	case "pop_back":
        		sb.append(deque.popBack()).append("\n");
        		break;
        	case "size":
        		sb.append(deque.size()).append("\n");
        		break;
        	case "empty":
        		sb.append(deque.empty()).append("\n");
        		break;
        	case "front":
        		sb.append(deque.front()).append("\n");
        		break;
        	case "back":
        		sb.append(deque.back()).append("\n");
        		break;
        	}
        }
        System.out.print(sb.toString());
        
        br.close();
    }
}