移动端app下载_可以自己画设计图的app_手机百度网页版入口_网络营销策略存在的问题

1.队列的概念

1.1 栈也是一种特殊的线性表。

1.2 栈和队列的区别：

（1）几端
在栈中，出数据和入数据都是在固定的一端（栈顶）。而在队列中(两端)，出数据在一端，入数据在另一端 。

（2）先后
栈：先进后出
队列：先进先出 （意思是先进来的元素，从它开始出去）

1.3 入和出

入队列：插入数据----->这一端称为队尾
出队列：删除数据----->这一端称为队头

两端都需要操作，所以两头都是空的。

1.4 底层

栈的底层是数组，队列的底层是什么呢？（单链表）

2. 队列的操作

2.1 队列的定义

之前学习的其余类型，只需要一个结构体就可以定义好。但是队列需要两个结构体嵌套使用才可以。

定义队列需要一个结构体（里面是头phead和尾ptail），队列里面的数据是一个一个的结点类型（所以需要有结点类型的结构:里面保存了数据+下一个结点地址）。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Datatype;//定义队列结点的结构
typedef struct QueueNode
{Datatype data;struct QueueNode* next;
}QueueNode;
//定义队列的结构
typedef struct Queue
{struct QueueNode* phead;  //对头删(出)struct QueueNode* ptail;  //队尾插(入)
}Queue;

2.2 队列的初始化Init

初始化时，phead和ptail都置为空。

2.3 入队列

如果队列为空，那么新插入的结点既是phead，又是ptail。
如果队列不为空，新插入的结点在ptail之后即可。

void QueuePush(Queue* pq, Datatype x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//记得给新结点初始化（赋值）newnode->data = x;newnode->next = NULL;if (newnode == NULL){perror("malloc fail!");exit(1);}if (pq->phead == NULL) //队列为空{pq->phead = pq->ptail = newnode;}else if (pq->phead != NULL) //队列不为空{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}
}

2.4 出队列

出队列，想要把队头的那个数据出掉，需要先把第二个数据保存下来（否则等一会找不到新的队头了），存下之后再将phead释放掉。

在出队列时要考虑队列是否为空。
队列为空：不能出数据。
队列不为空：ok

还需要判断是否只剩下一个结点：只剩下一个指针，头结点指向下一个，即NULL。那尾结点怎么办，将会成为野指针。x

如果只有一个结点，将头尾释放即可。

//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead&& pq->ptail == NULL;
}
//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//队列不为空且结点大于1个，继续出队列QueueNode* next = pq->phead->next;free(pq->phead);pq->phead->data = pq->phead->next = NULL;pq->phead = next;//不要忘记让phead等于下一个结点}
}

2.5 取队头数据

对头数据是QueueNode里的data，类型是Datatype。所以这个函数的返回类型是Datatype。

Datatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}

2.6 取队尾数据

Datatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}

2.7 获取队列有效元素的个数

通过循环来求得个数–可以。
还可以在队列的结构中加入:int size;在入队列时size++，出队列时size–。这样子最后得到的size就是元素个数了。

typedef struct Queue
{struct QueueNode* phead;struct QueueNode* ptail;int size;  //记录个数
}Queue;

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

2.8 销毁队列