目录
题目来源:
代码实现:
思路分析:
实现过程:
题目来源:
力扣 - 232.用栈实现队列
题目描述:
代码实现:
我们这里的栈已经写好了,如果对栈还不是很懂的可以看看这篇文章:CSDN - [数据结构 -- C语言] 栈(stack)
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
//ps->top = -1;//top 指栈顶数据
ps->top = 0;//top 指栈顶数据的下一个位置
ps->capacity = 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail:");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = data;
ps->top++;
}
// 出栈
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;
}
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
if (0 == ps->top)
return 1;
else
return 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
typedef struct {
Stack push;
Stack pop;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->push);
StackInit(&obj->pop);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->push, x);
}
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
StackPop(&obj->pop);
return front;
}
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->pop))
{
while(!StackEmpty(&obj->push))
{
StackPush(&obj->pop, StackTop(&obj->push));
StackPop(&obj->push);
}
}
return StackTop(&obj->pop);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->push);
StackDestroy(&obj->pop);
}
思路分析:
我们知道队列的特性:先入先出;栈的特性:先入后出。因此我们定义两个栈,一个是入元素的栈(push栈),另一个是出元素的栈(pop栈)。当我们要入队的时候就把元素直接入到 push栈中,出队的时候先把 push栈 中的元素全部放入 pop栈 中,将 pop栈 的栈顶元素出栈就能实现队列的特性。
此题的本质是以栈的特性来实现队列的特性。
实现过程:
1、我们先将栈的所有接口都写出来。然后我们创建两个栈,一个是实现入队功能的栈(push栈),另一个是实现出队功能的栈(pop栈);
2、我们要实现入队的时候,将元素入到 push栈 中,要出队的时候先将 push栈 中的元素转到 pop栈 中,然后出pop栈 这样就可以实现出队时出的是队头元素;
3、在出队的时候我们先看 pop栈 中还有没有元素,要是有元素我们直接出 pop栈 中的栈顶元素就可以,如果没有就先将 push栈 中的元素转到 pop栈 中;入队的时候直接入到 push栈 中就可以。
对栈还不太明白的朋友可以参考代码实现那部分的 栈 的那篇文章。
文章来源:https://www.toymoban.com/news/detail-463136.html
*** 本篇结束 ***文章来源地址https://www.toymoban.com/news/detail-463136.html
到了这里,关于[链表OJ题 8] 用栈实现队列,没想到你小子的基础这么好,这么快就做对了的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!