栈和队列(二) 队列操作详解及栈与队列的相互实现

矫情吗；* 2024-03-23 19:49 90阅读 0赞

#### 文章目录 ####

*  四、队列
 *   *  1、什么是队列
     *  2、队列的基本操作
     *   *  Queue.h
         *  Queue.c
         *   *  初始化队列
             *  队尾入队列
             *  队头出队列
             *  获取队列头部元素
             *  获取队列队尾元素
             *  获取队列中有效元素个数
             *  检测队列是否为空，如果为空返回非零结果，如果非空返回0
             *  销毁队列
 *  五、设计循环队列
 *  六、栈与队列的相互实现
 *   *  1、用栈实现队列
     *  2、用队列实现栈

栈操作实现：[栈和队列(一) 栈操作详解][Link 1]

![在这里插入图片描述][b88e1cc80d0c4d9c9349f4fcb48d5be7.png]

## 四、队列 ##

### 1、什么是队列 ###

队列就像是高速公路上的一个隧道一样，所有的车辆只允许从入口驶入，从出口驶出，先进先出，不允许逆行。

> 队列(queue)是一种线性数据结构，队列的元素只能**先入先出**(First In First Out，简称FIFO)。  
> **入队列**：进行插入操作的一端称为**队尾**  
> **出队列**：进行删除操作的一端称为**队头**

![在这里插入图片描述][7808351b154f4663bd1a6d2770a16be9.png]

### 2、队列的基本操作 ###

利用单链表来实现队列的基本操作

![在这里插入图片描述][49c7dfb304ea423fb5d7b11c978a58ad.png]

**代码结构设计：**

*  Queue.h: 存放队列结构及需要用到的头文件，函数声明等
 *  Queue.c: 各种操作函数的具体实现

#### Queue.h ####

#pragma once
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<stdbool.h>
    
    //方便修改数据类型
    typedef int QDataType;
    
    // 链式结构：表示队列 
    typedef struct QListNode
    {
        
    	struct QListNode* next;
    	QDataType data;
    }QNode;
    
    // 队列的结构 
    typedef struct Queue
    {
        
    	QNode* front;//队头
    	QNode* rear;//队尾
    }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 
    int QueueEmpty(Queue* q);
    // 销毁队列 
    void QueueDestroy(Queue* q);

#### Queue.c ####

#include "Queue.h"

##### 初始化队列 #####

void QueueInit(Queue* q)
    {
        
    	assert(q);
    
    	q->front = NULL;
    	q->rear = NULL;
    }

##### 队尾入队列 #####

void QueuePush(Queue* q, QDataType data)
    {
        
    	assert(q);
    	//创建一个节点放数据
    	QNode* newNode=(QNode*)malloc(sizeof(QNode));
    	if (newNode == NULL)
    	{
        
    		perror("malloc fail");
    		exit(-1);
    	}
    	newNode->data = data;
    	newNode->next = NULL;
    
    	//判断是否是第一个入队元素
    	if (q->rear == NULL)
    	{
        
    		q->front = q->rear = newNode;
    	}
    	else
    	{
        
    		q->rear->next= newNode;
    		q->rear = newNode;
    	}
    }

![在这里插入图片描述][29b48d85091f4e44ae16de1b0e34a765.png]

##### 队头出队列 #####

void QueuePop(Queue* q)
    {
        
    	assert(q);
    	assert(!QueueEmpty(q));
    
    	//判断是否只有一个元素
    	if (q->front->next == NULL)
    	{
        
    		free(q->front);
    		q->front = q->rear = NULL;
    	}
    	else
    	{
        
    		QNode* del = q->front;
    		q->front = q->front->next;
    		free(del);
    	}
    }

![在这里插入图片描述][714a3c9d0a484fa9ac3f0423f8e26df0.png]

##### 获取队列头部元素 #####

front是队头节点，它的数据便是队头元素

QDataType QueueFront(Queue* q)
    {
        
    	assert(q);
    	assert(!QueueEmpty(q));
    
    	return q->front->data;
    }

##### 获取队列队尾元素 #####

rear是队尾节点，它的数据便是队尾元素

QDataType QueueBack(Queue* q)
    {
        
    	assert(q);
    	assert(!QueueEmpty(q));
    
    	return q->rear->data;
    }

##### 获取队列中有效元素个数 #####

遍历一遍链表就能得到有效元素个数，也可以直接给队列的结构里加上一个size

int QueueSize(Queue* q)
    {
        
    	assert(q);
    
    	QNode* cur = q->front;
    	int size = 0;
    	while (cur)
    	{
        
    		cur = cur->next;
    		size++;
    	}
    	return size;
    }

##### 检测队列是否为空，如果为空返回非零结果，如果非空返回0 #####

int QueueEmpty(Queue* q)
    {
        
    	assert(q);
    
    	//队头节点为空说明队列为空
    	return q->front == NULL;
    }

