자료 구조 Dequeue와 구현하기 (C++)

설명 :

 

Dequeue의 구조

덱은 큐의 진화 버전이라고 생각하면 된다.

큐가 앞으로 빼고 뒤로 넣는 자료 구조이면,

덱은 앞으로 뒤로도 뺴고 뒤로 넣는 자료구조이다.

 

코드 : 

Dequeue.cpp :

#include <iostream>
#define maxsize 5;

using namespace std;

class Dequeue {

private:
int front;
int rear;
int size;
int *values;
int number;
public:

Dequeue() //생성자 함수
{
size = maxsize;

values = new int[size]; //최대크기만큼 동적 배열 생성

front = 0; //앞을 나타내는 변수

rear = 1; //뒤를 나타내는 변수

number = 0; //현재 들어가 있는 데이터의 수를 나타내는 변수
}

bool isEmpty() //자료 구조가 비어 있는지 확인하는 함수
{

if (number == 0) //현재 데이터가 0개 들어가 있다면
{
return true;
}

else //아니라면
{
return false;
}
}

bool isFull() //자료 구조가 가득 차있는지 확인하는 함수
{
if (number == size) //현재 데이터가 최대크기만큼 들어가 있다면
{
return true;
}

else
{
return false;
}
}

void front_push(int value) //앞으로 넣는 것
{
if (isFull() == true) //자료 구조에 데이터가 가득 차 있다면
{
cout << "Dequeue is Full" << endl; //출력
}

else
{
values[front] = value; //배열의 rear번쨰 인덱스에 value 값을 저장

front = (front -1) % size; //size 개수만큼 원을 나눠서 차례대로 돌아가는 원형 큐 아이디어

if (front < 0) //front가 앞으로 가므로 하나 뺴줘야 하는데, 음수가 될 수 있는 걸 방지
front = size - 1;

number = number + 1; //데이터를 추가해줬으니 현재 데이터 개수를 나타내는 변수에 1 추가하기
}
}

void rear_push(int value) //뒤로 넣는 것
{
if (isFull() == true) //자료 구조에 데이터가 가득 차 있다면
{
cout << "Dequeue is Full" << endl; //출력
}

else
{
values[rear] = value; //배열의 rear번쨰 인덱스에 value 값을 저장

rear = (rear + 1) % size; //size 개수만큼 원을 나눠서 차례대로 돌아가는 원형 큐 아이디어

number = number + 1; //데이터를 추가해줬으니 현재 데이터 개수를 나타내는 변수에 1 추가하기
}
}

void front_pop()
{
if (isEmpty() == true) //자료 구조에 데이터가 비어있다면
{
cout << "Dequeue is Empty" << endl; //출력
}

else
{
front = (front + 1) % size; //size 개수만큼 원을 나눠서 차례대로 돌아가는 원형 큐 아이디어

number = number -1 ; //데이터를 뺴주었으니 현제 데이터 개수를 나타내는 변수에 1 빼기
}
}

void rear_pop()
{
if (isEmpty() == true) //자료 구조에 데이터가 비어있다면
{
cout << "Dequeue is Empty" << endl; //출력
}

else
{
rear = (rear - 1) % size; //size 개수만큼 원을 나눠서 차례대로 돌아가는 원형 큐 아이디어

if (rear < 0) //뒤에서 빼주므로, rear에 -1을 해줘야 함
rear = size - 1;

number = number - 1; //데이터를 뺴주었으니 현제 데이터 개수를 나타내는 변수에 1 빼기
}
}

void print()
{
if (isEmpty() == true) //자료 구조에 데이터가 비어있다면
{
cout << "There is nothing" << endl; //출력
}

else
{
int j = (front + 1) % size; //가장 처음 부분을 size로 나눈 나머지를 j에 저장


for (int i = 0; i < number; i++)
{
cout << values[j] << " "; //배열의 값 출력

j = (j + 1) % size; //원형 구조로 돈다

}

cout << endl;
}
}
};

 

main.cpp :

#include<iostream>
#include "dequeue.cpp"


using namespace std;

int main()
{
    Dequeue q;

    q.front_push(15);

    q.front_push(2);

    q.rear_push(3);

    q.rear_push(11);

    q.rear_push(20);

    q.rear_push(30);

    q.print();

    q.front_pop();

    q.print();

    q.front_pop();

    q.print();

    q.rear_pop();

    q.print();

    q.rear_pop();
    q.rear_pop();
    q.rear_pop();

    q.print();

    return 0;
}

 

출력 결과 :