[백준/c++] 10845번 큐

10845번 문제 링크

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

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

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

큐는 총 세가지의 방법으로 구현할 수 있다.
1. STL 사용
2. 배열 사용
3. 연결리스트 사용

자세한 내용은 👉 [알고리즘] Stack과 Queue 참고

소스코드

1. STL 사용

#include <iostream>
#include <queue>
using namespace std;

int main() {
    
    queue<int> q;
    
    int n; 					// 명령의 수 
    cin >> n;
    
    string command;		    // 명령어 
    int x;					// 스택에 넣을 수 
    
    for(int i=0;i<n;i++) {
        cin >> command;
        if (command == "push") {
	        // 정수 X 를 큐에 넣음 
            cin >> x;
            q.push(x);
        } else if (command == "size") {
	        // 큐에 들어있는 정수의 개수를 출력 
            cout << q.size() << endl;
        } else if (command == "empty") {
	        // 큐가 비어있는지 확인 
            cout << q.empty() << endl;
        } else if (q.empty()) {
            // pop, front, back 인 경우 큐가 비어 있으면 -1 을 출력해야 함 
            cout << "-1" << endl;
        } else if (command == "pop") {
	        // front 에 있는 값을 출력해주고 pop 해줌 
            cout << q.front() << endl;
            q.pop();
        } else if (command == "front") {
	        // front 에 있는 값 출력 
            cout << q.front() << endl;
        } else if (command == "back") {
	        // back 에 있는 값 출력 
            cout << q.back() << endl;
        }
    }

    return 0;
}

2. 배열 사용

#include <iostream>
#include <queue>
using namespace std;

struct queue_struct {
  
  int arr[10000];
  int rear = -1, fir = -1; // rear = 데이터가 들어가야할 위치, fir = 꺼내야할 데이터 위치 
  
  void push(int x) {
      if (fir == -1) fir++;
      arr[++rear] = x;
  }
  
  int empty() {
      if (fir > rear || fir == -1) {
          return 1;
      }
      return 0;
  }
  
  int fir_fun() {
      return arr[fir];
  }
  
  int back() {
      return arr[rear];
  }
  
  int pop() {
      if (fir > rear || fir == -1) {
          return -1;
      }
      return arr[fir++];
  }
  
  int size() {
      int size = rear - fir;
      if (size < 0 || rear == -1) {
          // 큐가 비어있을 때 
          return 0;
      } else {
          return size + 1;
      }
  }
  
};

int main() {
    
    queue_struct q;
    
    int n; 					// 명령의 수 
    cin >> n;
    
    string command;		    // 명령어 
    int x;					// 스택에 넣을 수 
    
    for(int i=0;i<n;i++) {
        cin >> command;
        
        if (command == "push") {
	        // 정수 X 를 큐에 넣음 
            cin >> x;
            q.push(x);
        } else if (command == "size") {
	        // 큐에 들어있는 정수의 개수를 출력 
            cout << q.size() << endl;
        } else if (command == "empty") {
	        // 큐가 비어있는지 확인 
            cout << q.empty() << endl;
        } else if (q.empty()) {
            // pop, front, back 인 경우 큐가 비어 있으면 -1 을 출력해야 함 
            cout << "-1" << endl;
        } else if (command == "pop") {
	        // front 에 있는 값을 출력해주고 pop 해줌 
            cout << q.fir_fun() << endl;
            q.pop();
        } else if (command == "front") {
	        // front 에 있는 값 출력 
            cout << q.fir_fun() << endl;
        } else if (command == "back") {
	        // back 에 있는 값 출력 
            cout << q.back() << endl;
        }
    }

    return 0;
}

3. 연결리스트 사용

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int data;    // 저장되는 값 
    Node* next;  // 연결되는 노드
};

struct queue_struct {
  Node* rear_node = NULL;  // 데이터가 들어가야 하는 마지막 노드 
  Node* first_node = NULL; // 데이터가 꺼내져야 하는 첫번째 노드
  int s = 0;               // 현재 총 큐 크기 
  
  void push(int x) {
      Node* node = new Node();
      node -> data = x;
      
      if (rear_node == NULL) {
          // rear_node 가 NULL 인 경우는 현재 값이 없는거기 떄문에 
          // rear_node 와 first_node 에 새로 만들어진 node 로 초기화
          rear_node = node;
          first_node = node;
      } else {
          // 큐에 값이 있는 경우 
          // 가장 마지막에 있는 rear_node 의 next 를 새로 만들어진 node 로 설정
          Node* temp = rear_node;
          rear_node = node;
          temp -> next = node;
      }
      s++;
  }
  
  int empty() {
      if (first_node == NULL) {
          return 1;
      }
      return 0;
  }
  
  int fir_fun() {
      return first_node -> data;
  }
  
  int back() {
      return rear_node -> data;
  }
  
  int pop() {
      int num = first_node -> data;
      if(first_node != rear_node) {
          // 큐에 값이 하나 이상인 경우 
          // first_node 를 first_node 와 연결되어 있는 노드로 초기화해준다. 
          first_node = first_node -> next;
      } else {
          // 큐에 값이 하나밖에 없는 경우 
          // 큐를 모두 비워준다. 
          first_node = NULL;
          rear_node = NULL;
      }
      s--;
      return num;
  }
  
  int size() {
      return s;
  }
};

int main() {
    queue_struct q;
    
    int n; 					// 명령의 수 
    cin >> n;
    
    string command;		    // 명령어 
    int x;					// 스택에 넣을 수 
    
    for(int i=0;i<n;i++) {
        cin >> command;
        
        if (command == "push") {
	        // 정수 X 를 큐에 넣음 
            cin >> x;
            q.push(x);
        } else if (command == "size") {
	        // 큐에 들어있는 정수의 개수를 출력 
            cout << q.size() << endl;
        } else if (command == "empty") {
	        // 큐가 비어있는지 확인 
            cout << q.empty() << endl;
        } else if (q.empty()) {
            // pop, front, back 인 경우 큐가 비어 있으면 -1 을 출력해야 함 
            cout << "-1" << endl;
        } else if (command == "pop") {
	        // front 에 있는 값을 출력해주고 pop 해줌 
            cout << q.fir_fun() << endl;
            q.pop();
        } else if (command == "front") {
	        // front 에 있는 값 출력 
            cout << q.fir_fun() << endl;
        } else if (command == "back") {
	        // back 에 있는 값 출력 
            cout << q.back() << endl;
        }
    }

    return 0;
}

정답