##### 销毁队列 #####

void QueueDestroy(Queue* q)
    {
        
    	assert(q);
    
    	QNode* cur = q->front;
    	while (cur)
    	{
        
    		QNode* curNext = cur->next;
    		free(cur);
    		cur = curNext;
    	}
    
    	q->front = q->rear = NULL;
    }

## 五、设计循环队列 ##

> 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。  
> 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

**设计循环队列实现以下操作：**

*  MyCircularQueue(k): 构造器，设置队列长度为 k 。
 *  Front: 从队首获取元素。如果队列为空，返回 -1 。
 *  Rear: 获取队尾元素。如果队列为空，返回 -1 。
 *  enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
 *  deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
 *  isEmpty(): 检查循环队列是否为空。
 *  isFull(): 检查循环队列是否已满。

创建队列时多开辟一个空间来区分空和满  
如下是一个队列长度k=4的循环队列：  
![在这里插入图片描述][20060746a3a54796a6a2675c47bf3276.png]  
**用数组实现**

//循环队列结构
    typedef struct {
        
        int* a;
        int front;
        int rear;
        int k;
    } MyCircularQueue;

//初始化创建
    MyCircularQueue* myCircularQueueCreate(int k) {
        
        MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        //多开一个空间方便区分空和满
        obj->a=(int*)malloc(sizeof(int)*(k+1));
        obj->front=0;
        obj->rear=0;
        obj->k=k;
    
        return obj;
    }

//判断队列是否为空
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
        
        //当队头和队尾相等时队列为空
        return obj->front==obj->rear;
    }

//判断队列是否已满
    bool myCircularQueueIsFull(MyCircularQueue* obj) {
        
        return (obj->rear+1)%(obj->k+1)==obj->front;
    }

![在这里插入图片描述][8401c1b9c6234ef180102d27bf8011bd.png]

//入队
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
        
    //判断满了没
        if(myCircularQueueIsFull(obj))
        {
        
            return false;
        }
        
        obj->a[obj->rear]=value;
        obj->rear++;
    
        //特殊情况
        (obj->rear)%=(obj->k+1);
    
        return true;
    }

![在这里插入图片描述][a0ee98efc28a4e4991c0565eaf862064.png]

//出队
    bool myCircularQueueDeQueue(MyCircularQueue* obj) {
        
        //判断队列是不是空的
        if(myCircularQueueIsEmpty(obj))
        {
        
            return false;
        }
    
        obj->front++;
        特殊情况
        (obj->front)%=(obj->k+1);
        return true;
    }

![在这里插入图片描述][c40f7419f5b74706a4b10e5819189b82.png]

//获取队头元素
    int myCircularQueueFront(MyCircularQueue* obj) {
        
        if(myCircularQueueIsEmpty(obj))
        {
        
            return -1;
        }
        return obj->a[obj->front];
    }

//获取队尾元素
    //rear是队尾元素下一个元素的下标，所以队尾元素的下标为rear-1
    //但当rear等于0的时候队尾元素下标为k，需要特殊处理
    int myCircularQueueRear(MyCircularQueue* obj) {
        
        if(myCircularQueueIsEmpty(obj))
        {
        
            return -1;
        }
        // if(obj->rear==0)
        // {
        
        //     return obj->a[obj->k];
        // }else
        // {
        
        //     return obj->a[obj->rear-1];
        // }
        return obj->a[((obj->rear)+(obj->k))%(obj->k+1)];
    }

![在这里插入图片描述][eaeb1a84f7c544f5a8d6d56eee57fcbb.png]

//销毁队列
    void myCircularQueueFree(MyCircularQueue* obj) {
        
        free(obj->a);
        free(obj);
    }

## 六、栈与队列的相互实现 ##

### 1、用栈实现队列 ###

实现 MyQueue 类：

*  void push(int x) 将元素 x 推到队列的末尾
 *  int pop() 从队列的开头移除并返回元素
 *  int peek() 返回队列开头的元素
 *  boolean empty() 如果队列为空，返回 true ；否则，返回 false

**思路：**

用两个栈实现先入先出队列，当有元素入队时，就是在pushst入栈

![在这里插入图片描述][858475611b2c43a9a20f15c9580b5699.png]  
当出队时，将pushst中元素依次出栈放进popst中，然后对popst进行出栈操作

![在这里插入图片描述][09a6e84a4b314fbd8a9f6369557db702.png]

**代码实现：**

用的是前面自己实现的栈来实现的

