数据结构学习心得——顺序队和链队

秒速五厘米 2022-06-09 06:19 271阅读 0赞

## 队列的定义 ##

和栈相反队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾，允许删除的一端叫做对头。

## 顺序队和链队 ##

顺序队列是队列的顺序存储结构，顺序队列实际上是运算受限的顺序表。和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应设置为0。

![这里写图片描述][SouthEast]

用链表表示的队列简称为链队，一个链队显然需要两个分别只是对头和队尾的指针才能唯一确定。

![这里写图片描述][SouthEast 1]

## 顺序队和链队的代码实现 ##

这里注意顺序队我实现的是循环队，注意循环队列的队空和队满的判断上的不同。

#include <iostream>
    
    using namespace std;
    #define maxSize 20//宏定义
    
    //顺序队列的定义
    typedef struct SqQueue
    {
        int data[maxSize];
        int front;
        int rear;
    }SqQueue;
    
    //队结点类型定义
    typedef struct QNode
    {
        int data;
        struct QNode *next;
    }QNode;
    
    //链队的定义
    typedef struct LiQueue
    {
        QNode *front;
        QNode *rear;
    }LiQueue;
    
    //顺序队列的初始化
    void initSqQueue(SqQueue &q)
    {
        q.front = q.rear = 0;
    }
    
    //判断顺序队列空
    int isSqQueueEmpty(SqQueue q)
    {
        if(q.front == q.rear)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    
    //顺序队列入队
    int enSqQueue(SqQueue &q,int x)
    {
        if((q.rear+1)%maxSize==q.front)
        {
            return 0;
        }
        else
        {
            q.rear = (q.rear + 1)%maxSize;
            q.data[q.rear] = x;
            return 1;
        }
    }
    
    //顺序队列出队
    int deSqQueue(SqQueue &q,int &x)
    {
        if(isSqQueueEmpty(q))
        {
            return 0;
        }
        else
        {
            q.front = (q.front + 1)%maxSize;
            x = q.data[q.front];
            return 1;
        }
    }
    
    //链队初始化
    void initQueue(LiQueue *&q)
    {
        q = new LiQueue;
        q->front=q->rear=NULL;
    }
    
    //判断链队为空
    int isQueueEmpty(LiQueue *q)
    {
        //这里注意q->front == q->rear不能判断链队为空，因为只有一个结点时也有q->front == q->rear
        if(q->front==NULL ||q->rear==NULL)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    
    //链队入队
    void enQueue(LiQueue *&q,int x)
    {
        QNode *p = new QNode;
        p->data = x;
        p->next =NULL;
        if(q->rear==NULL)
        {
            q->front = q->rear = p;
        }
        else
        {
            q->rear->next = p;
            q->rear = p;
        }
    
    }
    
    //链队出队
    int deQueue(LiQueue *&q,int &x)
    {
        QNode *p;
        if(isQueueEmpty(q))
        {
            return 0;
        }
        //同样注意q->front == q->rear的情况
        if(q->front == q->rear)
        {
            p = q->front;
            x = p->data;
            q->front = q->rear = NULL;
            delete p;
            return 1;
        }
        else
        {
            p = q->front;
            q->front = p->next;
            x = p->data;
            delete p;
            return 1;
        }
    }
    int main()
    {
        cout << "Hello world!" << endl;
        return 0;
    }

[SouthEast]: /images/20220609/c329b3f6e3df4e2b89c227d9539804aa.png
[SouthEast 1]: /images/20220609/e2715a0d6eda49929df91c7977d007d6.png