【LeetCode】LeetCode刷题(8)【栈&队列】用栈实现队列(C语言)
用栈实现队列
232. 用栈实现队列 - 力扣(LeetCode) (leetcode-cn.com)
类似题目——用队列实现栈
LeetCode刷题(7)【栈&队列】用队列实现栈(C语言)_半生瓜のblog-CSDN博客
思路:
用栈实现队列要比用队列实现栈要简单一些,我们不用来回在两个栈里面导数据,只需要导一次,然后在依次出栈就成功实现队列的出队操作了。
结论:
- 入数据往push栈里面入
- 出数据从pop栈里面出,如果里面有数据,直接出,没有就把push栈里面的数据导过来,然后再出。
代码实现:
typedef int StackDataType;
typedef struct Stack
{
StackDataType* arry;
int top;//指向栈顶
int capacity;//栈的容量——能放几个数据
}Stack;
//初始化
void StackInit(Stack* ps)
{
assert(ps);
ps->arry = (StackDataType*)malloc(sizeof(StackDataType)*4);
if (ps->arry == NULL)
{
printf("malloc fail");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
//销毁
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->arry);
ps->arry = NULL;
ps->top = ps->capacity =0 ;
}
//入栈
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
//满了
if (ps->top == ps->capacity)
{
StackDataType* tmp = (StackDataType*)realloc(ps->arry, ps->capacity * 2 * sizeof(StackDataType));
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
else
{
ps->arry = tmp;
ps->capacity *= 2;
}
}
ps->arry[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
//如果栈空了调用top,直接终止程序报错
assert(ps->top > 0);
ps->top--;
}
//返回栈顶元素
StackDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->arry[ps->top - 1];
}
//返回栈中元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
//是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;//真为空,假为非空。
}
//////////////////////////////////////////////////////////
typedef struct
{
Stack pushST;
Stack popST;
} MyQueue;
/** Initialize your data structure here. */
MyQueue* myQueueCreate()
{
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
if(q == NULL)
{
printf("malloc is fail!");
return;
}
StackInit(&q->pushST);
StackInit(&q->popST);
return q;
}
/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x)
{
//入数据就往pushST里面入
StackPush(&obj->pushST,x);
}
/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj)
{
//类似于下面的peek
// if(StackEmpty(&obj->popST))
// {
// while(!StackEmpty(&obj->pushST))
// {
// StackPush(&obj->popST,StackTop(&obj->pushST));
// StackPop(&obj->pushST);
// }
// }
// int top = StackTop(&obj->popST);
///////////////////////////////////////////////////////////////
//或者直接调用下面的myQueuePeek函数直接获取popST的栈顶元素
//保存给top之后删除,然后return
int top = myQueuePeek(obj);
StackPop(&obj->popST);
return top;
}
/** Get the front element. */
int myQueuePeek(MyQueue* obj)
{
//出数据要从popST里面出
//如果popST里面是空的
//就要先从pushST里面拿
if(StackEmpty(&obj->popST))
{
//把pushST里面的元素导到popST里面
//然后取第一个
while(!StackEmpty(&obj->pushST))
{
//取pushST最上面的元素依次压进popST
StackPush((&obj->popST),StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
return StackTop(&obj->popST);
}
/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj)
{
return StackEmpty(&obj->popST) && StackEmpty(&obj->pushST);
}
void myQueueFree(MyQueue* obj)
{
StackDestory(&obj->pushST);
StackDestory(&obj->popST);
free(obj);
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/