【数据结构】栈和队列（队列的基本操作和基础知识）

🌈个人主页：秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏：《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482

​

目录

 前言

  队列

队列的概念和结构

 队列的实现

单链表队列的实现

总的声明

初始化

销毁

插入

删除

取队头

取队尾

判断是否为空

返回队列数据个数

队列的一对一关系

---

 前言

    💬 hello! 各位铁子们大家好哇。

              这是2024年的第一篇博客。
    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

  队列

队列的概念和结构

​

 队列的实现

队列也有数组队列和链式队列。队列的特点是先进先出。实现时，数组队列，不适合头删。双向链表需要多个指针，因此，这里选择使用单链表实现。

单链表队列的实现

总的声明

typedef int QDataType;
typedef struct QueueNode
{	QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int	QueueSize(Queue* pq);

初始化

​

上方的Push函数是有问题的，因为队列的特点是队尾进，队头出。所以插入时是尾插，单链表不好找队尾，就需要一个指向队尾的指针。因为我们的单链表是不带头节点的， 所以传一级指针也是有问题的。

解决方法：

​

我们将两个一级指针都放在结构体中，传参时传这个结构体指针，这样只需要传一级指针。因为改变phead和ptail时，我们改的是结构体的内容，传结构体指针即可。

下方是初始化代码：

typedef int QDataType;
typedef struct QueueNode
{	QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

销毁

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

插入

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail == NULL){pq->ptail = pq->phead = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

删除

void QueuePop(Queue* pq) 
{assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL){pq->ptail = NULL;	}pq->size--;
}

取队头

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

取队尾

QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

判断是否为空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

返回队列数据个数

int	QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

队列的一对一关系

队列的特点是先进先出，与栈不同。入队的顺序只有一种，出队的顺序也只有一种。