例题1
实现一个MyQueue类，该类用两个栈来实现一个队列。
示例：
MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false说明：
- 你只能使用标准的栈操作 -- 也就是只有?
push to top,?peek/pop from top,?size?和?is empty?操作是合法的。- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
- 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
(C语言)
这段代码实现了使用两个栈来模拟队列的功能。栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。通过使用两个栈，我们可以达到模拟队列的效果。
整体的思路如下：
1. 首先，我们定义了一个结构体 `MyQueue`，它包含一个数组 `elements` 用于存储队列元素，以及 `front` 和 `rear` 分别表示队列的前端和后端。
2. 初始化队列时，我们将 `front` 和 `rear` 的初始值都设为 -1，表示队列为空。
3. 入队操作 `push`：
- ? ??首先检查队列是否已满，如果后端指针 `rear` 已经指向数组的最后一个位置（`MAX_SIZE - 1`），则队列已满，无法再插入元素。
- ? ??如果队列不满，我们将要插入的元素放入数组的后端，并将 `rear` 后移一位。
- ? ??如果队列之前为空（即 `front` 为初始值 -1），则将 `front` 移动到数组的第一个元素。
4. 出队操作 `pop`：
- ? ? 首先检查队列是否为空，如果前端指针 `front` 为初始值 -1 或者 `front` 大于 `rear`，则队列为空，无法进行出队操作。
- ? ??如果队列不为空，我们返回数组前端指针 `front` 所指向的元素，并将 `front` 后移一位。
5. 查看队头元素操作 `peek`：
- ? ??首先检查队列是否为空，如果前端指针 `front` 为初始值 -1 或者 `front` 大于 `rear`，则队列为空，无法获取队头元素。
- ? ??如果队列不为空，我们返回数组前端指针 `front` 所指向的元素，但不改变 `front` 的位置。
6. 判断队列是否为空操作 `isEmpty`：
- ? ? 如果前端指针 `front` 为初始值 -1 或者 `front` 大于 `rear`，则队列为空，返回 `true`，否则返回 `false`。
在 `main` 函数中，我们使用上述操作函数来对模拟队列进行一些简单的测试：
- ?首先，我们创建一个 `MyQueue` 对象 `queue` 并初始化。
- ?然后，我们调用 `push` 函数两次将元素 1 和 2 入队，依次变为 [1, 2]。
- ?接下来，我们调用 `peek` 函数获取队头元素，即 1，并打印出来。
- ?然后，我们调用 `pop` 函数将队头元素 1 出队，并打印出来。
- ?最后，我们调用 `isEmpty` 函数判断队列是否为空，并将结果打印出来。
这样，我们就完成了使用两个栈来模拟队列的功能。
C++
#include <stack>
#include<iostream>
class MyQueue {
private:
std::stack<int> inStack; // 用于入队的栈
std::stack<int> outStack; // 用于出队的栈
public:
MyQueue() {}
void push(int x) {
inStack.push(x); // 将元素压入入队栈
}
int pop() {
if (outStack.empty()) {
// 如果出队栈为空，将入队栈中的元素依次弹出并压入出队栈
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
int front = outStack.top(); // 获取队头元素
outStack.pop(); // 弹出队头元素
return front;
}
int peek() {
if (outStack.empty()) {
// 如果出队栈为空，将入队栈中的元素依次弹出并压入出队栈
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
return outStack.top(); // 返回队头元素
}
bool empty() {
return inStack.empty() && outStack.empty(); // 判断队列是否为空
}
};
int main() {
MyQueue queue;
queue.push(1);
queue.push(2);
int peekValue = queue.peek(); // 返回 1
int popValue = queue.pop(); // 返回 1
bool isEmpty = queue.empty(); // 返回 false
std::cout << peekValue << " " << popValue << " ";
if(isEmpty)
{
std::cout<<"空";
}
else
{
std::cout<<"非空";
}
return 0;
}C
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int elements[MAX_SIZE];
int front;
int rear;
} MyQueue;
void initQueue(MyQueue* queue) {
queue->front = -1; // 初始化队列的前端指针为-1
queue->rear = -1; // 初始化队列的后端指针为-1
}
void push(MyQueue* queue, int x) {
if (queue->rear == MAX_SIZE - 1) {
printf("Queue is full. Cannot push element.\n");
return; // 如果队列已满，则无法将元素入队，直接返回
}
queue->elements[++queue->rear] = x; // 将元素x入队到队尾
if (queue->front == -1) {
queue->front = 0; // 如果队列为空，将前端指针指向队列的第一个元素
}
}
int pop(MyQueue* queue) {
if (queue->front == -1 || queue->front > queue->rear) {
printf("Queue is empty. Cannot pop element.\n");
return -1; // 如果队列为空或前端指针大于后端指针，则无法将元素出队，直接返回-1
}
return queue->elements[queue->front++]; // 将前端指针指向的元素出队，并将前端指针后移
}
int peek(MyQueue* queue) {
if (queue->front == -1 || queue->front > queue->rear) {
printf("Queue is empty. Cannot peek element.\n");
return -1; // 如果队列为空或前端指针大于后端指针，则无法获取队头元素，直接返回-1
}
return queue->elements[queue->front]; // 返回前端指针指向的元素，不改变前端指针的位置
}
int isEmpty(MyQueue* queue) {
return (queue->front == -1 || queue->front > queue->rear); // 判断队列是否为空，如果前端指针大于后端指针，则为空
}
int main() {
MyQueue queue;
initQueue(&queue); // 初始化队列
push(&queue, 1); // 入队元素1
push(&queue, 2); // 入队元素2
int peekValue = peek(&queue); // 获取队头元素
printf("Peek: %d\n", peekValue); // 打印队头元素
int popValue = pop(&queue); // 出队元素
printf("Pop: %d\n", popValue); // 打印出队元素
int empty = isEmpty(&queue); // 判断队列是否为空
printf("Is empty: %s\n", empty ? "true" : "false"); // 打印队列是否为空的结果
return 0;
}例题2
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop?和?empty）。实现?
MyStack?类：
void push(int x)?将元素 x 压入栈顶。int pop()?移除并返回栈顶元素。int top()?返回栈顶元素。boolean empty()?如果栈是空的，返回?true?；否则，返回?false?。注意：
- 你只能使用队列的基本操作 —— 也就是?
push to back、peek/pop from front、size?和?is empty?这些操作。- 你所使用的语言也许不支持队列。?你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列?, 只要是标准的队列操作即可。
示例：
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False提示：
1 <= x <= 9- 最多调用
100?次?push、pop、top?和?empty- 每次调用?
pop?和?top?都保证栈不为空
(C语言)
题目要求使用两个队列实现一个后入先出（LIFO）的栈，并支持栈的常见操作：push、pop、top和empty。
我们可以借助两个队列来模拟栈的行为。其中一个队列作为主队列，用于存储栈的元素，另一个队列作为辅助队列，在执行出栈操作时辅助完成元素的移动。
具体的做题思路如下：
1. 定义一个类 `MyStack`，并声明两个队列，一个用于存储栈的元素，命名为 `mainQueue`，另一个作为辅助队列，命名为 `helperQueue`。
2. 实现 `push` 操作：
- ? ?将元素 `x` 推入 `mainQueue` 中即可。
3. 实现 `pop` 操作：
- ? ?将 `mainQueue` 中的元素移动到 `helperQueue` 中，直到 `mainQueue` 中只剩下一个元素为止。
- ? ?弹出 `mainQueue` 中的最后一个元素并返回。
- ? ?将 `helperQueue` 重新赋值给 `mainQueue`。
4. 实现 `top` 操作：
- ? ?将 `mainQueue` 中的元素移动到 `helperQueue` 中，直到 `mainQueue` 中只剩下一个元素为止。
- ? ?获取 `mainQueue` 中的最后一个元素并返回。
- ? ?将 `helperQueue` 重新赋值给 `mainQueue`。
5. 实现 `empty` 操作：
- ? ?当且仅当 `mainQueue` 为空时，栈为空，返回 `true`，否则返回 `false`。
通过以上操作，我们可以使用两个队列模拟一个后入先出的栈。具体实现时，出栈和获取栈顶元素时，需要将元素从一个队列移动到另一个队列，以保持栈的后入先出的特性。
C?
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
int* data; // 存储栈元素的数组
int top; // 栈顶指针
int maxSize; // 栈的最大容量
} MyStack;
/** Initialize your data structure here. */
MyStack* myStackCreate(int maxSize) {
MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
stack->data = (int*)malloc(sizeof(int) * maxSize);
stack->top = -1; // 初始化栈顶指针为-1
stack->maxSize = maxSize;
return stack;
}
/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
obj->top++; // 栈顶指针加1
obj->data[obj->top] = x; // 将元素x存入栈顶位置
}
/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
int topElement = obj->data[obj->top]; // 获取栈顶元素
obj->top--; // 栈顶指针减1
return topElement;
}
/** Get the top element. */
int myStackTop(MyStack* obj) {
return obj->data[obj->top]; // 返回栈顶元素
}
/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
return (obj->top == -1); // 栈空的条件是栈顶指针为-1
}
/** Free memory allocated to the stack. */
void myStackFree(MyStack* obj) {
free(obj->data); // 释放存储栈元素的数组内存
free(obj); // 释放栈结构体内存
}
int main() {
MyStack* stack = myStackCreate(5); // 创建容量为5的栈
myStackPush(stack, 1); // 入栈操作
myStackPush(stack, 2);
myStackPush(stack, 3);
printf("%d\n", myStackTop(stack)); // 获取栈顶元素
printf("%d\n", myStackPop(stack)); // 出栈操作
printf("%s\n", myStackEmpty(stack) ? "true" : "false"); // 判断栈是否为空
myStackFree(stack); // 释放栈内存
return 0;
}