C语言用栈模拟实现队列问题详解
时间：2022-12-03 12:10:03 | 栏目：C代码 | 点击：次
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
题目链接
思路分析
题目的意思是要用两个栈来模拟实现一个队列。仅可以用栈的基本功能实现队列的基本功能。所以需要创建两个栈。所以这两个栈st1，st2可用一个结构体包含。本质就是用两个后进先出的栈，来模拟一个先进先出的队列。
思路：
1.st2这个栈用来压栈，st1的作用：把st2的所有值压到st1中，然后经过st1出栈。这样就达到了队列先进先出的性质。
2.st2一直用来压栈。如果st1为空则将st2里面的值全都转移到st1，如果st1不为空，则继续出栈，知道st1为空为止。
代码实现
ypedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化结构体
void StackInit(ST* ps);
//销毁结构体
void StackDestroy(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//得到栈顶的值
STDataType StackTop(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);
//得到栈的长度
int StackSize(ST* ps);
//初始化结构体
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//销毁结构体
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//压栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (new == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = new;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top>0);
return ps->a[ps->top-1];
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//得到栈的长度
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//创建了两个栈
typedef struct
{
ST st1;
ST st2;
} MyQueue;
//对两个栈进行初始化。
MyQueue* myQueueCreate()
{
MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue));
assert(newQueue);
StackInit(&newQueue->st1);
StackInit(&newQueue->st2);
return newQueue;
}
void myQueuePush(MyQueue* obj, int x)
{
assert(obj);
StackPush(&obj->st2, x);
}
int myQueuePop(MyQueue* obj)
{
assert(obj);
if(StackEmpty(&obj->st1))
{
while(!StackEmpty(&obj->st2))
{
StackPush(&obj->st1, StackTop(&obj->st2));
StackPop(&obj->st2);
}
}
int top = 0;
if(!StackEmpty(&obj->st1))
{
top = StackTop(&obj->st1);
StackPop(&obj->st1);
}
return top;
}
int myQueuePeek(MyQueue* obj)
{
assert(obj);
if(StackEmpty(&obj->st1))
{
while(!StackEmpty(&obj->st2))
{
StackPush(&obj->st1, StackTop(&obj->st2));
StackPop(&obj->st2);
}
}
if(!StackEmpty(&obj->st1))
{
return StackTop(&obj->st1);
}
return 0;
}
bool myQueueEmpty(MyQueue* obj)
{
return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);
}
void myQueueFree(MyQueue* obj)
{
StackDestroy(&obj->st1);
StackDestroy(&obj->st2);
free(obj);
}