[자료구조] 큐 (queue)

큐

큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로 선입선출 특성을 가진다.

 

구조상으로 큐가 스택과 다른 점이 있다.

스택의 경우, 삽입과 삭제가 같은 쪽에서만 일어난다.

그렇지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다.

 

✅ 큐에서 삽입이 일어나는 곳을 후단(rear)이라 하고 삭제가 일어나는 곳을 전단(front)이라고 한다.

 

---

📌

큐 연산

• enQueue(int value) : 큐 후단(rear)에 값을 추가
• deQueue() : 큐 전단(front)의 값을 제거
• isFull() : 큐가 가득 찼는지 확인
• isEmpty() : 큐가 비어있는지 확인
• displayQueue() : 큐에 있는 요소들 출력

 

---

클래스 생성

#define MAX_SIZE 5

class Queue
{
    int myqueue[MAX_SIZE], front, rear;

public:
    Queue();
    bool isFull();
    bool isEmpty();
    void enQueue(int value);
    int deQueue();
    void displayQueue();
};

클래스로 큐를 정의해준다.

 

---

생성자 초기화

Queue::Queue()
{
    front = -1;
    rear = -1;
}

 

 

enQueue 함수

void Queue::enQueue(int value)
{
    if (isFull())
    {
        cout << "\nQueue is full!!";
    }
    else
    {
        if (front == -1)
            front = 0;
        rear++;
        myqueue[rear] = value;
    }
}

 

 

deQueue 함수

int Queue::deQueue()
{
    int value;
    if (isEmpty())
    {
        cout << "Queue is empty!!\n";
        return (-1);
    }
    else
    {
        value = myqueue[front];
        if (front >= rear)
        { //큐에 하나의 요소만 있을 때
            front = -1;
            rear = -1;
        }
        else
        {
            front++;
        }
        return (value);
    }
}

 

 

isFull 함수

bool Queue::isFull()
{
    if (front == 0 && rear == MAX_SIZE - 1)
        return true;
    return false;
}

 

 

isEmpty 함수

bool Queue::isEmpty()
{
    if (front == -1)
        return true;
    return false;
}

 

 

displayQueue 함수

void Queue::displayQueue()
{
    if (isEmpty())
    {
        cout << "\nQueue is Empty!!\n";
    }
    else
    {
        cout << "\nFront = " << front;
        cout << "\nQueue elements : ";
        for (int i = front; i <= rear; i++)
            cout << myqueue[i] << "\t";
        cout << "\nRear = " << rear << "\n";
    }
}

---

📌 전체 코드

#include <iostream>
#define MAX_SIZE 5
using namespace std;

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

public:
    Queue();
    bool isFull();
    bool isEmpty();
    void enQueue(int value);
    int deQueue();
    void displayQueue();
};

Queue::Queue()
{
    front = -1;
    rear = -1;
}

void Queue::enQueue(int value)
{
    if (isFull())
    {
        cout << "\nQueue is full!!";
    }
    else
    {
        if (front == -1)
            front = 0;
        rear++;
        myqueue[rear] = value;
    }
}

int Queue::deQueue()
{
    int value;
    if (isEmpty())
    {
        cout << "Queue is empty!!\n";
        return (-1);
    }
    else
    {
        value = myqueue[front];
        if (front >= rear)
        {
            front = -1;
            rear = -1;
        }
        else
        {
            front++;
        }
        return (value);
    }
}

bool Queue::isFull()
{
    if (front == 0 && rear == MAX_SIZE - 1)
    	return true;
    return false;
}

bool Queue::isEmpty()
{
    if (front == -1)
        return true;
    return false;
}

void Queue::displayQueue()
{
    if (isEmpty())
    {
        cout << "\nQueue is Empty!!\n";
    }
    else
    {
        cout << "\nFront = " << front;
        cout << "\nQueue elements : ";
        for (int i = front; i <= rear; i++)
            cout << myqueue[i] << "\t";
        cout << "\nRear = " << rear << "\n";
    }
}

int main()
{
    Queue q;

    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);

    q.displayQueue();

    //deQueue =>removes 1
    q.deQueue();

    //queue after dequeue
    q.displayQueue();
}

 

 

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!