队列的实现

常规链队列的实现

#include <iostream>

using namespace std;
#define OK true;
#define ERROR false;

typedef struct QNode{
    int data;
    QNode *Next;
}QNode , *QueuePtr;

typedef struct{
    QueuePtr Front;
    QueuePtr Rear;
}LinkQueue;

bool Init(LinkQueue &Q){
    Q.Front = Q.Rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.Front){
        return ERROR;
    }
    Q.Front->Next = NULL;
    return OK;
}

//插入
bool Insert(LinkQueue &Q , int e){
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p){
        return ERROR;
    }
    p->data = e;
    p->Next = NULL;
    Q.Rear->Next = p;
    Q.Rear = p;
    return OK;
}

//删除
bool Delete(LinkQueue &Q , int &e){
    if(Q.Front == Q.Rear) return ERROR;
    QueuePtr p = Q.Front->Next;
    e = p->data;
    Q.Front->Next = p->Next;
    if(Q.Rear == p) Q.Rear = Q.Front;  //当队列中只有一个元素时
    free(p);
    return OK;
}

//遍历
void print(LinkQueue Q){
    if(Q.Front == Q.Rear){
        cout<<"没有元素"<<endl;
    }
    else {
        Q.Front = Q.Front->Next;
        while(Q.Front){
            cout<<Q.Front->data<<' ';
            Q.Front = Q.Front->Next;
        }
    }
    cout<<endl;
}

//销毁队列
bool DestroyQueue(LinkQueue &Q){
    while(Q.Front){
        Q.Rear = Q.Front->Next;
        free(Q.Front);
        Q.Front = Q.Rear;
    }
    return OK;
}


int main()
{
    LinkQueue Q;
    Init(Q);
    for(int i = 0 ; i<5 ; ++i){
        int n;
        cin>>n;
        Insert(Q , n);
    }
    print(Q);
    int e;
    Delete(Q , e);
    cout<<endl;
    cout<<e<<endl;
    print(Q);
    DestroyQueue(Q);
    print(Q);
}

循环队列的实现

循环队列主要是针对队列的顺序存储结构，主要目的是避免顺序存储中的内存空间的浪费。 下面的这种方法少用一个储存空间。

#include <iostream>

using namespace std;
#define OK true;
#define ERROR false;
#define MAXSIZE 6

typedef struct Queue{
    int *base;
    int Front;
    int Rear;
}Queue;

bool Init(Queue &Q){
    Q.base = (int *)malloc(MAXSIZE * sizeof(int));
    if(!Q.base) return ERROR;
    Q.Front = Q.Rear = 0;
    return OK;
}

//队列长度
int getLength(Queue &Q){
    return (Q.Rear - Q.Front + MAXSIZE) % MAXSIZE;
}

bool Insert(Queue &Q , int e){
    if((Q.Rear + 1) % MAXSIZE == Q.Front) return ERROR;  //队列满的标志
    Q.base[Q.Rear] = e;
    Q.Rear = (Q.Rear + 1)%MAXSIZE;
    return OK;
}

bool Delete(Queue &Q , int &e){
    if(Q.Front == Q.Rear) return ERROR;  //队列空的标志
    e = Q.base[Q.Front];
    Q.Front = (Q.Front + 1)%MAXSIZE;
    return OK;
}

void print(Queue Q){
    if(Q.Front == Q.Rear) cout<<"队列空"<<endl;
    else {
        while((Q.Front + 1)%MAXSIZE != Q.Rear){
            cout<<Q.base[Q.Front]<<' ';
            Q.Front = Q.Front+1;
        }
        cout<<Q.base[Q.Front];
    }
    cout<<endl;
}

int main()
{
    Queue Q;
    Init(Q);
    for(int i = 0 ; i<5 ; ++i){
        int n;
        cin>>n;
        bool a;
        a = Insert(Q , n);
        cout<<a<<' ';
    }
    int e;
    cout<<endl;
    cout<<getLength(Q)<<endl;
    print(Q);
    //cout<<Q.Front<<' '<<Q.Rear<<endl;
    Delete(Q , e);
    cout<<e<<endl;
    print(Q);
    cout<<getLength(Q)<<endl;
    
}