【基础数据结构】栈和队列

  • 开发
  • 34

例题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;
}

阅读全部

相关推荐

  1. 【基础数据结构】栈和队列

    2024-01-13 14:58:03       35 阅读

  4. 数据结构---栈和队列

    2024-01-13 14:58:03       39 阅读

  6. 数据结构:栈和队列

    2024-01-13 14:58:03       37 阅读

  7. 「数据结构」栈和队列

    2024-01-13 14:58:03       21 阅读

  8. 【数据结构】栈和队列

    2024-01-13 14:58:03       23 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-01-13 14:58:03       16 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-01-13 14:58:03       16 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-01-13 14:58:03       15 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-01-13 14:58:03       18 阅读

热门阅读

  2. uniapp搜索附近蓝牙信标（iBeacon）

    2024-01-13 14:58:03       37 阅读

  13. react自定义组件间的传值,if..else..判断,for循环(嵌套map使用),点击事件(Onclick),页面上事件实事传递参数（基础版）

    2024-01-13 14:58:03       38 阅读

  14. SQL常用时间处理函数总结

    2024-01-13 14:58:03       38 阅读

  16. RNN和LSTM的区别是什么？

    2024-01-13 14:58:03       33 阅读

  19. 利用PowerShell和Mkvtoolnix批量去除视频封面

    2024-01-13 14:58:03       41 阅读

  20. 深入理解虚拟DOM：原理、优势与实践

    2024-01-13 14:58:03       28 阅读

  22. 一文读懂Qt信号与槽的机制

    2024-01-13 14:58:03       31 阅读

  25. 传统的背包问题~3479：【例86.4】 混合背包

    2024-01-13 14:58:03       35 阅读