[Algorithm] 큐(Queue)

1. 개요

큐(Queue)는 한쪽 끝에서 자료를 넣고, 다른 한쪽 끝에서 뺄 수 있는 자료구조이다. 먼저 넣은 값이 가장 먼저 나오기 떄문에 First In First Out(FIFO) 구조라고 하며, push, pop, front, back, size, empty 6개의 명령이 존재한다. 예제를 통해 큐(Queue)의 동작 방식에 대해 알아보도록 하자.

• push {값} : 큐의 맨 뒤에 값을 넣음

• pop : 큐의 맨 앞의 값을 뺌

• front : 큐의 맨 앞의 값을 반환

• back : 큐의 맨 뒤의 값을 반환

• size : 큐의 크기 반환

• empty : 큐가 비어있는지 여부 반환(비어있으면 true, 비어있지 않으면 false)

2. 예제

1. 명령 : empty / 반환값 : true

   큐가 비어있으므로 true를 반환한다.

   

2. 명령 : push 2 / 반환값 : X

   큐의 빈 공간 중 가장 위에 2를 넣는다.

   

3. 명령 : push 5 / 반환값 : X

   큐의 빈 공간 중 가장 위에 5를 넣는다.

   

4. 명령 : push 7 / 반환값 : X

   큐의 빈 공간 중 가장 위에 7을 넣는다.

   

5. 명령 : front / 반환값 : 2

   큐의 맨 아래 값인 2를 반환한다.

   

6. 명령 : pop / 반환값 : X

   큐의 맨 아래 값인 2를 뺀다.

   

7. 명령 : back / 반환값 : 7

   큐의 맨 위의 값인 7을 반환한다.

   

8. 명령 : size / 반환값 : 2

   큐에 들어있는 값의 크기(갯수)를 반환한다.

   

9. 명령 : empty / 반환값 : false

   큐가 비어있지 않으므로 false를 반환한다.

   

3. 구현 코드

3-1. C++

3-1-1. 구현

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/queue.cpp

#include <iostream>
#include <vector>

using namespace std;

vector<int> v(10003);

int main(void) {
    ios_base::sync_with_stdio(false);
    int begin = 0, end = 0;
    int n; for (cin >> n; n--;) {
        string cmd; cin >> cmd;
        if (cmd == "push") {
            int num; cin >> num;
            v[end++] = num;
        }
        else if (cmd == "pop") {
            if (begin == end) {
                cout << "-1" << "\n";
            }
            else {
                cout << v[begin] << "\n";
                v[begin++] = 0;
            }
        }
        else if (cmd == "size") {
            cout << end - begin << "\n";
        }
        else if (cmd == "empty") {
            cout << (begin == end ? 1 : 0) << "\n";
        }
        else if (cmd == "front") {
            cout << (begin == end ? -1 : v[begin]) << "\n";
        }
        else if (cmd == "back") {
            cout << (begin == end ? -1 : v[end - 1]) << "\n";
        }
    }
    return 0;
}

[실행 결과]

3-1-2. 라이브러리 이용

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/queue2.cpp

#include <iostream>
#include <queue>

using namespace std;

queue<int> q;

int main(void) {
	ios_base::sync_with_stdio(false);
	int n; for (cin >> n; n--;) {
		string cmd; cin >> cmd;
		if (cmd == "push") {
			int num; cin >> num;
			q.push(num);
		} else if (cmd == "pop") {
			if (q.empty()) {
				cout << "-1\n";
			} else {
				cout << q.front() << "\n";
				q.pop();
			}
		} else if (cmd == "size") {
			cout << q.size() << "\n";
		} else if (cmd == "empty") {
			cout << q.empty() << "\n";
		} else if (cmd == "front") {
			if (q.empty()) cout << "-1\n";
			else cout << q.front() << "\n";
		} else if (cmd == "back") {
			if (q.empty()) cout << "-1\n";
			else cout << q.back() << "\n";
		}
	}
	return 0;
}

[실행 결과]

3-2. JAVA

3-2-1. 구현

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/queue.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class QueueExample {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int arr[] = new int[10003];
        int begin = 0, end = 0;
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; ++i) {
            String cmd = br.readLine();
            StringTokenizer st = new StringTokenizer(cmd);
            if(st.nextToken().equals("push")) {
                int num = Integer.parseInt(st.nextToken());
                arr[end++] = num;
            } else if(cmd.equals("pop")) {
                if(begin == end) {
                    sb.append("-1").append("\n");
                } else {
                    sb.append(arr[begin]).append("\n");
                    arr[begin++] = 0;
                }
            } else if(cmd.equals("size")) {
                sb.append(end - begin).append("\n");
            } else if(cmd.equals("empty")) {
                sb.append(begin == end ? 1 : 0).append("\n");
            } else if(cmd.equals("front")) {
                sb.append(begin == end ? -1 : arr[begin]).append("\n");
            } else if(cmd.equals("back")) {
                sb.append(begin == end ? -1 : arr[end - 1]).append("\n");
            }
        }
        System.out.println(sb);
    }
}

[실행 결과]

3-2-2. 라이브러리 이용

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/queue2.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Queue<Integer> q = new LinkedList<>();
        int n = Integer.parseInt(br.readLine());
        int num = 0;
        for(int i = 0; i < n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            if(cmd.equals("push")) {
                num = Integer.parseInt(st.nextToken());
                q.offer(num);
            } else if(cmd.equals("pop")) {
                if(q.isEmpty()) sb.append("-1\n");
                else sb.append(q.poll()).append("\n");
            } else if(cmd.equals("size")) {
                sb.append(q.size()).append("\n");
            } else if(cmd.equals("empty")) {
                sb.append(q.isEmpty() ? 1 : 0).append("\n");
            } else if(cmd.equals("front")) {
                if(q.isEmpty()) sb.append("-1\n");
                else sb.append(q.peek()).append("\n");
            } else if(cmd.equals("back")) {
                if(q.isEmpty()) sb.append("-1\n");
                else sb.append(num).append("\n");
            }
        }
        System.out.println(sb);
    }
}

[실행 결과]