首页 > 其他分享 >Leetcode:栈和队列的互相实现

Leetcode:栈和队列的互相实现

时间：2024-09-30 19:47:26浏览次数：11  
标签：obj tem 队列 互相 assert int Leetcode Empty

目录

一、用两个队列实现栈

题目：

分析：

代码实现：

 二、用两个栈实现队列

题目：

 分析：

代码：

总结：核心就在于先进先出和后进先出之间的一个灵活变换，两个栈能够先进先出，而两个队列能够后进先出 

一、用两个队列实现栈

题目：

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=O83Ahttps://leetcode.cn/problems/implement-stack-using-queues/description/

 

分析：

首先，我们明确队列有几个接口，初始化、入队、出队、取队头、取队尾、判空、返回有效元素个数、销毁。

题目要求只使用队列标准操作实现栈的四种操作，push、pop、top、empty,实际要求我们主要要能够实现栈存储元素后进先出的特点即可。

那如何利用两个队列实现栈的后进先出呢？

 

代码实现：

（注释在代码中哦，一些错误的代码我给注释掉的不用管）

//两个队列，一个装元素，另一个用来倒

typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
    QDataType data;
}QNode;

//定义一个包含队头和队尾的结构体
typedef struct Queue
{
	QNode* front;
	QNode* rear;
    int size;//标记队列中元素个数
}Queue;

void QueueInit(Queue* q)
{
	assert(q);
	/*QNode* tem = (QNode*)malloc(sizeof(QNode));
	if (tem == NULL)
	{
		perror("malloc");
		return;
	}*/
	q->front = q->rear = NULL;
	//q->front->next = NULL;
	//q->front->data = 0;
	q->size = 0;
}

//通过尾插在队尾入队列
void QueuePush(Queue* q,QDataType x)
{
	assert(q);
	QNode* tem = (QNode*)malloc(sizeof(QNode));
	if (tem == NULL)
	{
		assert("malloc");
		return;
	}
    
	if (q->front == NULL)//第一个节点
	{
		q->front = q->rear = tem;
		q->front->data = x;
        tem->next=NULL;//别忘了tem的next置空
	}
	else//第二及以后节点
	{
		q->rear->next = tem;
		q->rear = tem;
		q->rear->next = NULL;
		q->rear->data = x;
	}
	q->size++;

    // tem->next = NULL;
    // tem->data = x;
    // if (q->rear == NULL) {
    //     q->front = q->rear = tem;
    // } else {
    //     q->rear->next = tem;
    //     q->rear = tem; // 更新tail的指向
    // }
 
    // q->size++; // push一下节点个数++

}

//通过头删实现在队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->front);//头指针不为空才存在删
	QNode* tem = q->front;
	q->front = q->front->next;
	if (q->front == NULL)
		q->rear = NULL;//避免尾指针变成野指针
	free(tem);
	q->size--;
}

//获取队列头部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->front->data;
}

//获取队列尾部元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->rear);
	return q->rear->data;
}

//获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	if (q->size == 0)
		return 1;
	else
		return 0;
}

//销毁队列
void QueueDestroy(Queue* q)
{
    assert(q);
    while(q->front)
    {
        QNode* tem=q->front;
        q->front=q->front->next;
        free(tem);
    }
    q->rear=NULL;
    q->size=0;
    //assert(pq);

	// QNode* cur = pq->front;
	// while (cur)
	// {
	// 	QNode* next = cur->next;
	// 	free(cur);

	// 	cur = next;
	// }

	// pq->front = pq->rear = NULL;
	// pq->size = 0;
}

//上面都是队列的接口，因为此处是用C语言实现，所以得写一下
//接下来才是栈的实现

typedef struct {
    Queue q1;//定义两个队列
    Queue q2;
} MyStack;

// typedef struct Stack
// {
//     int* arr;
//     int top;
//     int capacity;
// }

//初始化
//在本题由于栈的4种操作的实现完全依赖于队列，对栈的初始化就是对两个队列的初始化
MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);//->优先级高于&
    QueueInit(&obj->q2);
    return obj;
}

//压栈,把元素往不为空的队列压
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    QueuePush(&obj->q1,x);
    else//
    QueuePush(&obj->q2,x);
}

//出栈
//关键在于找到空队列，将不为空队列的前size-1个元素导到空队列，剩下的那1个元素则头删，从而实现栈的后进先出
int myStackPop(MyStack* obj) {
    //假定q1为空队列
    Queue* Empty=&obj->q1;
    Queue* No_Empty=&obj->q2;
    if(!QueueEmpty(Empty))//假定错误则调换
    {
        Empty=&obj->q2;
        No_Empty=&obj->q1;
    }
    //找到了空队列和不为空队列，接下来实现不为空队列的前size-1个元素导到空队列
    while(QueueSize(No_Empty)>1)
    {
        int tem=QueueFront(No_Empty);
        QueuePush(Empty,tem);//先将非空队列的元素压到空队列
        QueuePop(No_Empty);//再头头删掉它
    }
    //不为空队列的最后一个元素删除和返回
    int tem=QueueFront(No_Empty);
    QueuePop(No_Empty);
    return tem;
}

