数据结构之队列_数据结构队列

目录

一、队列的概念

二、队列的实现

 (1)问题1：结构体和指针变量传参

(2)初始化

(3)销毁队列

(4)入队

(5)出队

(6)获取队头元素

(7)获取队尾元素

(8)获取队列长度

(9)判断是否为空队列

(10)创建新节点

(11)相当于打印队列中的元素

 总代码：

Queue.h

Queue.c

test.c

三、用队列实现栈

 四、用栈实现队列

---

一、队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出(FIFO)的原则。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为对头

如图：

二、队列的实现

队列既可以用数组和也可以用链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，每次删除队头，后面的元素就要向前移动，所以效率比较低

 (1)问题1：结构体和指针变量传参

  1.当我们创建的只是一个指针变量的时候，如果我们要改变这个指针变量，那么我们需要传二级指针

比如：单链表，初始创建的是一个节点的指针变量，那我们如果需要改变这个指针变量，那么传的就是这个指针变量的地址。

2.但如果我们在初始定义一个结构体，里面存放着俩个指针， 那当我们需要改变这个结构体的内容时，我们传的是这个结构体的地址。

比如：   

 

 个人总结：改变指针所指向内容和指针方向的传地址，不改变指针所指向的内容和方向的传本身。即改变什么就要传它的地址，比如，要改变结构体，那么就要传结构体的地址。

(2)初始化

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

(3)销毁队列

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);//此处说明传过来的队列不能为空，为空说明传错了
	QueueNode* cur= pq->front;
	//删除，直到为NULL
	while (cur != NULL)
	{
		//先保存下一个节点
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//到这，说明删除成功
	pq->front = pq->rear = NULL;
}

(4)入队

分为俩种情况：

第一种情况:对头和队尾都指向NULL

第二种情况：一个节点或者多个节点时，可以直接插入在队尾后面

void QueuePush(Queue* pq, DataType x)
{
	assert(pq); 
	QueueNode* newnode = BuyNode(x);
	//对头和队尾都指向NULL的情况
	if (pq->front == NULL && pq->rear == NULL)
	{
		pq->front = newnode;
		pq->rear = newnode;
	}
	//如果只有一个节点的情况或者多个节点的情况
	else
	{
		pq->rear->next = newnode;
		pq->rear = newnode;
	}
}

(5)出队

思路：

1.先保存对头的下一个节点，然后将对头删除，再将保存的节点赋值给对头，并且只有当对头不为NULL的时候才可以继续删除
2.当队头为NULL的情况下，则会有问题
3.特殊情况：如果front指向rear时，将rear的空间释放了，front指向了空，而rear还是指向那个空间，则会造成野指针，所以这时的处理是当front为空时，将front也置为空

void QueuePop(Queue* pq)
{
	assert(pq);
	//如果队列为空的情况
	//方式一：
	/*assert(pq->front);*/
	//方式二：
	assert(!QueueEmpty(pq));
 
	//只有对头不为NULL的时候才可以继续删除
	QueueNode* Next = pq->front->next;
	free(pq->front);
	pq->front = Next;
    //特殊情况：
	if (pq->front == NULL)
	{
		pq->rear = NULL;
	}
}

(6)获取队头元素

//获取队头的元素
DataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->front->data;
}

(7)获取队尾元素

//获取队尾的元素
DataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->rear->data;
}

(8)获取队列长度

//获取队列的长度
int QueueSize(Queue* pq)
{
	assert(pq);
	int count = 0;
	QueueNode* cur = pq->front;
	while (cur != NULL)
	{
		count++;
		cur = cur->next; 
	}
	return count;
}

(9)判断是否为空队列

//队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->front == NULL;
}

(10)创建新节点

//创建新节点
QueueNode* BuyNode(DataType x)
{
	QueueNode* temp= (QueueNode*)malloc(sizeof(QueueNode));
	if (temp == NULL)
	{
		printf("BuyNode failed");
		exit(-1);
	}
	temp->data = x;
	temp->next = NULL;
	return temp;
}

(11)相当于打印队列中的元素

