Implementation of queue (sequential storage, chain storage)

 

/**
    Basic operations of queues ：
    Queue CreateQueue (int Maxsize): Initialize a new empty queue ;
    bool IsFull(Queue Q): Judge the queue Q Whether is full ;
    bool AddQ(Queue Q,ElementType X): Put the element X Push into the queue Q;
    bool IsEmpty(Queue Q): Determines if the queue is empty ;
    ElementType DelectQ(Queue Q): Delete and return the queue header element ;
*/

/**
    1) Circular queue , When Front==Rear when , Indicates that the queue is empty ;
    When (Rear+1)%Maxsize==Front when , The queue is full ;（ That is, when the circular queue is full, there is a position that is empty ）
*/

/**
     Basic operations of queues ：
    Queue CreateQueue (int Maxsize):  Initialize a new empty queue ;
    bool IsFull(Queue Q): Judge the queue Q Whether is full ;
    bool AddQ(Queue Q,ElementType X): Put the element X Push into the queue Q;
    bool IsEmpty(Queue Q): Determines if the queue is empty ;
    ElementType DelectQ(Queue Q): Delete and return the queue header element ;
*/

/**
    1) Circular queue , When Front==Rear when , Indicates that the queue is empty ;
     When (Rear+1)%Maxsize==Front when , The queue is full ;（ That is, when the circular queue is full, there is a position that is empty ）
*/

/**
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define error 1e9
const int Maxsize = 100;
typedef int ElementType;
typedef int Position;
typedef struct QNode * PtrToQNode;
struct QNode
{
    ElementType *Data;
    Position Front,Rear;
    int Maxsize;
};
typedef PtrToQNode Queue;

Queue CreateQueue (int Maxsize);
bool IsFull(Queue Q);
bool AddQ(Queue Q,ElementType X);
bool IsEmpty(Queue Q);
ElementType DelectQ(Queue Q);

int main()
{
    Queue Q=CreateQueue(Maxsize);
    cout << "DElectQ:\n";
    auto tem=DelectQ(Q);
        if(tem!=error)
            printf("%d ",tem);
    for(int i=1;i<15;++i)
        AddQ(Q,i);

    cout << "\nDElectQ After AddQ:\n";
    for(int i=0;i<10;++i)
    {
        auto tem=DelectQ(Q);
        if(tem!=error)
            printf("%d ",tem);
    }

    cout << "\nDElectQ:\n";
    for(int i=0;i<10;++i)
    {
        auto tem=DelectQ(Q);
        if(tem!=error)
            printf("%d ",tem);
    }
    return 0;
}

Queue CreateQueue (int Maxsize)
{
    Queue Q=(Queue) malloc(sizeof(QNode));
    Q->Data=(ElementType *) malloc(Maxsize*sizeof(ElementType));
    Q->Front=Q->Rear=0;
    Q->Maxsize=Maxsize;
    return Q;
}

bool IsFull(Queue Q)
{
    return ((Q->Rear+1)%Q->Maxsize==Q->Front);
}

bool AddQ(Queue Q,ElementType X)
{
    if(IsFull(Q))
    {
        printf(" The queue is full \n");
        return false;
    }
    else
    {
        Q->Rear=(Q->Rear+1)%Q->Maxsize;
        Q->Data[Q->Rear]=X;
        return true;
    }
}

bool IsEmpty(Queue Q)
{
    return (Q->Rear==Q->Front);
}

ElementType DelectQ(Queue Q)
{
    if(IsEmpty(Q))
    {
        printf(" The queue is empty \n");
        return error;
    }
    else
    {
        Q->Front=(Q->Front+1)%Q->Maxsize;
        return Q->Data[Q->Front];
    }
}
*/

 2) The chain storage implementation of the queue ;
    Linked list without leading node ：

/**
    2) The chain storage implementation of the queue ;
     Linked list without leading node ：
*/


#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define error 1e9
const int Maxsize = 100;
typedef int ElementType;
typedef struct Node * PtrToNode;
struct Node
{
    ElementType data;
    PtrToNode next;
};  // The linked list node implements the queue 
typedef PtrToNode Position;
typedef struct QNode *PtrToQNode;
struct QNode
{
    Position Front,Rear;    // Pointer to the beginning and end of the queue 
    int Maxsize;    // The maximum capacity of the queue 
    int sum;    // Number of people who have joined the team 
};  // Queue node 
typedef PtrToQNode Queue;

Queue CreateQueue ();
bool IsFull(Queue Q);
bool AddQ(Queue Q,ElementType X);
bool IsEmpty(Queue Q);
ElementType DelectQ(Queue Q);

int main()
{
    Queue Q=CreateQueue();
    cout << "size create a empty queue: " << Q->sum << endl;
    cout << "DElectQ after create a empty queue:\n";
    auto tem=DelectQ(Q);
        if(tem!=error)
            printf("%d ",tem);
    for(int i=1;i<15;++i)
        AddQ(Q,i);
    cout << "\nsize after add elements: " << Q->sum << endl;
    cout << "\nDElectQ After AddQ:\n";
    for(int i=0;i<10;++i)
    {
        auto tem=DelectQ(Q);
        if(tem!=error)
            printf("%d ",tem);
    }

    cout << "\nsize after delect elements: " << Q->sum << endl;
    cout << "\nDElectQ:\n";
    for(int i=0;i<10;++i)
    {
        auto tem=DelectQ(Q);
        if(tem!=error)
            printf("%d ",tem);
    }
    return 0;
}

Queue CreateQueue ()
{
    Queue Q=(Queue) malloc(sizeof(QNode));
    Q->Front=Q->Rear=NULL;
    Q->Maxsize=Maxsize;
    Q->sum=0;
    return Q;
}

bool IsFull(Queue Q)
{
    return (Q->sum==Q->Maxsize);
}


// There are two situations such as joining the team , One is that the queue is empty , Then the head and tail pointers should point to this new node , Otherwise, the tail pointer points to this new node , The head pointer doesn't move ,
// Then move the pointer back one position 
bool AddQ(Queue Q,ElementType X)
{
    if(IsFull(Q))
    {
        printf(" The queue is full \n");
        return false;
    }
    else
    {
        Position RearCell=(PtrToNode) malloc(sizeof(Node));
        RearCell->data=X;
        RearCell->next=NULL;
        if(Q->Front==NULL)
            Q->Front=Q->Rear=RearCell;
        else
        {
            Q->Rear->next=RearCell;
            Q->Rear=RearCell;
        }
        Q->sum+=1;
        return true;
    }
}

bool IsEmpty(Queue Q)
{
    return (Q->Front==NULL);
}

ElementType DelectQ(Queue Q)
{
    if(IsEmpty(Q))
    {
        printf(" The queue is empty \n");
        return error;
    }
    else
    {
        Position FrontCell=Q->Front;
        ElementType FrontElem=FrontCell->data;
        if(Q->Front==Q->Rear)
            Q->Front=Q->Rear=NULL;
        else
            Q->Front=Q->Front->next;
        free(FrontCell);
        Q->sum-=1;
        return FrontElem;
    }
}