//取栈顶元素
int myStackTop(MyStack* obj) {
    // //假定q1为空队列
    // Queue* Empty=&obj->q1;
    // Queue* No_Empty=&obj->q2;
    // if(!QueueEmpty(Empty))//假定错误则调换
    // {
    //     Empty=&obj->q2;
    //     No_Empty=&obj->q1;
    // }
    // //找到了空队列和不为空队列，接下来实现不为空队列的前size-1个元素导到空队列
    // while(QueueSize(No_Empty)>1)
    // {
    //     int tem=QueueFront(No_Empty);
    //     QueuePush(Empty,tem);
    //     QueuePop(No_Empty);
    // }
    // //不为空队列的最后一个元素返回
    // int tem=QueueBack(No_Empty);
    // //QueuePop(No_Empty);
    // return tem;
    
    if(!QueueEmpty(&obj->q1))
    return QueueBack(&obj->q1);
    else
    return QueueBack(&obj->q2);
}

//判空
bool myStackEmpty(MyStack* obj) {
    if(QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
    return true;
    else
    return false;
    //return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

//销毁栈
//即销毁掉两个队列
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

 

 二、用两个栈实现队列

题目：

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=O83Ahttps://leetcode.cn/problems/implement-queue-using-stacks/description/

 

 分析：

与上面的思路类似，不同之处在于栈的的特点是后进先出，要实现队列的先进先出的话，除了要将后进的size-1个元素导到另一个栈，将最先进的元素通过出栈pop删除，为了以后能够继续重复此操作，还要再将导过去的元素再导回来。

注意在本题实现队列的出队pop时，最关键的就在于还要导回去！！！！

代码：

typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;//栈中元素个数
	int capacity;//栈容量
}Stack;

//扩容函数
void Exp(Stack* p)
{
	if (p->capacity == p->top)
	{
		int new_capacity = p->capacity == 0 ? 4 : p->capacity * 2;//三目运算
		STDataType* tem = (STDataType*)realloc(p->arr, new_capacity * sizeof(STDataType));//注意是p->arr，不是p
		if (tem == NULL)//对返回值判断
		{
			perror("realloc");
			exit(1);
		}
		p->capacity = new_capacity;
		p->arr = tem;
	}
}

//初始化栈
void InitStack(Stack* p)
{
	assert(p);
	p->arr = NULL;
	p->top = 0;
	p->capacity = 0;
}

//入栈
void PushStack(Stack* p, STDataType x)
{
	assert(p);
	Exp(p);
	p->arr[p->top] = x;//元素入栈顶
	p->top++;
}

//出栈
void PopStack(Stack* p)
{
	assert(p);
	assert(p->top > 0);//有元素才能出
	p->top--;
}

//取栈顶元素
STDataType TopStack(Stack* p)
{
	assert(p);
	assert(p->top > 0);
	return p->arr[p->top - 1];//top相当于size，而数组下标是从0开始的
}

//获取栈中有效元素个数
int SizeStack(Stack* p)
{
	assert(p);
	return p->top;
}

//判空
bool EmptyStack(Stack* p)
{
	assert(p);
	//确实栈中元素为0则为true,否则为false
	return !p->top;
}

void DestroyStack(Stack* p)
{
	assert(p);
	if (p->arr)//arr非空指针时才存在释放问题
	{
		free(p->arr);//释放掉动态申请的内存
		p->arr = NULL;//置空
		p->capacity = p->top = 0;
	}
}

//以上都是栈的接口
//接下来才是用栈实现队列

typedef struct {
    Stack s1;//定义两个栈
    Stack s2;
} MyQueue;

//对队列的初始化即对两个栈的初始化
MyQueue* myQueueCreate() {
    MyQueue* tem=(MyQueue*)malloc(sizeof(MyQueue));
    InitStack(&tem->s1);
    InitStack(&tem->s2);
    return tem;//不要忘了返回！！！
}

//同样，始终保持一个栈为空，而另一个不为空,往不为空的栈压
void myQueuePush(MyQueue* obj, int x) {
    if(!EmptyStack(&obj->s1))
    PushStack(&obj->s1,x);
    else
    PushStack(&obj->s2,x);
}

//队列的头删
//
int myQueuePop(MyQueue* obj) {
    assert(obj);
    //assert((!EmptyStack(&obj->s1) || !EmptyStack(&obj->s2));//两个栈都为空就不存在后面问题
    //假设
    Stack* Empty=&obj->s1;
    Stack* No_Empty=&obj->s2;
    if(!EmptyStack(Empty))//假设错误调换
    {
        Empty=&obj->s2;
        No_Empty=&obj->s1;
    }
    //实现头删
    //1.找到先进的元素
    while(SizeStack(No_Empty)>1)
    {
        int tem=TopStack(No_Empty);//取栈顶元素
        PopStack(No_Empty);//删除栈顶元素
        PushStack(Empty,tem);//压入另一个空栈
    }
    //2。删除
    int tem=TopStack(No_Empty);
    PopStack(No_Empty);
    //3.将在另一个栈中的元素导回去，以便下次头删
    while(!EmptyStack(Empty))
    {
    int tem=TopStack(Empty);
    PopStack(Empty);
    PushStack(No_Empty,tem);
    }
    return tem;
}

//返回队列开头元素
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    //assert((!EmptyStack(&obj->s1) || !EmptyStack(&obj->s2));//两个栈都为空就不存在后面问题
    if(!EmptyStack(&obj->s1))
    return (&obj->s1)->arr[0];
    else
    return (&obj->s2)->arr[0];
}