//相当于打印队列中的元素
//1.队列不为空，打印队头元素，删除多头元素，然后队头指向下一个节点，直到队列为空
void QueuePrint(Queue* pq)
{
	while (!QueueEmpty(pq))
	{
		//获取队头元素
		DataType front = QueueFront(pq);
		//打印队头元素
		printf("%d\n",front);
		//删除队头，即出队
		QueuePop(pq);
	}
}

 初始值：

 运行结果：

 总代码：

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<malloc.h>
#include<stdbool.h>
typedef int DataType;
typedef struct QueueNode
{
	DataType data;
	struct QueueNode* next;
}QueueNode;
 
//再给队列定义一个对头和队尾
typedef struct Queue
{
	QueueNode* front;
	QueueNode* rear;
}Queue;
 
 
//创建新节点
QueueNode* BuyNode(DataType x);
void QueueInit(Queue* pq);//传过去的是结构体的地址
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,DataType x);
void QueuePop(Queue* pq);
//获取对头的元素
DataType QueueFront(Queue* pq);
//获取队尾的元素
DataType QueueBack(Queue* pq);
//获取队列的长度
int QueueSize(Queue* pq);
//队列是否为空
bool QueueEmpty(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
 
#include"Queue.h"
 
//创建新节点
QueueNode* BuyNode(DataType x)
{
	QueueNode* temp= (QueueNode*)malloc(sizeof(QueueNode));
	if (temp == NULL)
	{
		printf("BuyNode failed");
		exit(-1);
	}
	temp->data = x;
	temp->next = NULL;
	return temp;
}
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->front = pq->rear = NULL;
}
 
//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);//此处说明传过来的队列不能为空，为空说明传错了
	QueueNode* cur= pq->front;
	//删除，直到为NULL
	while (cur != NULL)
	{
		//先保存下一个节点
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//到这，说明删除成功
	pq->front = pq->rear = NULL;
}
//入队
void QueuePush(Queue* pq, DataType x)
{
	assert(pq); 
	QueueNode* newnode = BuyNode(x);
	//对头和队尾都指向NULL的情况
	if (pq->front == NULL && pq->rear == NULL)
	{
		pq->front = newnode;
		pq->rear = newnode;
	}
	//如果只有一个节点的情况或者多个节点的情况
	else
	{
		pq->rear->next = newnode;
		pq->rear = newnode;
	}
}
//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	//如果队列为空的情况
	//方式一：
	/*assert(pq->front);*/
	//方式二：
	assert(!QueueEmpty(pq));
 
	//只有对头不为NULL的时候才可以继续删除
	QueueNode* Next = pq->front->next;
	free(pq->front);
	pq->front = Next;
	//特殊情况
	if (pq->front == NULL)
	{
		pq->rear = NULL;
	}
}
//获取队头的元素
DataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->front->data;
}
//获取队尾的元素
DataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->rear->data;
}
//获取队列的长度
int QueueSize(Queue* pq)
{
	assert(pq);
	int count = 0;
	QueueNode* cur = pq->front;
	while (cur != NULL)
	{
		count++;
		cur = cur->next; 
	}
	return count;
}
//队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->front == NULL;
}
 
//相当于打印队列中的元素
//1.队列不为空，打印队头元素，删除多头元素，然后队头指向下一个节点，直到队列为空
void QueuePrint(Queue* pq)
{
	while (!QueueEmpty(pq))
	{
		//获取队头元素
		DataType front = QueueFront(pq);
		//打印队头元素
		printf("%d\n",front);
		//删除队头，即出队
		QueuePop(pq);
	}
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
 
#include"Queue.h"
 
void QueueTest()
{
	Queue q ;//创建一个结构体
	//那么想要改变这个结构体，就要传结构体的指针
	QueueInit(&q);
 
	QueuePush(&q,1);
	QueuePush(&q,2);
	QueuePush(&q,3);
	QueuePush(&q,4);
 
	QueuePrint(&q);
 
	//printf("%d", QueueSize(&q));
	//QueuePop(&q);
	//printf("%d\n", QueueFront(&q));
	//QueuePop(&q);
	//printf("%d\n", QueueFront(&q));
	//QueuePop(&q);
	//printf("%d\n", QueueFront(&q));
	QueuePop(&q);
	printf("%d", QueueFront(&q));
	//QueuePush(&q, 3);
	//printf("%d\n", QueueBack(&q));
	//QueuePush(&q, 4);
	//printf("%d\n", QueueBack(&q));
	QueueDestroy(&q);
 
}
 
int main()
{
	QueueTest();
	return 0;
}

三、用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)

题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

思路:

