一、队列的概念
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
二、模拟实现顺序队列
我们可以用单链表模拟实现顺序队列。
队列采用的FIFO(first in first out),新元素(等待进入队列的元素)总是被插入到链表的尾部(对应单链表的尾插),而读取的时候总是从链表的头部开始读取。每次读取一个元素,释放一个元素(对应单链表的头删)。
对应的接口
注意又提供一种避免使用二级指针的方法,创建一个结构体变量,里面存储结点,当我们想要改变结构体里面的值,我们就用一级指针即可。
typedef int QDataType;
typedef struct QueueNode
{
//用单链表模拟实现队列
struct QueueNode* next;
QDataType data;
}QNode;
//新的避免二级指针的结构体
typedef struct Queue
{
QNode* head;
QNode* tail;
int sz;
}Que;
void QueueInit(Que* pq);
void QueueDestory(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueeuPop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);
队列的初始化:
void QueueInit(Que* pq)
{
assert(pq);
pq->sz = 0;
pq->head = pq->tail = NULL;
}
队列的销毁
注意free过后,也要指向空
void QueueDestroy(Que* pq)
{
assert(pq);
while (pq->sz > 0)
{
QNode* cur = pq->head->next;
free(pq->head);
pq->head = cur;
pq->sz--;
}
pq->tail = pq->head = NULL;
}
队列的插入数据
也就是单链表的尾插,同时也要注意当队列为空时的特殊情况。
void QueuePush(Que* pq,QDataType x)
{
//类似于尾插
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror(malloc);
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
pq->sz++;
}
else
{
pq->sz++;
pq->tail->next = newnode;
pq->tail = newnode;
}
}
队列的删除数据
也就是单链表的头删,同时也要注意只剩下一个结点删除后,尾结点指向空的情况
void QueeuPop(Que* pq)
{
assert(pq);
assert(pq->sz > 0);
//头删
//单独判断只剩下一个结点,头删后tail是野指针的情况
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
pq->sz--;
}
else
{
QNode* cur = pq->head;
pq->head = pq->head->next;
free(cur);
pq->sz--;
}
}
返回队列头数据
QDataType QueueFront(Que* pq)
{
assert(pq);
//assert(pq->head);
assert(!QueueEmpty(pq));
return pq->head->data;
}
返回队列尾数据
QDataType QueueBack(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
判断队列是否为空
bool QueueEmpty(Que* pq)
{
assert(pq);
return pq->head == NULL;
}
返回队列的数据个数
int QueueSize(Que* pq)
{
assert(pq);
//assert(pq->head);
return pq->sz;
}
三、模拟实现循环队列
622. 设计循环队列 - 力扣(LeetCode)
这实际上是把队列空间想象成一个环形空间,环形空间中的存储单元循环使用,用这种方法管理的队列也就称为循环队列。
注意本题结构较为复杂,必须要画图进行解决,这样就容易考虑到特殊情况,不容易出错。
本题用数组实现较为简单,如果用单链表实现,那么rear尾结点的前一个不好寻找。
那数组如何实现循环呢?
数组实现循环并不像单链表那样有一个next指针指向头结点,如果已经走向尾部,可以直接让头部的值等于尾部想要的值。
//如何用数组实现循环?
typedef struct {
int* a;
int front;
int rear;
int num;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* cur = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//用k+1个数组空间,便于判断空和满的情况。
cur->a = (int*)malloc(sizeof(int)*(k+1));
cur->front = 0;
cur->rear = 0;
cur->num = k;
return cur;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->front == obj->rear)
return true;
else
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
//两种情况都要考虑到!
if(obj->front-obj->rear == 1 || obj->rear-obj->front == obj->num)
return true;
else
return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//先判断是否已经满
if(myCircularQueueIsFull(obj) == true)
return false;
//假设rear在队列的尾部
if(obj->rear == obj->num)
{
obj->a[obj->rear] = value;
obj->rear = 0;
}
else
{
obj->a[obj->rear] = value;
obj->rear++;
}
//obj->a[obj->rear] = value;
//obj->rear++;
//obj->rear %= (obj->num+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//先判断是否已经空了
if(myCircularQueueIsEmpty(obj) == true)
{
return false;
}
//假设front在队列的尾部
if(obj->front == obj->num)
obj->front = 0;
else
obj->front++;
//++obj->front;
//obj->front %= (obj->num+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj) == true)
return -1;
else
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
//注意队尾的rear比数据提前一位数,所以是rear-1
//但要考虑rear-1的情况
if(myCircularQueueIsEmpty(obj) == true)
return -1;
if(obj->rear == 0)
{
//需要再创建一个临时变量,不能改变rear的值
int tmp = obj->num;
return obj->a[tmp];
}
// else
// return obj->a[(obj->rear+obj->num)%(obj->num+1)];
return obj->a[obj->rear-1];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
四、用队列实现栈
225. 用队列实现栈 - 力扣(LeetCode)
本题要求用两个队列实现栈,两个队列我们就可以互相倒数据,来满足题目对栈的需求!
思路:
入队列:
入不为空的队列
出队列:
利用队列的性质将前n-1个数据放入另一个空的队列中,删除剩下一个数据,这样就完成栈的pop操作!
代码:
typedef struct {
Que q1;
Que q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* cur = (MyStack*)malloc(sizeof(MyStack));
//不能忘记初始化
QueueInit(&cur->q1);
QueueInit(&cur->q2);
return cur;
}
void myStackPush(MyStack* obj, int x) {
//push到不为空的的队列中
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
//先假设q1不为空,q2为空
Que* empty = &obj->q1;
Que* nonEmpty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
//如果假设失败,相反
empty = &obj->q2;
nonEmpty = &obj->q1;
}
while(QueueSize(nonEmpty)>1)
{
//开始用函数进行捯数据
//从前往后的顺序是根据队列pop的顺序定的
QueuePush(empty,QueueFront(nonEmpty));
QueuePop(nonEmpty);
}
int top = QueueBack(nonEmpty);
QueuePop(nonEmpty);
return top;
}
int myStackTop(MyStack* obj) {
Que* empty = &obj->q1;
Que* nonEmpty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
//如果假设失败,相反
empty = &obj->q2;
nonEmpty = &obj->q1;
}
return QueueBack(nonEmpty);
}
bool myStackEmpty(MyStack* obj) {
//判断两个队列
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
//先对两个队列中的链表进行free
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
五、用栈实现队列
232. 用栈实现队列 - 力扣(LeetCode)
题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):文章来源:https://www.toymoban.com/news/detail-647462.html
思路:
本题与上一题用队列实现栈有所差别,可以直接区分push栈和pop栈,如果pop栈为空,就将push栈全部捯到pop栈!文章来源地址https://www.toymoban.com/news/detail-647462.html
代码:
typedef struct
{
ST push;
ST pop;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* cur = (MyQueue*)malloc(sizeof(MyQueue));
SLInit(&cur->push);
SLInit(&cur->pop);
return cur;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->push,x);
}
int myQueuePop(MyQueue* obj) {
int ret = myQueuePeek(obj);
STPop(&obj->pop);
return ret;
}
int myQueuePeek(MyQueue* obj) {
//出栈只能从后往前出
//如果pop栈为空,就将push栈全部捯到pop栈!
if(STEmpty(&obj->pop))
{
while(!STEmpty(&obj->push))
{
STPush(&obj->pop,STTop(&obj->push));
STPop(&obj->push);
}
}
int ret = STTop(&obj->pop);
return ret;
}
bool myQueueEmpty(MyQueue* obj) {
//用函数求解
return STEmpty(&obj->push) && STEmpty(&obj->pop);
}
void myQueueFree(MyQueue* obj) {
SLDestroy(&obj->pop);
SLDestroy(&obj->push);
free(obj);
}
到了这里,关于数据结构之队列详解(包含例题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!