C++, 큐 (Queue)구현하기 - 연결 리스트, 배열 이용

C++에서 큐(Queue)를 구현하는 방법에는 여러 가지가 있습니다. STL(Standard Template Library)에서 제공하는 std::queue를 사용할 수도 있고, 직접 사용자 정의 큐를 구현할 수도 있습니다. 아래는 사용자 정의 큐를 배열과 연결 리스트 두 가지 방식으로 구현한 예제입니다.

 

1. 배열을 이용한 큐 구현

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

#define MAX_SIZE 100

class Queue {
private:
    int data[MAX_SIZE];
    int front;
    int rear;

public:
    Queue() : front(0), rear(0) {}

    // 큐가 비어 있는지 확인
    bool isEmpty() const {
        return front == rear;
    }

    // 큐가 가득 찼는지 확인
    bool isFull() const {
        return (rear + 1) % MAX_SIZE == front;
    }

    // 큐에 데이터 추가
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is full!\n";
            return;
        }
        data[rear] = value;
        rear = (rear + 1) % MAX_SIZE;
    }

    // 큐에서 데이터 제거
    int dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty!\n";
            return -1;
        }
        int value = data[front];
        front = (front + 1) % MAX_SIZE;
        return value;
    }

    // 큐의 첫 번째 요소 확인
    int peek() const {
        if (isEmpty()) {
            cout << "Queue is empty!\n";
            return -1;
        }
        return data[front];
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "Front element: " << q.peek() << "\n";
    cout << "Dequeued: " << q.dequeue() << "\n";
    cout << "Dequeued: " << q.dequeue() << "\n";

    q.enqueue(40);
    cout << "Dequeued: " << q.dequeue() << "\n";

    return 0;
}

(Output)

Front element: 10
Dequeued: 10
Dequeued: 20
Dequeued: 30

C++, 큐 (Queue)구현하기

 

2. 연결 리스트를 이용한 큐 구현

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

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

class Queue {
private:
    Node* front;
    Node* rear;

public:
    Queue() : front(nullptr), rear(nullptr) {}

    ~Queue() {
        while (!isEmpty()) {
            dequeue();
        }
    }

    // 큐가 비어 있는지 확인
    bool isEmpty() const {
        return front == nullptr;
    }

    // 큐에 데이터 추가
    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (rear) {
            rear->next = newNode;
        }
        rear = newNode;
        if (!front) {
            front = rear;
        }
    }

    // 큐에서 데이터 제거
    int dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty!\n";
            return -1;
        }
        Node* temp = front;
        int value = temp->data;
        front = front->next;
        if (!front) {
            rear = nullptr;
        }
        delete temp;
        return value;
    }

    // 큐의 첫 번째 요소 확인
    int peek() const {
        if (isEmpty()) {
            cout << "Queue is empty!\n";
            return -1;
        }
        return front->data;
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "Front element: " << q.peek() << "\n";
    cout << "Dequeued: " << q.dequeue() << "\n";
    cout << "Dequeued: " << q.dequeue() << "\n";

    q.enqueue(40);
    cout << "Dequeued: " << q.dequeue() << "\n";

    return 0;
}

(Output)

Front element: 10
Dequeued: 10
Dequeued: 20
Dequeued: 30