沁水网站建设,建设网站坪山,网站导航类型,公司管理制度用栈实现队列 #x1f609; 1.题目来源#x1f440;2.题目描述#x1f914;3.解题思路#x1f973;4.代码展示 所属专栏#xff1a;玩转数据结构题型❤️ #x1f680; 博主首页#xff1a;初阳785❤️ #x1f680; 代码托管#xff1a;chuyang785❤️ … 用栈实现队列 1.题目来源2.题目描述3.解题思路4.代码展示 所属专栏玩转数据结构题型❤️ 博主首页初阳785❤️ 代码托管chuyang785❤️ 感谢大家的支持您的点赞和关注是对我最大的支持❤️ 博主也会更加的努力创作出更优质的博文❤️ 关注我关注我关注我重要的事情说三遍❤️ 1.题目来源
LeetCode用栈实现队列 注意本题涉及到有关数据结构——队列和栈这两章节的知识点如有小伙伴还不熟栈的可以先复习复习一下有关栈的相关知识复习的地方我也提供了哦所用到的知识点——栈所用到的知识点——队列 注意同样的本题是使用纯C语言实现的.
2.题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty 实现 MyQueue 类 1.void push(int x) 将元素 x 推到队列的末尾 2.int pop() 从队列的开头移除并返回元素 3.int peek() 返回队列开头的元素 4.boolean empty() 如果队列为空返回 true 否则返回 false 说明
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。 3.解题思路
从题目要求我们知道要用两个栈列实现队列的功能也就是使用的是栈但是实现的效果时队列的效果。开始做题之前我们首要的是明白队列和栈的特点。这里我们就简单的提一下具体的知识请看上述给的链接。队列——队列的特性是先进的先出就跟食堂打饭一样先到的先打饭打完饭就可以走了。栈——栈的特性是先进的后出就跟我们在桌子上叠书一样想要拿到最底下的书就要先把最上面的书先拿走。首先队列的插入和栈的插入都是一样的都是尾插所以push这个动作并不难关键是栈的删除是尾删而队列的删除时头删那怎么样才能使用两个栈实现删除头上的数据呢。既然栈是尾删能不能把存放进去的数据反过来这样虽然栈进行的是尾删但是删除的是头上的数据也就相当于是头删一样了。那么我们的思路肯定是这样的两个栈首先第一次存放数据的时候随便找一个栈粗放数据假设放的是12345头数据是1尾数据是5等到要删除的时候通过找到尾的方式把数据一一放到另一个栈中这样另一个栈的数据就是54321了这个时候头数据就是5尾数据就是1了Pop的时候就是Pop尾数据1也就是插入时的头数据这样就实现头删。而如果还要继续存放数据的时候就把数据按照上面同样的操作把数据重新放回去也就是2345然后继续在后面放数据要删除的时候再重复第一次的操作即可。那么问题来了从上述分析我们知道了两个栈一个栈是用来存放数据进去的栈我们命名为Spush一个是用来删除数据的栈Spop而且我们每次还要继续放数据的是由都要把数据从Spop中把数据放回Spush然后进行追加数据但是这一步真的有必要吗其实并不需要这两个栈就只需要完成一个push另一个pop就行了追加数据的时候也不需要把数据从Spop中重新放回Spush中只需要等Spop中数据被删除完后再从Spush中导入即可。 所以总上所述我们的两个栈每一栈复杂特定的功能一个负责push数据一个用来pop数据 同时解释一下我们oj刷题的时出现的一些一些疑问 typedef struct {} MyQueue;MyQueue* myQueueCreate() {}这个是我们题目出现的函数接口我来解释一下表示什么意思。
题目已经明确我们要使用两个栈来实现队列所有我们就得创建两个栈的而我们通常遇到这种两个及以上的要使用的成员时为了减少传递的参数以及代码的可读性简洁性我们通常会用一个结构体把他们封装起来所以我们的上述结构体就是用来创建两个栈的并且这个结构体还是个匿名结构体匿名结构体的特点就是只能用一次这里我们只需要使用一次即可所以匿名合理。而另一个函数接口是用来初始化我们的结构体的并返回结构体指针。
4.代码展示
//栈函数接口
typedef int STDataType;
typedef struct Stack
{STDataType* data;int capaciyt;int size;
}Stack;void StackInit(Stack* ps);void StackDestroy(Stack* ps);void StackPush(Stack* ps, STDataType x);void StackPop(Stack* ps);STDataType StackTop(Stack* ps);bool StackEmpt(Stack* ps);int StackSize(Stack* ps);void StackInit(Stack* ps)
{assert(ps);ps-data NULL;ps-capaciyt 0;ps-size 0;
}void StackDestroy(Stack* ps)
{assert(ps);free(ps-data);ps-data NULL;ps-capaciyt ps-size 0;
}void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps-size ps-capaciyt){int newCapacity ps-capaciyt 0 ? 4 : ps-capaciyt * 2;STDataType* tmp (STDataType*)realloc(ps-data, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc);exit(-1);}ps-data tmp;ps-capaciyt newCapacity;}ps-data[ps-size] x;ps-size;
}void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpt(ps));ps-size--;
}STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpt(ps));return ps-data[ps-size - 1];
}bool StackEmpt(Stack* ps)
{assert(ps);return ps-size 0;
}int StackSize(Stack* ps)
{assert(ps);return ps-size;
}//函数实现
typedef struct {Stack Spush;Stack Spop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* ret (MyQueue*)malloc(sizeof(MyQueue));StackInit(ret-Spush);StackInit(ret-Spop);return ret;
}//这里我把Peek函数放到了前面考虑到后面的Pop也会用到类似的功能直接服用Peek就行了
int myQueuePeek(MyQueue* obj) {//为空导入数据if (StackEmpt(obj-Spop)){while (!StackEmpt(obj-Spush)){StackPush(obj-Spop,StackTop(obj-Spush));StackPop(obj-Spush);}}return StackTop(obj-Spop);
}void myQueuePush(MyQueue* obj, int x) {//直接再Spush中插入数据StackPush(obj-Spush,x);
}int myQueuePop(MyQueue* obj) {//服用Peek,如果Spop为空就从Spush中导入数据int ret myQueuePeek(obj);StackPop(obj-Spop);return ret;
}bool myQueueEmpty(MyQueue* obj) {//两个为空才为空return StackEmpt(obj-Spop) StackEmpt(obj-Spush);
}void myQueueFree(MyQueue* obj) {StackDestroy(obj-Spop);StackDestroy(obj-Spush);free(obj);
}
