[Data Structure] 자료구조(1강) - Queue

• 수식이 제대로 보이지 않는다면, 새로고침(F5)을 해주시기 바랍니다.

이번 글을 시작으로 하여, 여러 자료 구조의 개념 및 c++로의 프로그래밍을 다룰 예정입니다. 자료 구조는 비교적 널리 알려져있고, 다른 곳에서도 잘 설명된 곳이 많기 때문에 자료구조에 한해서는 간단한 개념 및 구현만을 다루겠습니다. 간단히 정리된 것을 볼 수 있는 용도로 적합할 것 같습니다.
경쟁적 프로그래밍 문제 풀이에 유용한 c++의 STL의 헤더파일도 함께 다루겠습니다.

Queue

선입선출(FIFO, First-In-First-Out)이 가능한 자료구조입니다. Queue 클래스를 구현하면 아래와 같습니다. (에 있는 모든 기능을 구현한 것은 아닙니다.)

#include <iostream>
using namespace std;

class Queue {
private:
    int* arr;
    int front, rear, capacity, count;
    bool isFull(){
        return capacity==count;
    }

public:
    Queue(int size) {
        capacity = size;
        arr = new int[capacity];
        front = 0;
        rear = -1;
        count = 0;
    }

    ~Queue() {
        delete[] arr;
    }

    bool empty() const {
        return count == 0;
    }

    void enqueue(int item) {
        if (isFull()) {
            cout << "Queue overflow\n";
            return;
        }
        rear = (rear+1)%capacity;
        arr[rear] = item;
        count++;
    }

    void dequeue() {
        if (empty()) {
            cout << "Queue underflow\n";
            return;
        }
        front = (front+1)%capacity;
        count--;
    }

    int peek() const {
        if (empty()) {
            cout << "Queue is empty\n";
            return -1;
        }
        return arr[front];
    }

    int size() const {
        return count;
    }
};

int main() {
    Queue q(5);

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "front: " << q.peek() << '\n';
    q.dequeue();
    cout << "after dequeue: " << q.peek() << '\n';

    q.enqueue(40);
    q.enqueue(50);
    q.enqueue(60);

    q.enqueue(70);

    while (!q.empty()) {
        cout << q.peek() << ' ';
        q.dequeue();
    }
    cout << '\n';

    return 0;
}

C++ <queue> 사용법 요약

함수	설명
push(x)	뒤에 원소 x 추가
pop()	앞에서 제거
front()	앞 원소 확인
back()	뒤 원소 확인
empty()	비었는지 확인
size()	크기 반환