DS初阶：栈和队列的相互实现

栈和队列的相互实现是用两个栈去实现队列或者是用两个队列去实现栈，这样其实是把问题复杂化的，实际中没有什么应用价值，但是通过他们的相互实现可以让我们更加深入地理解栈和队列的特点

Carroll Chen

3014人浏览 · 2024-02-19 20:06:37

Carroll Chen · 2024-02-19 20:06:37 发布

创作不易，感谢友友们三连！！

一、前言

栈和队列的相互实现是用两个栈去实现队列或者是用两个队列去实现栈，这样其实是把问题复杂化的，实际中没有什么应用价值，但是通过他们的相互实现可以让我们更加深入地理解栈和队列的特点，而我也是用两道相关的OJ题来分析这个过程！

二、用两个队列实现栈

力扣：队列实现栈

2.1 思路

2.2 代码实现

2.2.1 队列的代码

我们先把队列的实现声明放这

Queue.h

#include<stdbool.h>
#include<assert.h>
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{
	QDatatype data;//存储数据
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;//指向队头，用于出队（头删）
	QNode* ptail;//指向队尾，用于入队（尾插）
	int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
void QueueInit(Queue* pq);//队列的初始化
void QueuePush(Queue* pq, QDatatype x);//队列的入队（尾插）
void QueuePop(Queue* pq);//队列的出队(头删)
QDatatype QueueFront(Queue* pq);//获取队列头部元素
QDatatype QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueDestory(Queue* pq);//队列的销毁

2.2.2 结构体的创建

封装一个myStack结构体管理两个队列

typedef struct MyStack
{
	Queue q1;
	Queue q2;
} MyStack;
//用两个队列实现栈，构建一个结构体去管理这两个队列

2.2.3 初始化栈

初始化栈，相当于先构建栈的结构体变量，然后再初始化他的两个队列成员

MyStack* myStackCreate() //返回一个MySack类型的指针
{
	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
	if (obj == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
//如果开辟成功，对栈初始化相当于对栈结构体中的两个队列初始化
	QueueInit(&obj->q1);
	QueueInit(&obj->q2);
	return obj;
}

2.2.4 模拟压栈

按照我们之前的思路，压栈直接找到不为空的队列尾插就行

void myStackPush(MyStack* obj, int x)
//压栈前必须在不为空的队列中压栈
{
	if (!QueueEmpty(&obj->q1))//如果q1不为空压q1
		QueuePush(&obj->q1, x);
	else//如果q1为空，则压q2
		QueuePush(&obj->q2, x);
}

2.2.5 模拟出栈并返回栈顶元素

按照之前的思路，出栈就是先找到非空的队列，移除到空的队列上，只留下最后一个元素，再头删

int myStackPop(MyStack* obj)
//出栈，必须找到不为空的队列，然后将该队列的元素倒倒另一个队列中，知道只剩最后一个元素的时候，就删除
{
	//要找到不为空的队列进行操作，所以先假设一个为空一个不为空，如果给个条件判断
	Queue* Emptyq = &obj->q1;
	Queue* NonEmptyq = &obj->q2;
	if (!QueueEmpty(&obj->q1))//错了的话就认个错然后换回来
	{
		 NonEmptyq = &obj->q1;
		 Emptyq = &obj->q2;
	}
	//开始导数据
	while (QueueSize(NonEmptyq) > 1)
	{
	//将队列头的元素倒进去另一个队列，在出栈
		QueuePush(Emptyq, QueueFront(NonEmptyq));//压栈
		QueuePop(NonEmptyq);//倒入一个就将非空队列出队列一个
	}
	//倒完后只剩一个数据了，先记录返回值再删除
	int top = QueueFront(NonEmptyq);
	QueuePop(NonEmptyq);
	return top;
}

2.2.6 获取栈顶元素

找到不为空的队列，然后获取队列尾的元素，就是获取栈顶元素

int myStackTop(MyStack* obj)
//找到不为空的队列，然后获取队列尾的元素，相当于获取栈顶元素
{
	if (!QueueEmpty(&obj->q1))//如果q1不为空取q1队尾
		return QueueBack(&obj->q1);
	else//如果q2不为空取q2队尾
		return QueueBack(&obj->q2);
}

2.2.7 判断栈是否为空

判断栈是否为空，本质上就是判断两个队列是否为空

bool myStackEmpty(MyStack* obj) //栈为空当且仅当两个队列都为空
{
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

2.2.8 释放栈

要先释放掉栈的队列成员的空间，然后再释放栈的空间，并置空

void myStackFree(MyStack* obj) 
{
	//释放obj前一定也要将q1和q2的空间释放了
	QueueDestory(&obj->q1);
	QueueDestory(&obj->q2);
	free(obj);
	//obj = NULL;没用，一级指针接受指针相当于值传递
	//要手动在main函数中置空
}

值得注意的是，这边给obj置空是没有的，要想改变obj必须用二级指针，所以我们最后要释放的话要在程序的最后自己手动释放。

2.3 全部代码

2.3.1 queue.h

#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{
	QDatatype data;//存储数据
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;//指向队头，用于出队（头删）
	QNode* ptail;//指向队尾，用于入队（尾插）
	int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
void QueueInit(Queue* pq);//队列的初始化
void QueuePush(Queue* pq, QDatatype x);//队列的入队（尾插）
void QueuePop(Queue* pq);//队列的出队(头删)
QDatatype QueueFront(Queue* pq);//获取队列头部元素
QDatatype QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueDestory(Queue* pq);//队列的销毁

2.3.2 queue.c

#include"Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);//判断传的是不是空指针
	pq->phead = pq->ptail = NULL;
	pq->size = 0;//因为队列不像栈一样，有一个top表示栈顶元素的下标
	//所以如果我们想知道这个队列的有效数据个数，就必须遍历队列
	//由于其先进先出的特性，我们默认只能访问到头元素和尾元素
	//所以必须访问一个头元素，就出队列一次，这样才能实现遍历
	//但是这样的代价太大了，为了方便，我们直接用size
}
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	//入队必须从队尾入！
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点
	if (newnode == NULL)//如果新节点申请失败，退出程序
	{
		perror("malloc fail");
	}
	//新节点创建成功，给新节点初始化一下
	newnode->data = x;
	newnode->next = NULL;
	//开始入队
	//如果直接尾插的话，由于会用到ptail->next,所以得考虑队列为空的情况
	if (pq->ptail == NULL)//如果为空，直接把让新节点成为phead和ptail
	{
		//按道理来说，如果ptail为空，phead也应该为空
		// 但是有可能会因为我们的误操作使得phead不为空，这个时候一般是我们写错的问题
		//所以使用assert来判断一下，有问题的话会及时返回错误信息
		assert(pq->phead == NULL);
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	//如果队列为空，没有删除的必要
	assert(!QueueEmpty(pq));
	//队列中的出队列相当于链表的头删
	//如果直接头删，那么如果队列只有一个有效数据的话，那么我们将phead的空间释放掉，但是没有将ptail给置空
	//这样会导致ptail成为一个野指针，所以我们需要考虑只有一个节点多个节点的情况
	if (pq->phead->next == NULL)//一个节点的情况,直接将这个节点释放并置空即可
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;//置空，防止野指针
	}
	else//多个节点的情况，直接头删

	{
		QNode* next = pq->phead->next;//临时指针记住下一个节点
		free(pq->phead);
		pq->phead = next;//让下一个节点成为新的头
	}
	pq->size--;
}

QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//队列如果为空，则不可能找得到队列头元素
	//队列不为空的时候，直接返回phead指向的数据
	return pq->phead->data;
}

QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//队列如果为空，则不可能找得到队尾元素
	//队列不为空的时候，直接返回ptail指向的数据
	return pq->ptail->data;
}

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

bool QueueEmpty(Queue* pq)//链表为空的情况，可以根据容量，也可以根据ptail==NULL&&phead==NULL
{
	assert(pq);
	return pq->phead == NULL && pq->ptail == NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);//判断传的是不是空指针
	//要逐个节点释放
	QNode* pcur = pq->phead;
	while (pcur)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

2.3.3 mystack.h

#include"Queue.h"

typedef struct MyStack
{
	Queue q1;
	Queue q2;
} MyStack;
//用两个队列实现栈，构建一个结构体去管理这两个队列

MyStack* myStackCreate();//初始化栈
void myStackPush(MyStack* obj, int x);//压栈
int myStackPop(MyStack* obj);//出栈
int myStackTop(MyStack* obj);//获取栈顶元素
bool myStackEmpty(MyStack* obj);//判断栈是否为空
void myStackFree(MyStack* obj);//释放栈

2.3.4 mystack.c

#include"MyStack.h"

MyStack* myStackCreate() //返回一个MySack类型的指针
{
	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
	if (obj == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
//如果开辟成功，对栈初始化相当于对栈结构体中的两个队列初始化
	QueueInit(&obj->q1);
	QueueInit(&obj->q2);
	return obj;
}

void myStackPush(MyStack* obj, int x)
//压栈前必须在不为空的队列中压栈
{
	if (!QueueEmpty(&obj->q1))//如果q1不为空压q1
		QueuePush(&obj->q1, x);
	else//如果q1为空，则压q2
		QueuePush(&obj->q2, x);
}

int myStackPop(MyStack* obj)
//出栈，必须找到不为空的队列，然后将该队列的元素倒倒另一个队列中，知道只剩最后一个元素的时候，就删除
{
	//要找到不为空的队列进行操作，所以先假设一个为空一个不为空，如果给个条件判断
	Queue* Emptyq = &obj->q1;
	Queue* NonEmptyq = &obj->q2;
	if (!QueueEmpty(&obj->q1))//错了的话就认个错然后换回来
	{
		 NonEmptyq = &obj->q1;
		 Emptyq = &obj->q2;
	}
	//开始导数据
	while (QueueSize(NonEmptyq) > 1)
	{
	//将队列头的元素倒进去另一个队列，在出栈
		QueuePush(Emptyq, QueueFront(NonEmptyq));//压栈
		QueuePop(NonEmptyq);//倒入一个就将非空队列出队列一个
	}
	//倒完后只剩一个数据了，先记录返回值再删除
	int top = QueueFront(NonEmptyq);
	QueuePop(NonEmptyq);
	return top;
}

int myStackTop(MyStack* obj)
//找到不为空的队列，然后获取队列尾的元素，相当于获取栈顶元素
{
	if (!QueueEmpty(&obj->q1))//如果q1不为空取q1队尾
		return QueueBack(&obj->q1);
	else//如果q2不为空取q2队尾
		return QueueBack(&obj->q2);
}

bool myStackEmpty(MyStack* obj) //栈为空当且仅当两个队列都为空
{
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) 
{
	//释放obj前一定也要将q1和q2的空间释放了
	QueueDestory(&obj->q1);
	QueueDestory(&obj->q2);
	free(obj);
	//obj = NULL;没用，一级指针接受指针相当于值传递
	//要手动在main函数中置空

三、用两个栈实现队列

力扣：用栈实现队列

3.1 思路

3.2 代码实现

3.2.1 栈的代码

这里先把栈的声明放这里

stack.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//栈容量
}Stack;

void StackInit(Stack* ps);//初始化栈
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取栈中有效元素个数
bool StackEmpty(Stack* ps);//检测栈是否为空，为空返回true
void StackDestory(Stack* ps);//销毁栈

3.2.2 结构体的创建

根据前面的思路，一个栈专门用来入栈，一个栈专门用来出栈

typedef struct  MyQueue
{
	Stack Pushst;//专门用来入栈
	Stack Popst;//专门用来出栈
} MyQueue;

MyQueue* myQueueCreate();//初始化队列
void myQueuePush(MyQueue* obj, int x);//模拟入队
int myQueuePop(MyQueue* obj);//模拟出队，并返回出去的头元素
int myQueuePeek(MyQueue* obj);//获取队列头元素并返回
bool myQueueEmpty(MyQueue* obj);//判断队列是否为空
void myQueueFree(MyQueue* obj);//销毁队列

3.2.3 初始化队列并返回节点

初始化队列本质上就是对两个栈进行初始化

MyQueue* myQueueCreate() 
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	if (obj == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	//对队列初始化其实就是对里面的两个栈初始化
	StackInit(&obj->Pushst);
	StackInit(&obj->Popst);
	return obj;
}

3.2.4 模拟入队

入队就很简单了，直接往第一个栈里面入栈就行

void myQueuePush(MyQueue* obj, int x)
{
	StackPush(&obj->Pushst, x);
}

3.2.5 获取队列头的元素并返回

队列头的元素要在第二个栈去获取，但在获取前还得确保第二个栈有元素，如果没有，就得先把第一个栈倒过去

int myQueuePeek(MyQueue* obj)
//获取队列头元素有两种情况
//1、一种是popst不为空，直接返回其top下标的元素就行了
//2、一种是popst为空，这时候需要将pushst中的数据全部倒过去，再重复情况1
{
	if (StackEmpty(&obj->Popst))
	{
		while (!StackEmpty(&obj->Pushst))
		{
		//挪数据就是一边给popst入栈，一边给pushst出栈
			StackPush(&obj->Popst, StackTop(&obj->Pushst));
			StackPop(&obj->Pushst);
		}
	}
	return StackTop(&obj->Popst);
}

3.2.6 模拟出队，并返回出去的头元素

出队也要确保第二个栈不为空，但其实我们有了上面这个函数，直接调用一次就相当于是把我们把这个操作给完成了，所以我们直接接受上面那个函数的返回值然后直接pop就行

int myQueuePop(MyQueue* obj)
{
//跟myQueuePeek一样有两种情况，但是我们调用了这个函数相当于是帮我们判断过了，此时直接删就可以了
	int top = myQueuePeek(obj);
	StackPop(&obj->Popst);
	return top;
}

3.2.7 判断队列是否为空

队列是否为空，本质上就是两个栈是否为空

bool myQueueEmpty(MyQueue* obj) 
{
	return StackEmpty(&obj->Popst) && StackEmpty(&obj->Pushst);
}

3.2.8 销毁队列

队列销毁，本质上就是两个栈的销毁，但是要在最后把队列的结构体的释放掉

void myQueueFree(MyQueue* obj) 
{
	StackDestory(&obj->Popst);
	StackDestory(&obj->Pushst);
	free(obj);
	//没用obj = NULL;
}

注意的是这边接受obj的是一级指针，相当于值传递，这里置空没什么意义，要在外面手动置空

3.3 全部代码

3.3.1 stack.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//栈容量
}Stack;