//判空
bool myQueueEmpty(MyQueue* obj) {
    return EmptyStack(&obj->s1) && EmptyStack(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    assert(obj);//销毁栈即销毁队列
    DestroyStack(&obj->s1);
    DestroyStack(&obj->s2);

}

 

总结：核心就在于先进先出和后进先出之间的一个灵活变换，两个栈能够先进先出，而两个队列能够后进先出 

 （栈和队列还不是很清楚的铁铁可以看我前面博客哦）

标签：obj,tem,队列,互相,assert,int,Leetcode,Empty
From： https://blog.csdn.net/2301_81271741/article/details/142629910

相关文章

  • 1284 海港 队列 模拟
    思路解释 1. 数据结构选择： 使用 queue 来存储每艘船的到达时间和乘客国籍信息。 使用数组 a 来记录每个国籍的乘客数量。 2. 输入处理： 读取船只数量 n。 对于每艘船，读取其到达时间 t 和乘客数量 k，然后读取每个乘客的国籍 x。 3. 统计不同......
  • 9073 关系网络 广搜 队列
    解决思路 广度优先搜索 (BFS)：使用BFS从起点 x 开始搜索，找到到达终点 y 的最短路径。 队列：使用队列存储当前节点和步数。 访问标记：使用数组 vis 标记节点是否被访问过，防止重复访问。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;c......
  • 2520 牛的舞蹈表演 二分答案 优先队列
    解决思路 二分查找：使用二分查找来确定舞台的最小大小 K。 检查函数：定义一个检查函数 check(mid)，判断在舞台大小为 mid 时，演出是否能在 T_max 时间内完成。 优先队列：使用优先队列模拟舞台上的奶牛，确保每次有奶牛完成表演时，下一头奶牛立即上台。 更新边界：......
  • 9564 Work Scheduling 结构体排序 优先队列 最小堆 贪心
    解决思路 排序：首先将所有工作按照截止时间 D_i 进行排序。 优先队列：使用一个最小堆来存储当前选择的工作的利润。 选择工作：遍历所有工作，如果当前工作的截止时间大于堆的大小，则将该工作加入堆中；否则，如果当前工作的利润大于堆顶的利润，则替换堆顶的工作。#include......
  • 3319 哈夫曼树 优先队列 最小堆
    #include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e3+10,inf=0x3f3f3f3f;//优先队列（最小堆），用于存储叶结点的权值priority_queue<int,vector<int>,greater<int>>q;intn,ans,x;intmain(){//读取叶结点的数量......
  • leetcode1353. 最多可以参加的会议数目
    给你一个数组 events，其中 events[i]=[startDayi,endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。你可以在满足 startDayi <=d<=endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。请你返回你可以参加的 最大 会议......
  • leetcode133. 克隆图
    给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。classNode{publicintval;publicList<Node>neighbors;}测试用例格式：简单起见，每个节点的值都和它的索引相同。例如，第一个......
  • Leetcode 981. 基于时间的键值存储
    1.题目基本信息1.1.题目描述设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。实现TimeMap类：TimeMap()初始化数据结构对象voidset(Stringkey,Stringvalue,inttimestamp)存储给定时间戳timestamp......
  • Leetcode 875. 爱吃香蕉的珂珂
    1.题目基本信息1.1.题目描述珂珂喜欢吃香蕉。这里有n堆香蕉，第i堆中有piles[i]根香蕉。警卫已经离开了，将在h小时后回来。珂珂可以决定她吃香蕉的速度k（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉k根。如果这堆香蕉少于k根，她将吃掉这堆的所有香蕉，然后这一小......
  • 【leetcode】169.多数元素
    boyer-moore算法最简单理解方法：假设你在投票选人如果你和候选人（利益）相同，你就会给他投一票（count+1），如果不同，你就会踩他一下（count-1）当候选人票数为0（count=0）时，就换一个候选人，但因为和你利益一样的人占比超过了一半不论换多少次，最后留下来的都一定是个和你（利益）相同的人。代码：......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99