Queue(큐) 구현 & STL 총정리

c++ STL container 중 하나인 queue를 구현해봤다.

작동 원리

FIFO (First - In - First - Out) : 먼저 들어온 값이 먼저 나가는 구조.

알고리즘

※ circular queue

circular queue란 rear와 front라는 변수를 통해 array 저장 공간을 효율적으로 사용하는 queue 구현 방법이다.
rear는 array 속에 있는 값 중 가장 최근 push된 값의 array index를 나타낸다.
front는  array 속에 있는 값 중 가장 먼저 push된 값의 array index를 나타낸다.
rear와 front를 잘 조절하면
queue가 empty 한 상태인지
queue가 full 한 상태인지
queue의 size는 몇인지 등등
queue의 상태에 대해 쉽게 알 수 있다.

예를 들어서 좀 더 쉽게 설명 하겠다.

size가 5인 array queue에 1,2,3,4,5가 push 된후, 2번의 pop. -> array : [ , ,3,4,5]
6이 push -> array : [ , , 3,4,5,6] (X)    array : [6, ,3,4,5] (O)
후자가 circular queue 이다.
이처럼 pop된 공간을 계속 해서 활용하는 array queue를 말한다. 메모리를 최대한 아끼기 때문에 효율적이다.

코드 구조

class를 사용하여 queue의 변수와 메서드를 정리해 두었다.
template을 이용하여 여러가지 type의 queue로 활용할 수 있게 해두었다.

변수

int size; ->최대 queue의 크기
int rear; -> 가장 최근 들어온 값의 array index
int front; -> 가장 먼저 들어온 값의 array index
T* values -> queue를 나타내는 array

함수

1) isfull -> 꽉 찬 상태라면 true를 return 아니라면 false를 return.
2) empty -> 비어있다면 true를 return, 아니라면 false를 return.
3) push -> 값을 집어넣음.
4) pop -> queue속의 값 중 가장 먼저 들어간 값을 꺼냄.
5) queue_front -> queue 속의 값 중 가장 먼저 들어간 값을 반환.
6) queue_size -> queue 속의 값들의 개수 반환.

Coding

 

// c++ - array를 이용하여 queue 구현
// rear 와 front를 이용하여 circular queue를 구현하였다.


#include <iostream>
#define MAXVALUE 5 // queue size

using namespace std;

template <class T>
class Queue{
public:
    int size; // queue max size.
    int rear; // queue back index.
    int front; // queue front index.
    T* values; // queue using array.

    Queue(){
            front = -1;
            rear = -1;
            size = MAXVALUE;
            values = new T[size];
    }

    ~Queue(){
        delete[] values;
    }

    // queue가 다 찼다면 true return , else false return.

    bool isfull(){
        if((rear+1)%size == front) return true;
        return false;
    }

    // 비어있다면 true, else false.

    bool empty(){
        return (front == -1) ? true : false;
    }

    // 데이터 queue에 입력.

    void push(T value)
    {
        if(empty()){
            values[++rear] = value;
            front++;
        }
        else if(isfull()){
            cout << "queue is full!!" << endl;
        }
        else{
            rear = (rear+1) % size;
            values[rear] = value;
        }
    }

    // 맨 앞의 값 꺼내기.(선입선출)

    void pop(){
        if(empty()) cout << "queue is empty! pop doesn't work." << endl;
        else if( front==rear && front != -1 ){
            front = -1;
            rear = -1;
        }
        else{
            front = (front+1) % size;
        }
    }

    // 가장 최근에 들어온 데이터 반환

    T queue_back(){
        if(empty()){
            return -1;
        }
        return values[rear];
    }

    // 가장 먼저 들어온 데이터 반환

    T queue_front(){
        if(empty()){
            return -1;
        }
        return values[front];
    }

    // 현재 queue의 데이터 갯수

    int queue_size(){
        int i = front;
        int cnt = 1;
        if(empty()) return -1;
        else if(isfull()) return size;

        while(i!=rear){
            i = (i+1)%size;
            cnt++;
        }
        return cnt;
    }
};

2022.02.10 - [c++/문법] - [c++] Template(템플릿) 총 정리 & 예제

[c++] Template(템플릿) 총 정리 & 예제

Template을 사용하여 int 뿐만 아니라 string , double 등 다른 타입을 담는 queue로 사용 가능하다.

Template을 잘 모르겠다면 위 게시글을 참고 하자

--------------------------------------------------------------------------------------------------

STL queue

헤더파일

#include <queue>

선언

queue<데이터 타입> 이름;

ex) queue<int> q;

 

함수

 

① push
Queue에 데이터를 추가하는 함수이다.

queue이름.push(데이터);
ex) q.push(3);

② pop
Queue 의 값 중 가장 먼저 들어온 값을 삭제하는 함수이다.

queue이름.pop();
ex)q.pop();

③ front
Queue의 값 중 가장 먼저 들어온 값을 반환!

queue이름.front()
ex) int a = q.front();

④ back
Queue의 값 중 가장 늦게 들어온 값을 반환!

queue이름.back()
ex) int a = q.back();

⑤ size
Queue안에 있는 데이터 개수 반환!

queue이름.size()
ex) int a = q.size();

⑥empty
Queue가 비어있다면 true 를, 아니라면 false를 반환!

queue이름.empty()
ex) cout << q.empty() << endl;

⑦swap

두 큐의 내용을 바꾸는 함수
swap(queue1 이름, queue2 이름);
ex) swap(q1,q2);