본문 바로가기

PS/BOJ

[C++] BOJ (백준) 10845 : 큐

문제

10845번: 큐 (acmicpc.net)

 

10845번: 큐

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

www.acmicpc.net

코드 1 (std::queue)
#include <iostream>
#include <queue>

using namespace std;

queue<int> q;

void push(int num) {
  q.emplace(num);
}

bool empty() {
  return q.empty();
}

int pop() {
  if (empty()) return -1;

  int res = q.front();
  q.pop();
  return res;
}

int size() {
  return (int) q.size();
}

int front() {
  if (empty()) return -1;

  return q.front();
}

int back() {
  if (empty()) return -1;

  return q.back();
}

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

  int n;
  cin >> n;
  while (n--) {
    string cmd;
    cin >> cmd;
    if (cmd == "push") {
      int num;
      cin >> num;
      push(num);
    } else if (cmd == "pop") {
      cout << pop() << '\n';
    } else if (cmd == "size") {
      cout << size() << '\n';
    } else if (cmd == "empty") {
      cout << empty() << '\n';
    } else if (cmd == "front") {
      cout << front() << '\n';
    } else if (cmd == "back") {
      cout << back() << '\n';
    }
  }
  return 0;
}

 

설명

queue 헤더의 std::queue를 이용해 손쉽게 해결할 수 있다.

 

코드 2 (직접 구현)
#include <iostream>

using namespace std;

struct LinkedList {
  struct Node {
    int data;
    Node *next;

    explicit Node(int data) : data(data), next(nullptr) {}
  };

  Node *head = nullptr;
  Node *tail = nullptr;

  [[nodiscard]] bool isEmpty() const {
    return !head;
  }

  void addBack(int data) {
    Node *pNode = new Node(data);

    if (isEmpty()) {
      head = pNode;
      tail = pNode;
    } else {
      tail->next = pNode;
      tail = pNode;
    }
  }

  void deleteFront() {
    if (head == tail) {
      head = nullptr;
      tail = nullptr;
    } else {
      head = head->next;
    }
  }
};

struct Queue : LinkedList {
  void push(int num) {
    addBack(num);
  }

  bool empty() {
    return isEmpty();
  }

  int front() {
    if (empty()) return -1;

    return head->data;
  }

  int back() {
    if (empty()) return -1;

    return tail->data;
  }

  int pop() {
    if (empty()) return -1;

    int res = front();
    deleteFront();
    return res;
  }

  int size() {
    int cnt = 0;
    Node *pNode = head;
    while (pNode) {
      cnt++;
      pNode = pNode->next;
    }
    return cnt;
  }
};

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

  Queue q;
  int n;
  cin >> n;
  while (n--) {
    string cmd;
    cin >> cmd;
    if (cmd == "push") {
      int num;
      cin >> num;
      q.push(num);
    } else if (cmd == "pop") {
      cout << q.pop() << '\n';
    } else if (cmd == "size") {
      cout << q.size() << '\n';
    } else if (cmd == "empty") {
      cout << q.empty() << '\n';
    } else if (cmd == "front") {
      cout << q.front() << '\n';
    } else if (cmd == "back") {
      cout << q.back() << '\n';
    }
  }
  return 0;
}
설명

Linked List를 구현한 후 상속하여 Queue를 구현하였다.