Queue [c++]

Queue 개념

queue는 stack과 반대로 입력과 출력 공간이 따로 존재하고 제일 먼저 들어간 데이터가 제일 먼저 나온다.

---

Queue 특징

-FIFO(First In - First Out)

---

c++로 구현한 array Queue

#include <iostream>
using namespace std;
template <typename T>
struct Node {
        T data;
};
template <typename T>
class ArrayQueue{
        private:
                Node<T>* nodes_;
                int capacity_;
                int front_;
                int rear_;

        public:
                ArrayQueue();
                ~ArrayQueue();
                ArrayQueue(int capacity);

                void enQueue(T newData);
                void deQueue();
                int getSize();
                bool isEmpty();
                void printAll();
};
template <typename T>
ArrayQueue<T>::ArrayQueue():nodes_(nullptr), front_(-1), rear_(-1), capacity_(0){}
template <typename T>
ArrayQueue<T>::~ArrayQueue(){
        delete nodes_;
}
template <typename T>
ArrayQueue<T>::ArrayQueue(int capacity){
        capacity_ = capacity;
        front_ = -1;
        rear_ = -1;
        nodes_ = (Node<T>*)malloc(sizeof(Node<T>)*capacity_+1);
}
template <typename T>
void ArrayQueue<T>::enQueue(T newData){
        if (front_ == -1){
                nodes_[++front_].data = newData;
                rear_ = front_ + 1;
        }
        else {
                if (rear_ == capacity_+1){
                        rear_ = 0;
                }
                nodes_[rear_++].data = newData;
        }
}
template <typename T>
void ArrayQueue<T>::deQueue(){
        cout << "deQueue : " << nodes_[front_].data << endl;
        front_ = (front_ + 1) % (capacity_+1);
}
template <typename T>
void ArrayQueue<T>::printAll(){
        cout << "front -> ";

        for (int i=front_; i != rear_%(capacity_+1); i = (i+1)%(capacity_+1)){
                cout << nodes_[i].data << " -> ";
        }

        cout << "rear" << endl;
}
template <typename T>
int ArrayQueue<T>::getSize(){
        return (front_ + rear_ + 1)%capacity_;
}
template <typename T>
bool ArrayQueue<T>::isEmpty(){
        return front_ == rear_;
}
int main(){
        ArrayQueue<int>* arrayQueue = new ArrayQueue<int>(10);

        for (int i=0;i<10;i++){
                arrayQueue->enQueue(i+1);
        }

        arrayQueue->printAll();

        for (int i=0;i<5;i++){
                arrayQueue->deQueue();
        }

        arrayQueue->printAll();

        for (int i=0;i<3;i++){
                arrayQueue->enQueue(i+6);
                arrayQueue->printAll();
        }
}

출력 결과

front -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> rear
deQueue : 1
deQueue : 2
deQueue : 3
deQueue : 4
deQueue : 5
front -> 6 -> 7 -> 8 -> 9 -> 10 -> rear
front -> 6 -> 7 -> 8 -> 9 -> 10 -> 6 -> rear
front -> 6 -> 7 -> 8 -> 9 -> 10 -> 6 -> 7 -> rear
front -> 6 -> 7 -> 8 -> 9 -> 10 -> 6 -> 7 -> 8 -> rear

---

c++로 구현한 linked list Queue

#include <iostream>
using namespace std;
template <typename T>
struct Node{
        T data;
        struct Node* next;
};
template <typename T>
class LinkedQueue{
        private:
                Node<T>* front_;
                Node<T>* rear_;
                int size_;

        public:
                LinkedQueue();
                ~LinkedQueue();

                Node<T>* createNode(T newData);
                void destroyNode(Node<T>* node);
                int getSize();
                void enQueue(Node<T>* newNode);
                Node<T>* deQueue();
                bool isEmpty();
                void printAll();
};
template <typename T>
LinkedQueue<T>::LinkedQueue():front_(nullptr), rear_(nullptr), size_(0){}
template <typename T>
LinkedQueue<T>::~LinkedQueue(){
        Node<T>* current = front_;

        while (current != nullptr){
                Node<T>* temp = current;
                current = current->next;
                destroyNode(temp);
        }
}
template <typename T>
Node<T>* LinkedQueue<T>::createNode(T newData){
        Node<T>* newNode = new Node<T>();

        newNode->data = newData;
        newNode->next = nullptr;

        return newNode;
}
template <typename T>
void LinkedQueue<T>::destroyNode(Node<T>* node){
        node->next = nullptr;
        free(node);
}
template <typename T>
int LinkedQueue<T>::getSize(){
        return size_;
}
template <typename T>
void LinkedQueue<T>::enQueue(Node<T>* newNode){
        if (front_ == nullptr){
                front_ = newNode;
        }
        else {
                newNode->next = rear_;
        }
        rear_ = newNode;
        size_++;
}
template <typename T>
Node<T>* LinkedQueue<T>::deQueue(){
        Node<T>* temp;

        if (front_ == rear_){
                temp = front_;
                front_ = nullptr;
                rear_ = nullptr;
        }
        else {
                Node<T>* current = rear_;

                while (current->next != front_){
                        current = current->next;
                }

                front_ = current;
                front_->next = nullptr;
        }

        size_--;
        return temp;
}
template <typename T>
bool LinkedQueue<T>::isEmpty(){
        return size_ == 0;
}
template <typename T>
void LinkedQueue<T>::printAll(){
        Node<T>* current = rear_;
        cout << "rear -> ";

        while (current != nullptr){
                cout << current->data << " -> ";
                current = current->next;
        }

        cout << "front" << endl;
}
int main(){
        LinkedQueue<int>* linkedQueue = new LinkedQueue<int>();

        Node<int>* newNode = new Node<int>;
        for (int i=0;i<6;i++){
                newNode = linkedQueue->createNode(i+1);
                linkedQueue->enQueue(newNode);
        }
        linkedQueue->printAll();

        while (!linkedQueue->isEmpty()){
                newNode = linkedQueue->deQueue();
                linkedQueue->printAll();
        }
}

출력 결과
rear -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> front
rear -> 6 -> 5 -> 4 -> 3 -> 2 -> front
rear -> 6 -> 5 -> 4 -> 3 -> front
rear -> 6 -> 5 -> 4 -> front
rear -> 6 -> 5 -> front
rear -> 6 -> front
rear -> front

---