void StackInit(Stack* ps);//初始化栈
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取栈中有效元素个数
bool StackEmpty(Stack* ps);//检测栈是否为空，为空返回true
void StackDestory(Stack* ps);//销毁栈

3.3.2 stack.c

#include"Stack.h"

void StackInit(Stack* ps)
{
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->a = temp;
		ps->capacity = newcapacity;
	}
	//压栈
	ps->a[ps->top++] = x;
}


void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈为空，则没有删除的必要
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	//如果栈为空，不可能有栈顶元素
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackDestory(Stack* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

3.3.3 myqueue.h

#include"Stack.h"

typedef struct  MyQueue
{
	Stack Pushst;//专门用来入栈
	Stack Popst;//专门用来出栈
} MyQueue;

MyQueue* myQueueCreate();//初始化队列并返回节点
void myQueuePush(MyQueue* obj, int x);//模拟入队
int myQueuePop(MyQueue* obj);//模拟出队，并返回出去的头元素
int myQueuePeek(MyQueue* obj);//获取队列头元素并返回
bool myQueueEmpty(MyQueue* obj);//判断队列是否为空
void myQueueFree(MyQueue* obj);//销毁队列

3.3.4 myqueue.c

#include"MyQueue.h"

MyQueue* myQueueCreate() 
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	if (obj == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	//对队列初始化其实就是对里面的两个栈初始化
	StackInit(&obj->Pushst);
	StackInit(&obj->Popst);
	return obj;
}

void myQueuePush(MyQueue* obj, int x)
{
	StackPush(&obj->Pushst, x);
}

int myQueuePop(MyQueue* obj)
{
//跟myQueuePeek一样有两种情况，但是我们调用了这个函数相当于是帮我们判断过了，此时直接删就可以了
	int top = myQueuePeek(obj);
	StackPop(&obj->Popst);
	return top;
}

int myQueuePeek(MyQueue* obj)
//获取队列头元素有两种情况
//1、一种是popst不为空，直接返回其top下标的元素就行了
//2、一种是popst为空，这时候需要将pushst中的数据全部倒过去，再重复情况1
{
	if (StackEmpty(&obj->Popst))
	{
		while (!StackEmpty(&obj->Pushst))
		{
		//挪数据就是一边给popst入栈，一边给pushst出栈
			StackPush(&obj->Popst, StackTop(&obj->Pushst));
			StackPop(&obj->Pushst);
		}
	}
	return StackTop(&obj->Popst);
}

bool myQueueEmpty(MyQueue* obj) 
{
	return StackEmpty(&obj->Popst) && StackEmpty(&obj->Pushst);
}

void myQueueFree(MyQueue* obj) 
{
	StackDestory(&obj->Popst);
	StackDestory(&obj->Pushst);
	free(obj);
	//没用obj = NULL;
}