[BOJ] 백준 10866 덱

Approach

출처: https://www.acmicpc.net/problem/10866

 

deque를 구현하는 문제이다.

덱은 stack, queue와 마찬가지로 자료구조 공부하는데 있어서

자주 나오는 자료구조이다.

 

앞/뒤로 push/pop이 되는 구조로

C++에서는 STL로 제공되기 때문에

비교적으로 쉽게 해결할 수 있는 문제이다.

* 앞뒤 방향과 비어있는 상태에 따른 출력처리에 유의

 

📌 [스택] Stack 이란?

[스택] Stack 이란?

 

📌 [큐] Queue란?

[큐] Queue란?

 

C++

#include <iostream>
#include <deque>
#include <string>
using namespace std;

deque<int> dQ;
string str;
int N, val;

int main() 
{
	// freopen("input.txt", "r", stdin);

	cin >> N;
	while (N--) 
	{
		cin >> str;
		if (str == "push_front")
		{
			cin >> val;
			dQ.push_front(val);
		}

		else if (str == "push_back")
		{
			cin >> val;
			dQ.push_back(val);
		}

		else if (str == "pop_front")
		{
			if (dQ.empty())
			{
				printf("%d\n", -1);
			}
			else 
			{
				printf("%d\n", dQ.front());
				dQ.pop_front();
			}
		}

		else if (str == "pop_back") 
		{
			if (dQ.empty())
			{
				printf("%d\n", -1);
			}
			else
			{
				printf("%d\n", dQ.back());
				dQ.pop_back();
			}
		}

		else if (str == "size")
		{
			printf("%d\n", dQ.size());
		}

		else if (str == "empty")
		{
			printf("%d\n", dQ.empty() ? 1 : 0);
		}

		else if (str == "front")
		{
			printf("%d\n", dQ.empty()  ? -1 : dQ.front());
		}

		else if (str == "back")
		{
			printf("%d\n", dQ.empty() ? -1 : dQ.back());
		}
	}
}

 

 

import java.util.Scanner;

class Node {
	int data;
	Node llink;
	Node rlink;

	public Node(int data) {
		this.data = data;
		this.llink = null;
		this.rlink = null;
	}
}

class Deque {
	Node front;
	Node rear;

	public Deque() {
		this.front = null;
		this.rear = null;
	}

	public void push_front(int data) {
		Node node = new Node(data);
		if (is_empty() == 1) {
			front = node;
			rear = node;
		}
		else {
			front.llink = node;
			node.rlink = front;
			front = node;
		}
	}
	public void push_rear(int data) {
		Node node = new Node(data);
		if (is_empty() == 1) {
			front = node;
			rear = node;
		}
		else {
			rear.rlink = node;
			node.llink = rear;
			rear = node;
		}
	}
	public int pop_front() {
		if (front == null)
			return -1;
		int result = front.data;
		front = front.rlink;
		if (front != null)
			front.llink = null; // 연결 끊기  
		else // 삭제해서 비어버린 경우이므로 rear도 null
			rear = null;

		return result;
	}
	public int pop_rear() {
		if (rear == null)
			return -1;
		int result = rear.data;
		rear = rear.llink;
		if (rear != null)
			rear.rlink = null; // 연결 끊기
		else { // 삭제해서 비어버린 경우이므로 front도 null
			front = null;
		}

		return result;
	}
	public int deque_size() {
		int count = 0;
		if (is_empty() == 1)
			return 0;
		Node search = front;
		while (true) {
			if (search == null)
				break;
			search = search.rlink;
			count++;
		}
		return count;
	}

	public int is_empty() {
		if (front == null && rear == null)
			return 1;
		return 0;
	}

	public int front_value() {
		if (front == null) {
			return -1;
		}
		return front.data;
	}

	public int rear_value() {
		if (rear == null) {
			return -1;
		}
		return rear.data;
	}
}


public class Main {

	public static void main(String[] args) {
		Deque DQ = new Deque();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int idx = 0;
		int result[] = new int[n];
		sc.nextLine();
		for (int i = 0; i < n; i++) {
			String str = sc.nextLine();
			String[]value = str.split(" ");
			
			// StringTokenizer과의 차이는 공백도 하나의 인자로 칠 수 있는데
			// 여기서는 공백으로 구분하기 의미가 모호 (ex. ',' 로 구분할 때)
			if (value[0].equals("push_back")) {
				int number = Integer.parseInt(value[1]);
				DQ.push_rear(number);
			}
			else if (value[0].equals("push_front")) {
				int number = Integer.parseInt(value[1]);
				DQ.push_front(number);
			}
			else if (value[0].equals("pop_front")) {
				result[idx++] = DQ.pop_front();
			}
			else if (value[0].equals("pop_back")) {
				result[idx++] = DQ.pop_rear();
			}
			else if (value[0].equals("front")) {
				result[idx++] = DQ.front_value();
			}
			else if (value[0].equals("back")) {
				result[idx++] = DQ.rear_value();
			}
			else if (value[0].equals("size")) {
				result[idx++] = DQ.deque_size();
			}
			else if (value[0].equals("empty")) {
				result[idx++] = DQ.is_empty();
			}
		}

		for (int i = 0; i < idx; i++) {
			System.out.println(result[i]);
		}

	}
}