[BOJ] 백준 10845 큐

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

Approach

Queue를 구현하는 문제이다.

[큐] Queue란?

- push X: 정수 X를 큐에 넣는 연산이다.

- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수 출력.

           만약 큐에 들어있는 정수가 없는 경우 -1 출력.

- size: 큐에 들어있는 정수 개수 출력.

- empty: 큐가 비어있으면 1, 아니면 0 출력.

- front: 큐의 가장 앞에 있는 정수 출력.

            만약 큐에 들어있는 정수가 없는 경우, -1 출력.

- back: 큐의 가장 뒤에 있는 정수를 출력.

            만약 큐에 들어있는 정수가 없는 경우, -1 출력.

 

덱(deque)을 사용해서 풀 수 있는 문제이지만

큐(Queue)를 사용하여 풀었습니다.

▶ [C++] [STL] Queue 

[C++] [STL] Queue

 

덱deque의 경우에는 back 명령어로 쉽게 처리할 수 있다.

제출 코드에서는 가장 뒤에 있는 원소들을 전부 꺼내서 다시 큐에 넣어준다.

이렇게 하면 가장 뒤에 있던 원소가 가장 앞에 위치하게 되면서 그 값을 출력.

출력후에는 원상태로 처리하기 위해 가장 앞에 있는 원소를 다시 push 하여 가장 뒤에 있게 해준다.

원형 큐 형태와 유사하다고 보면된다.

 

▶ [큐] 원형 큐 (Circular Queue) 

[큐] 원형 큐 (Circular Queue)

---

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int main(void)
{
	// freopen("input.txt", "r", stdin);
	int N, val;
	scanf("%d", &N);
	queue<int> que;

	for (int i = 0; i < N; i++)
	{

		string cmd;
		cin >> cmd;

		if (cmd == "push")
		{
			scanf("%d", &val);
			que.push(val);
		}
		else if (cmd == "pop")
		{
			if (!que.empty())
			{
				printf("%d\n", que.front());
				que.pop();
			}
			else
			{
				printf("-1\n");
			}
		}

		else if (cmd == "size")
		{
			printf("%d\n", que.size());
		}
		else if (cmd == "empty")
		{
			printf("%d\n", que.empty());
		}
		else if (cmd == "front")
		{
			if (!que.empty())
			{
				printf("%d\n", que.front());
			}
			else
			{
				printf("-1\n");
			}
		}
		else if (cmd == "back")
		{
			if (!que.empty())
			{
				int cnt = que.size();
				// 마지막 원소를 가장 앞쪽으로 조절
				for (int j = 0; j < cnt - 1; j++)
				{
					val = que.front();
					que.pop();
					que.push(val);
				}
				// 가장 앞으로 온 원소를 다시 Queue에 넣어 원래 상태로 복원
				val = que.front();
				que.pop();
				que.push(val);
				printf("%d\n", val);
			}
			else
			{
				printf("-1\n");
			}
		}
	}
}

 

Java

import java.util.Scanner;

class Queue {
	int front, rear;
	int[] queue;
	
	public Queue(int size) {
		front = 0;
		rear = 0;
		queue = new int[size];
	}

	public void push(int value) {
		queue[rear++] = value;
	}

	public int pop() {
		int result = -1;
		if(front == rear){
			return result;
		}else{
			result = queue[front++];
		}
		return result;
	}
	public int queue_size(){
		return (rear-front);
	}
	public int empty(){
		int result = 0;
		if(front == rear){
			result = 1;
		}
		return result;
	}
	public int front(){
		int result = -1;
		if(this.front == rear){
			return result;
		}else{
			result = queue[front];
		}
		return result;
	}
	public int back(){
		int result = -1;
		if(this.rear == front){
			return result;
		}else{
			result = queue[rear-1];
		}
		return result;
	}
	public void print_queue(){
		for(int i=front; i<rear; i++){
			System.out.println(queue[i]);
		}
	}
}
public class Main {
	public static void main(String[] args) {
		Queue Q = new Queue(10000);
		Queue result = new Queue(10000);
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		for(int i=0; i<n; i++){
			String str = sc.nextLine();
			String []value = str.split(" "); 
			// StringTokenizer과의 차이는 공백도 하나의 인자로 칠 수 있는데
			// 여기서는 공백으로 구분하기 의미가 모호 (ex. ',' 로 구분할 때 )
			if(value[0].equals("push")){
				int number = Integer.parseInt(value[1]);
				Q.push(number);
			}
			else if(value[0].equals("pop")){
				result.push(Q.pop());
			}
			else if(value[0].equals("front")){
				result.push(Q.front());
			}
			else if(value[0].equals("back")){
				result.push(Q.back());
			}
			else if(value[0].equals("size")){
				result.push(Q.queue_size());
			}
			else if(value[0].equals("empty")){
				result.push(Q.empty());
			}
		}
		result.print_queue();


	}
}