数据结构学习心得——顺序队和链队-蒲公英云

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

队列的定义

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

顺序队和链队

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

这里写图片描述

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

这里写图片描述

顺序队和链队的代码实现

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

#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;
}