1.入数据时，向不为空的队列中入，保持另一个队列为空
2.出数据时，一次出对头的数据，转移到另一个队列中保存，只剩下最后一个数据时，删除

注意点：不能去改变队列结构，只能调用队列提供的接口函数实现

图解：
 

 代码：

因为C语言不能直接使用队列及队列的相关操作，所以必须先创建一个队列及其操作函数

//栈的相关接口函数
typedef int DataType;
typedef struct QueueNode
{
	DataType data;
	struct QueueNode* next;
}QueueNode;
 
//再给队列定义一个对头和队尾
typedef struct Queue
{
	QueueNode* front;
	QueueNode* rear;
}Queue;
 
 
//创建新节点
QueueNode* BuyNode(DataType x);
void QueueInit(Queue* pq);//传过去的是结构体的地址
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,DataType x);
void QueuePop(Queue* pq);
//获取对头的元素
DataType QueueFront(Queue* pq);
//获取队尾的元素
DataType QueueBack(Queue* pq);
//获取队列的长度
int QueueSize(Queue* pq);
//队列是否为空
bool QueueEmpty(Queue* pq);
//创建新节点
QueueNode* BuyNode(DataType x)
{
	QueueNode* temp= (QueueNode*)malloc(sizeof(QueueNode));
	if (temp == NULL)
	{
		printf("BuyNode failed");
		exit(-1);
	}
	temp->data = x;
	temp->next = NULL;
	return temp;
}
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->front = pq->rear = NULL;
}
 
//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);//此处说明传过来的队列不能为空，为空说明传错了
	QueueNode* cur= pq->front;
	//删除，直到为NULL
	while (cur != NULL)
	{
		//先保存下一个节点
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//到这，说明删除成功  
	pq->front = pq->rear = NULL;
}
//入队
void QueuePush(Queue* pq, DataType x)
{
	assert(pq); 
	QueueNode* newnode = BuyNode(x);
	//对头和队尾都指向NULL的情况
	if (pq->front == NULL && pq->rear == NULL)
	{
		pq->front = newnode;
		pq->rear = newnode;
	}
	//如果只有一个节点的情况或者多个节点的情况
	else
	{
		pq->rear->next = newnode;
		pq->rear = newnode;
	}
}
//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	//如果队列为空的情况
	//方式一：
	/*assert(pq->front);*/
	//方式二：
	assert(!QueueEmpty(pq));
 
	//只有对头不为NULL的时候才可以继续删除
	QueueNode* Next = pq->front->next;
	free(pq->front);
	pq->front = Next;
	//特殊情况
	if (pq->front == NULL)
	{
		pq->rear = NULL;
	}
}
//获取队头的元素
DataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->front->data;
}
//获取队尾的元素
DataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->rear->data;
}
//获取队列的长度
int QueueSize(Queue* pq)
{
	assert(pq);
	int count = 0;
	QueueNode* cur = pq->front;
	while (cur != NULL)
	{
		count++;
		cur = cur->next; 
	}
	return count;
}
//队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->front == NULL;
}
 
//相当于打印队列中的元素
//1.队列不为空，打印队头元素，删除多头元素，然后队头指向下一个节点，直到队列为空
void QueuePrint(Queue* pq)
{
	while (!QueueEmpty(pq))
	{
		//获取队头元素
		DataType front = QueueFront(pq);
		//打印队头元素
		printf("%d\n",front);
		//删除队头，即出队
		QueuePop(pq);
	}
}
 
