[ 자료구조 ] Queue

큐(queue)는 선입선출 FIFO(First In First Out)의 형태를 띄는 자료구조로 처음 들어온 데이터가 먼저 나갑니다.

배열을 이용하여 큐를 만들면 처음 들어갔던 자료가 빠졌을경우, 그 자리가 비게됩니다.

따라서, 자료들을 이동시켜주는 작업을 해야하는 번거로움이 발생합니다.

 

그래서 원형 큐를 이용하여 구현.

 

1. 구현 사항

#include <iostream>
#define MAXSIZE 100
 
using namespace std;
 
template<typename T>
class Queue 
{
public:
    int front;
    int rear;
    int size;
    T* values;
 
    Queue()
    {
        size = MAXSIZE;
        values = new T[size];
        front = 0;
        rear = 0;
    }
 
    ~Queue()
    {
        delete[] values;
    }
 
    void push(T value)
    {
        if (!isFull())
        {
            values[rear] = value;
            rear = (rear + 1) % size;
        }
        else
            cout << "Stack is Full" << endl;
    }
 
    void pop()
    {
        if (!empty())
            front = (front + 1) % size;
        else
            cout << "Stack is Empty" << endl;
    }
 
    bool empty()
    {
        if (rear == front)
            return true;
        else
            return false;
    }
 
    bool isFull()
    {
        if ((rear + 1) % size == front)
            return true;
        else
            return false;
    }
};

2. STL 활용

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int main()
{
    queue<int> qu;
 
    // push
    qu.push(3);
    qu.push(2);
    qu.push(1);
 
    // pop
    qu.pop();
 
    // front
    cout << "front : " << qu .front() << endl;
 
    // back
    cout << "back : " << qu.back() << endl;
 
    // size
    cout << "size : " << qu.size() << endl;
 
    // empty
    cout << "empty : " << qu.empty() << endl;
 
    return 0;
}