[백준 18258번] 큐 2

🔗알고리즘 문제

단순히 Queue 자료구조를 구현하는 문제로 vector를 사용하면 빠르게 풀 수 있지만 STL을 사용하지 않고 풀어보자 하여 배열로 해결한 문제이다. 처음으로 STL을 사용하지 않고 배열로 자료구조를 구현해보아서 꽤나 힘들었던 문제이다,,,

문제 분석

이 문제는 입력으로 주어지는 명령을 처리하는 Queue 자료구조를 구현하는 문제이다.

발상

일반적인 배열에서 인덱스를 활용하여 Queue를 구현할 수 있겠다 라고 생각하였다.

front와 back이라는 각각 현재 Queue의 맨 앞과 맨 뒤 인덱스를 담당하는 변수를 만들어 Queue의 Push 할 때에는 back을 하나 증가시켜주고 Queue에서 Pop 할 때에는 front를 하나 증가시켜주는 방식으로 구현하였다.

push X: array[back] 부분에 입력값을 넣고 back을 증가시키기
pop: array[front] 부분 출력 후 front값 증가, 만약 front == back 이라면 -1 출력
size: back - front 출력하기 ( 현재 queue의 size )
empty: front == back 의 값 출력하기
top: array[front] 부분 출력하기, 만약 front == back이라면 -1 출력하기

알고리즘 설계

1. 입력할 명령의 수를 입력받는다.
2. 명령의 수 만큼 for문을 돌며 명령을 입력받는다.
3. 주어진 명령을 실행한다.

코드

#include<iostream>
#include<string>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    int* queue = new int[1000];
    int front = -1, back = -1;
    int count;
    cin >> count;

    for(int i = 0; i < count; i++){
        string command;
        cin >> command;

        if(command == "push"){
            int n;
            cin >> n;
            queue[++back] = n;
        }
        if(command == "pop" || command == "front"){
            if(front == back) cout << -1 << "\n";
            else{
                cout << queue[front + 1];
                if(command == "pop") front++;
            }
        }
        if(command == "back"){
            if(front == back) cout << -1 << "\n";
            else{
                cout << queue[back] << "\n";
            }
        }
        if(command == "size"){
            cout << back - front << "\n";
        }
        if(command == "empty"){
            cout << (int)(front == back) << "\n";
        }
    }
}