//建立栈结构体，栈中存放着俩个队列
typedef struct
{
    //创建俩个队列
    Queue q1;
    Queue q2;
} MyStack;
 
 
//创建栈的空间，为队列初始化，最后返回该栈
MyStack* myStackCreate() 
{
    MyStack* st= (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}
 
void myStackPush(MyStack* obj, int x) 
{
    //如果不为空就插入
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
 
//将不为空的队列前n-1个转移到另一个队列，最后一个删除，并返回其元素，删除队列最后一个元素，就相当于删除栈顶元素
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;
}
 
//q1和q2哪个队列不为空，就返回它的队尾元素，因为另一个队列为空
int myStackTop(MyStack* obj) 
{
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
 
//栈为空，将相当于q1和q2都为空时
bool myStackEmpty(MyStack* obj) 
{
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
 
//销毁栈，就相当于将malloc出的，free掉，q1和q2节点都是队列的对头，其每一个节点都是malloc出来的，并且栈也是malloc出来的，也要一并free掉
void myStackFree(MyStack* obj) 
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}
 
/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

 运行结果：

 四、用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

思路：
将元素都入到PushST,出栈从PopST中出栈,当PopST中没有元素可以出栈时,将PushST中的元素导入到PopST中,再出栈，出栈的顺序与队列的出队顺序一致。

注意点：不能去改变栈的结构，只能调用栈提供的接口函数实现

图解：

 代码：

typedef int DataType;
typedef struct Stack
{
	DataType* a;//a相当于一个数组
	int top;
	int capacity;
}ST;
 
//初始化
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//入栈
void StackPush(ST* ps,DataType x);
//出栈
void StackPop(ST* ps);
//获取栈顶元素
DataType StackTop(ST* ps);
//获取栈中有效元素
int StackSize(ST* ps);
//检测栈是否为空
bool StackEmpty(ST* ps);
//遍历栈
void StackPrint(ST* ps);
//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//ps->top = -1;
	ps->capacity = 0;
}
//入栈
void StackPush(ST* ps, DataType x)
{
	assert(ps);
	//考虑如果容量不够的情况
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		DataType* tmp =realloc(ps->a,newcapacity * sizeof(DataType));//就是a是一指针，每次访问4个字节，第一次扩了4个 4字节
		if (tmp == NULL)
		{
			printf("realloc failed");
			exit(-1);
		}
		//更新
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
//销毁栈
void StackDestroy(ST* ps) 
{
	//将数组的指针释放掉即可
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
//删除数据
void StackPop(ST* ps)
{
	assert(ps);
	//写法一：
	/*assert(ps->top > 0);*///top == 1 表示,容量为1,栈顶指针指向0，top == 0表示容量为0，栈顶指针为-1，栈为NULL
	//写法二：
	assert(!StackEmpty(ps));
	ps->top--;
}
//获取栈顶元素
DataType StackTop(ST* ps)
{
	assert(ps);
	//方式一：
	/*assert(ps->top > 0);*/
	//方式二：
	assert(!StackEmpty(ps));
	return ps->a[ps->top-1];
}
//检测栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	//写法一：
	//if (ps->top == 0)
	//{
	//	return true;
	//}
	//else
	//	return false;
	//写法二：
	return ps->top == 0;//top == 0，为1，表示栈为空
}
//获取栈中有效元素
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top为1，容量为1，如栈顶指向0，top指向他的上一个，也就是1，此时容量为1
}
 
//遍历栈
void StackPrint(ST* ps)
{
	//遍历栈
	while (!StackEmpty(ps))//栈不为空
	{
		printf("%d ", StackTop(ps));
		//删除栈顶元素，top--,也就是先将栈顶元素出栈，然后top--，访问下一个
		StackPop(ps);
	}
}
 
typedef struct 
{
    //创建俩个栈
    ST PushST;
    ST PopST;
} MyQueue;
 
 
MyQueue* myQueueCreate() 
{
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&queue->PushST);
    StackInit(&queue->PopST);
    return queue;
}
 
void myQueuePush(MyQueue* obj, int x) 
{
    StackPush(&obj->PushST,x);
}
 
int myQueuePop(MyQueue* obj) 
{
    //如果PopST没有数据，就PushST的数据导过去
   if(StackEmpty(&obj->PopST))
   {
       while(!StackEmpty(&obj->PushST))
       {
            StackPush(&obj->PopST,StackTop(&obj->PushST));
            StackPop(&obj->PushST);
       }
   }
   int front = StackTop(&obj->PopST);
   StackPop(&obj->PopST);
   return front; 
}
 
int myQueuePeek(MyQueue* obj) 
{
   //如果PopST中没有数据了，就将PushST中的数据导入过去，就符合队列的顺序了
    if(StackEmpty(&obj->PopST))
   {
       while(!StackEmpty(&obj->PushST))
       {
            StackPush(&obj->PopST,StackTop(&obj->PushST));
            StackPop(&obj->PushST);
       }
   }
   return StackTop(&obj->PopST);
}
 
bool myQueueEmpty(MyQueue* obj) 
{
    return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}
 
void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->PushST);
    StackDestroy(&obj->PopST);
    free(obj);
}
 
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

运行结果:

循环队列详见下一篇博客，本篇如有问题，请在评论区多多评论哈^_^