typedef struct {
        
        ST pushst;
        ST popst;
    } MyQueue;
    
    
    MyQueue* myQueueCreate() {
        
        MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
        STInit(&obj->pushst);
        STInit(&obj->popst);
        return obj;
    }
    
    void myQueuePush(MyQueue* obj, int x) {
        
        STPush(&obj->pushst,x);
    }
    
    int myQueuePeek(MyQueue* obj) {
        
        if(STEmpty(&obj->popst))
        {
        
            while(!STEmpty(&obj->pushst))
            {
        
                STPush(&obj->popst,STTop(&obj->pushst));
                STPop(&obj->pushst);
            }
        }
        return STTop(&obj->popst);
    }
    
    
    int myQueuePop(MyQueue* obj) {
        
        int ret=myQueuePeek(obj);
        STPop(&obj->popst);
        return ret;
    }
    
    bool myQueueEmpty(MyQueue* obj) {
        
        return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
    }
    
    void myQueueFree(MyQueue* obj) {
        
        STDestroy(&obj->pushst);
        STDestroy(&obj->popst);
        free(obj);
    }

### 2、用队列实现栈 ###

实现 MyStack 类：

*  void push(int x) 将元素 x 压入栈顶。
 *  int pop() 移除并返回栈顶元素。
 *  int top() 返回栈顶元素。
 *  boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

**思路：**

用两个队列q1和q2来实现一个后入先出的栈

入栈：放进不为空的那个队列  
![在这里插入图片描述][9c4e8602c16d4896a70aec4d65226ca5.png]

出栈：不为空队列的前n-1个出队列插入空队列，删除剩下的一个即可

![在这里插入图片描述][2722de7f7c2647828ee79ecf10a53bb4.png]  
**代码实现：**

用的是前面自己实现的队列来实现的

typedef struct {
        
        Queue q1;
        Queue q2;
    } MyStack;
    
    
    MyStack* myStackCreate() {
        
        MyStack* p=(MyStack*)malloc(sizeof(MyStack));
        QueueInit(&p->q1);
        QueueInit(&p->q2);
    
        return p;
    }
    
    void myStackPush(MyStack* obj, int x) {
        
        if(!QueueEmpty(&obj->q1))
        {
        
            QueuePush(&obj->q1,x);
        }
        else
        {
        
            QueuePush(&obj->q2,x);
        }
    }
    
    int myStackPop(MyStack* obj) {
        
        Queue* empty=&obj->q1;
        Queue* noEmpty=&obj->q2;
        if(!QueueEmpty(&obj->q1))
        {
        
            empty=&obj->q2;
            noEmpty=&obj->q1;
        }
    
        while(QueueSize(noEmpty)>1)
        {
        
            QueuePush(empty,QueueFront(noEmpty));
            QueuePop(noEmpty);
        }
    
        int top=QueueFront(noEmpty);
        QueuePop(noEmpty);
    
        return top;
    }
    
    int myStackTop(MyStack* obj) {
        
        if(!QueueEmpty(&obj->q1))
        {
        
            return QueueBack(&obj->q1);
        }
        else
        {
        
            return QueueBack(&obj->q2);
        }
    }
    
    bool myStackEmpty(MyStack* obj) {
        
        return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    }
    
    void myStackFree(MyStack* obj) {
        
        QueueDestroy(&obj->q1);
        QueueDestroy(&obj->q2);
        free(obj);
    }

[Link 1]: https://blog.csdn.net/zcxyywd/article/details/132113392?spm=1001.2014.3001.5501
[b88e1cc80d0c4d9c9349f4fcb48d5be7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d90e98620a3e470aa196a0a00b7a23a7.png
[7808351b154f4663bd1a6d2770a16be9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/76fd57843b3a4bf2948c94a0d14c6b0b.png
[49c7dfb304ea423fb5d7b11c978a58ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8f93708129fd4a2ba6cc6f13daace41b.png
[29b48d85091f4e44ae16de1b0e34a765.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/19b27fdd2acc4f0fb8925e6c0722bab1.png
[714a3c9d0a484fa9ac3f0423f8e26df0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5d6437a06a9f4733a95f143266811ed1.png
[20060746a3a54796a6a2675c47bf3276.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/78e45bae301943e6b774b89256d4b6f8.png
[8401c1b9c6234ef180102d27bf8011bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/592e537a7c4a4e55bf774646558b9247.png
[a0ee98efc28a4e4991c0565eaf862064.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/26c56748377e4e4d8e44a896c83c1adb.png
[c40f7419f5b74706a4b10e5819189b82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/90be25dad9514f8c947d70eae00cf93e.png
[eaeb1a84f7c544f5a8d6d56eee57fcbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/de565e15557d40d4aee9184d237c817c.png
[858475611b2c43a9a20f15c9580b5699.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/292c98dd798a48128211a7c5e53caea6.png
[09a6e84a4b314fbd8a9f6369557db702.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7b2cfe29f61a4cf2beea2ac89e1d5abc.png
[9c4e8602c16d4896a70aec4d65226ca5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/65a41f128fe34541bacca83f6afd0445.png
[2722de7f7c2647828ee79ecf10a53bb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e95a2001670640ca9b04d56137ab3026.png