目录
1.队列
1.1队列的概念及结构
1.2 队列的实际应用联想
1.3队列的实现
2. 队列应用——队列实现栈
主要思路
1.队列
1.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为
队尾
出队列：进行删除操作的一端称为
队头
1.2 队列的实际应用联想
1. 基于队列的特点--先进先出，可以联想到大厅服务中的叫号机先到的先拿号，先拿号的先办业务，队列中的人是在等的人，办完业务为出队列，取号为如队列。
2. 也可以是查找和自己间接相关的人，像是查找qq好友的好友，开始自己在队列中，后来将自己出队列，将自己好友入队列，再将队列中的人出来，他们的好友再入队列，当然入队列的时候肯定有限制，不能是和之前重复的，以此类推，即可知道和自己外围相关的人，
注（仅为有代码新人的有端联想，不一定真正适合这些情况）
1.3队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
下面我们来实现队列：
分两个文件：Queue.h与Queue.c
Queue.h进行头文件和函数的声明，以及队列结构的创建
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//方便后面对不同数据的操作
typedef int QDataType;
//链式队列-队列结点结构体
typedef struct QListNode
{
QDataType _data;
struct QListNode* _pnext;
}QNode;
//队列结构体
typedef struct Queue
{
QNode* _phead;
QNode* _ptail;
int _size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
Queue.c进行队列相关函数的实现
#include "Queue.h"
//队列初始化
void QueueInit(Queue* pst)
{
assert(pst);
pst->_phead = pst->_ptail = NULL;
pst->_size = 0;
}
// 队尾入队列
void QueuePush(Queue* pst,QDataType x)
{
assert(pst);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->_data = x;
newnode->_pnext = NULL;
if (pst->_phead == NULL)
{
pst->_phead = pst->_ptail = newnode;
}
else
{
pst->_ptail->_pnext = newnode;
pst->_ptail = newnode;
}
pst->_size++;
}
// 队头出队列
void QueuePop(Queue* pst)
{
assert(pst);
assert(pst->_size);
QNode* next = pst->_phead->_pnext;
free(pst->_phead);
pst->_phead = next;
pst->_size--;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pst)
{
assert(pst);
assert(pst->_size);
return pst->_ptail->_data;
}
// 获取队列头部元素
QDataType QueueFront(Queue* pst)
{
assert(pst);
assert(pst->_size);
return pst->_phead->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pst)
{
assert(pst);
return pst->_size;
}
// 检测队列是否为空，如果为空返回True，如果非空返回False
bool QueueEmpty(Queue* pst)
{
assert(pst);
return pst->_size == 0;
}
// 销毁队列
void QueueDestroy(Queue* pst)
{
assert(pst);
QNode* cur = pst->_phead;
while (cur)
{
QNode* next = cur->_pnext;
free(cur);
cur = next;
}
pst->_size = 0;
pst->_phead = pst->_ptail = NULL;
}2. 队列应用——队列实现栈
225. 用队列实现栈 - 力扣（LeetCode）
题目：
我们用直接使用前队列的代码实现栈。
主要思路
创建两个队列相互导数据实现后进先出的效果，；压数据时直接在有数据的那个队列中插入数据，出栈时将有数据的队列中的size-1个数据导入另一个队列里，则第一个队列中剩下的那个数据是我们要出栈的数据，这就是主要思路。
下面是代码演示：（代码有点长但是前面的大部分都是前面实现队列的代码，直接复制粘贴的）
typedef int QDataType;
// 链式队列-队列结点结构体
typedef struct QListNode {
QDataType _data;
struct QListNode* _pnext;
} QNode;
// 队列结构体
typedef struct Queue {
QNode* _phead;
QNode* _ptail;
int _size;
} Queue;
// 队列初始化
void QueueInit(Queue* pst) {
assert(pst);
pst->_phead = pst->_ptail = NULL;
pst->_size = 0;
}
// 队尾入队列
void QueuePush(Queue* pst, QDataType x) {
assert(pst);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->_data = x;
newnode->_pnext = NULL;
if (pst->_phead == NULL) {
pst->_phead = pst->_ptail = newnode;
} else {
pst->_ptail->_pnext = newnode;
pst->_ptail = newnode;
}
pst->_size++;
}
// 队头出队列
void QueuePop(Queue* pst) {
assert(pst);
assert(pst->_size);
QNode* next = pst->_phead->_pnext;
free(pst->_phead);
pst->_phead = next;
pst->_size--;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pst) {
assert(pst);
assert(pst->_size);
return pst->_ptail->_data;
}
// 获取队列头部元素
QDataType QueueFront(Queue* pst) {
assert(pst);
assert(pst->_size);
return pst->_phead->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pst) {
assert(pst);
return pst->_size;
}
// 检测队列是否为空，如果为空返回True，如果非空返回False
bool QueueEmpty(Queue* pst) {
assert(pst);
return pst->_size == 0;
}
// 销毁队列
void QueueDestroy(Queue* pst) {
assert(pst);
QNode* cur = pst->_phead;
while (cur) {
QNode* next = cur->_pnext;
free(cur);
cur = next;
}
pst->_size = 0;
pst->_phead = pst->_ptail = NULL;
}
typedef struct {
Queue p1;
Queue p2;
} MyStack;
MyStack* myStackCreate() {
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&(st->p1));
QueueInit(&(st->p2));
return st;
}
void myStackPush(MyStack* obj, int x) {
if (!QueueEmpty(&(obj->p1))) {
QueuePush(&(obj->p1), x);
} else {
QueuePush(&(obj->p2), x);
}
}
int myStackPop(MyStack* obj) {
Queue* empty = &(obj->p1);
Queue* nonempty = &(obj->p2);
if (!QueueEmpty(empty)) {
empty = &(obj->p2);
nonempty = &(obj->p1);
}
while (QueueSize(nonempty) > 1) {
QueuePush(empty, QueueFront(nonempty));
QueuePop(nonempty);
}
int ret = QueueFront(nonempty);
QueuePop(nonempty);
return ret;
}
int myStackTop(MyStack* obj) {
if (!QueueEmpty(&obj->p1)) {
return QueueBack(&(obj->p1));
} else {
return QueueBack(&(obj->p2));
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&(obj->p1)) && QueueEmpty(&(obj->p2));
}
void myStackFree(MyStack* obj) {
QueueDestroy(&(obj->p1));
QueueDestroy(&(obj->p2));
free(obj);
}
各位看官姥爷点个赞再走吧，欢迎在评论区讨论。
