【栈和队列OJ练习题】-用栈实现队列
题目
https://leetcode-cn.com/problems/implement-queue-using-stacks/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
栈：后进先出
队列：先进先出
如何用两个栈实现队列：
-
方法
-
一个栈PushST 用于插入数据，一个栈PopST 用于出数据
当要入数据时：往PushST栈入数据
当要出数据时：如果PopST栈中有数据，就直接出栈顶数据，如果没有数据，就把PushST栈的数据导入到PopST栈，再出栈顶数据
- 将数据从PushST栈导入到PopST栈，可以得到入栈顺序，从而实现队列的先进先出
注意：PushST栈和PopST栈可以同时有数据，，但是只在PushST栈中入数据，出数据在PopST栈中出数据
当PopST栈中无数据，就把PushST栈中的数据导过去
队列结构
typedef struct {
ST PushST;//一个栈用来入元素
ST PopST;//一个栈用来出数据
} MyQueue;
注意点：
//写法1
struct {
ST PushST;//一个栈用来入元素
ST PopST;//一个栈用来出数据
} MyQueue;
//写法2
typedef struct {
ST PushST;//一个栈用来入元素
ST PopST;//一个栈用来出数据
} MyQueue;
写法1：MyQueue是一个匿名结构体
匿名结构体 - 没有名称
MyStack就是一个变量，一次性用品
//写法1
struct {
int a;
int b;
}MyQueue;
int main()
{
//MyQueue是一个变量
MyQueue.a = 1;
MyQueue.b = 2;
printf("%d %d\n", MyQueue.a, MyQueue.b);// 1 2
return 0;
}
写法2：MyStack是结构体类型 ,可以定义变量
typedef struct {
int a;
int b;
}MyQueue;
int main()
{
//MyQueue是结构体类型
MyQueue tmp;
tmp.a = 1;
tmp.b = 2;
printf("%d %d\n", tmp.a, tmp.b);// 1 2
return 0;
}
队列初始化
//新建队列：返回地址
MyQueue* myQueueCreate()
{
//动态开辟一个队列结构体，里面含两个栈
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
//初始化两个栈
//把栈的地址传过去
StackInit(&q->PushST);
StackInit(&q->PopST);
return q;
}
错误写法：
MyQueue* myQueueCreate()
{
MyQueue q;
return &q;
}
这样写是错误的，q出了作用域就销毁了(栈空间)
q是野指针，相当于返回了栈空间地址问题
入数据
void myQueuePush(MyQueue* obj, int x)
{
//入数据只在PushST栈中入
StackPush(&obj->PushST,x);
}
出数据
int myQueuePop(MyQueue* obj)
{
//出数据在PopST栈中出
//如果PopST栈中没有数据，就把PushST栈的数据导过去
if(StackEmpty(&obj->PopST))
{
//把PushST的数据导过去
while(!StackEmpty(&obj->PushST))
{
//得到PushST栈顶数据
STDataType tmp = StackTop(&obj->PushST);
//把PushST栈顶数据放到PopST栈
StackPush(&obj->PopST,tmp);
//PushST栈顶数据出栈
StackPop(&obj->PushST);
}
}
//题目要求：出数据要返回队头数据
int front = StackTop(&obj->PopST);
StackPop(&obj->PopST);
return front;
}
题目要求出数据还要返回此时的队头数据
得到队头数据
//思路和出数据基本一致，只是不需要Pop掉 PopST的栈顶数据
int myQueuePeek(MyQueue* obj)
{
//出数据在PopST栈中出
//如果PopST栈中没有数据，就把PushST栈的数据导过去
if(StackEmpty(&obj->PopST))
{
while(!StackEmpty(&obj->PushST))
{
STDataType tmp = StackTop(&obj->PushST);
StackPush(&obj->PopST,tmp);
StackPop(&obj->PushST);
}
}
int front = StackTop(&obj->PopST);
return front;
}
释放空间
void myQueueFree(MyQueue* obj)
{
//先释放两个栈空间
StackDestroy(&obj->PopST);
StackDestroy(&obj->PushST);
//再释放动态开辟的队列结构体
free(obj);
}
队列是否为空
bool myQueueEmpty(MyQueue* obj)
{
//如果两个栈都为空->说明队列为空
return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}
总代码
//现在栈存放的是字符
typedef 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);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0; // ps->top = -1;
ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 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* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)
{
assert(ps);
/*if (ps->top == 0)
{
return true;
}
else
{
return false;
}*/
return ps->top == 0;
}
typedef struct {
ST PushST;//一个栈用来入元素
ST PopST;
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&q->PushST);
StackInit(&q->PopST);
return q;
}
void myQueuePush(MyQueue* obj, int x)
{
//入数据在PushST栈中入
StackPush(&obj->PushST,x);
}
int myQueuePop(MyQueue* obj)
{
//出数据在PopST栈中出
//如果PopST栈中没有数据，就把PushST栈的数据导过去
if(StackEmpty(&obj->PopST))
{
while(!StackEmpty(&obj->PushST))
{
STDataType tmp = StackTop(&obj->PushST);
StackPush(&obj->PopST,tmp);
StackPop(&obj->PushST);
}
}
int front = StackTop(&obj->PopST);
StackPop(&obj->PopST);
return front;
}
int myQueuePeek(MyQueue* obj)
{
//出数据在PopST栈中出
//如果PopST栈中没有数据，就把PushST栈的数据导过去
if(StackEmpty(&obj->PopST))
{
while(!StackEmpty(&obj->PushST))
{
STDataType tmp = StackTop(&obj->PushST);
StackPush(&obj->PopST,tmp);
StackPop(&obj->PushST);
}
}
int front = StackTop(&obj->PopST);
return front;
}
bool myQueueEmpty(MyQueue* obj)
{
return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}
void myQueueFree(MyQueue* obj)
{
StackDestroy(&obj->PopST);
StackDestroy(&obj->PushST);
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);
*/
- 点赞
- 收藏
- 关注作者
评论（0）