当前位置： 首页 > article >正文

[LeetCode] 栈与队列 I — 232#用栈实现队列 | 225#用队列实现栈 | 20#有效的括号 | 1047#删除字符串中的所有相邻重复项

article 2025/2/6 3:23:14

栈与队列

  • 基础知识
  • 基础语句
  • 模拟栈与队列
    • 232# 用栈实现队列
    • 225# 用队列实现栈
  • 对称匹配—栈
    • 20# 有效的括号
    • 1047# 删除字符串中的所有相邻重复项

基础知识

栈：后进先出 LIFO

队列：先进先出 FIFO

这里介绍的栈和队列是SGI STL中的数据结构

三个最为普遍的STL（C++标准模板库）版本：

  • HP STL 是C++ STL的第一个实现版本，且开放源代码，其他版本的C++ STL，一般是以HP STL为蓝本实现
  • P.J.Plauger STL 由P.J.Plauger参照HP STL实现，被Visual C++编译器所采用，不开源
  • SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高

栈stack和队列queue的所有元素必须符合先进后出/先进先出规则，所以不提供走访功能，也不提供迭代器(iterator)来遍历所有元素

stack和queue 不是容器（Container），而是容器适配器（Container Adapter）

stack和queue 默认基于 deque（双端队列）实现，但允许用户指定其他底层容器（如 list 或 vector，一般queue不能使用vector，因为 vector 不支持 pop_front()）

标准容器（如 vector、list、 deque）直接管理自己的内存和元素

容器适配器仅对底层容器进行接口限制，以实现特定行为，基于现有的容器封装而成，提供特定接口（如后进先出 LIFO 操作），但底层存储和实现依赖于其他容器

基础语句

// 栈
std::stack<int, std::vector<int>> third; // 定义以vector为底层容器的栈
stack.push(val); // 将元素压入栈顶 O(1)，依赖底层容器的 push_back()
stack.pop(); // 移除栈顶元素（无返回值） O(1)，依赖底层容器的 pop_back()
stack.top(); // 返回栈顶元素（不移除） O(1)，依赖底层容器的 back()
stack.empty(); // 检查栈是否为空 O(1)，返回bool，直接调用底层容器的 empty()
stack.size(); // 返回栈中元素数量 O(1)，调用底层容器的 size()

// 队列
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
queue.push(val); // 将元素插入队尾 O(1)，依赖底层容器的 push_back()
queue.pop(); // 移除队首元素（无返回值） O(1)，依赖底层容器的 pop_front()
queue.front(); // 返回队首元素（不移除） O(1)，依赖底层容器的 front()
queue.back(); // 返回队尾元素（不移除） O(1)，依赖底层容器的 back()
queue.empty(); // 检查队列是否为空 O(1) ，返回bool，直接调用底层容器的 empty()
queue.size(); // 返回队列中元素数量 O(1)，调用底层容器的 size()

模拟栈与队列

232# 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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 操作）

需要两个栈一个输入栈，一个输出栈，先进后出+后进先出实现先进先出

在push时，只需将数据放进输入栈，但在pop时，需要从输出栈弹出数据，如果输出栈为空，就把输入栈的数据全部导入输出栈

// 栈模拟队列
// O(1) 0ms; O(n) 9.62MB
class MyQueue {
private:
    stack<int> stIn, stOut;
public:  
    MyQueue() { }
    
    void push(int x) { // O(1)
        stIn.push(x);
    }
    
    int pop() { // 均摊O(1)
        int front = this->peek();
        stOut.pop();
        return front;
    }
    
    int peek() { // 均摊O(1)
        if (stOut.empty()) {
            while (!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        return stOut.top();
    }
    
    bool empty() { // O(1)
        return stIn.empty() && stOut.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

225# 用队列实现栈

请你仅使用队列实现一个后入先出（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 都保证栈不为空

使用一个队列，在弹出元素时将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，弹出最后一个元素，实现后进先出

// 队列模拟栈
// 0ms; O(n) 9.19MB
class MyStack {
private:
    queue<int> que;
public:
    MyStack() { }
    
    void push(int x) { // O(1)
        que.push(x);
    }
    
    int pop() { // O(n)
        int size = que.size();
        size--;
        while (size--) {
            que.push(que.front());
            que.pop();
        }
        int top = que.front();
        que.pop();
        return top;
    }
    
    int top() { // O(n)
        int top = this->pop();
        que.push(top); // 将获取到的元素重新添加到队列尾部，保证数据结构没有变化
        return top;
    }
    
    bool empty() { // O(1)
        return que.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

对称匹配—栈

20# 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

提示：

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

括号匹配方式是先进后匹配，与栈思想类似

遍历字符串，遇到左括号将对应的右括号入栈，遇到右括号匹配出栈

// 栈--对称匹配
// O(n) 0ms; O(n) 9.8MB 
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false;
        stack<char> st;
        for (char e : s) {
            if (e == '(') st.push(')');
            else if (e == '[') st.push(']');
            else if (e == '{') st.push('}');
            else if (!st.empty() && e == st.top()) st.pop();
            else return false;
        }
        return st.empty();
    }
};

1047# 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

  1. 1 <= s.length <= 10^5
  2. s 仅由小写英文字母组成。
// 栈--对称匹配
// O(n) 11ms; O(n) 13.98MB
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        string result = "";
        for (char e : s) {
            if (!st.empty() && e == st.top()) st.pop();
            else st.push(e);
        }
        while (!st.empty()) {
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

优化：将字符串直接作为栈

// 栈--对称匹配（字符串实现）
// O(n) 15ms; O(1) 13.44MB
class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for (char e : s) {
            if (!result.empty() && e == result.back()) result.pop_back();
            else result.push_back(e);
        }
        return result;
    }
};

本文参考 LeetCode官方题解 及 代码随想录


http://www.kler.cn/a/533168.html

相关文章：

  • 小程序越来越智能化，作为设计师要如何进行创新设计
  • 结构体和类
  • 2024年度十大网络安全热点事件盘点：时代暗涌下的安全危机
  • 使用开源项目：pdf2docx，让PDF转换为Word
  • modbus协议处理
  • 排序算法--归并排序
  • ES6-rest参数、数组扩展中的扩展运算符
  • CPU、MCU、MPU、SOC、DSP、ECU、GPU、FPGA傻傻分不清楚？一文讲清它们的区别
  • （十一）机器人系统的仿真——建造机器人模型
  • 4. k8s二进制集群之ETCD集群证书生成
  • Vue.js组件开发-实现右下角浮动层可以最大化最小化效果
  • RGB565转BITMAP[C#---2]
  • Vim的基础命令
  • Go语言中结构体字面量
  • 2022年全国职业院校技能大赛网络系统管理赛项模块A：网络构建（样题2）-网络部分解析-附详细代码
  • 【人工智能】掌握图像风格迁移：使用Python实现艺术风格的自动化迁移
  • ChatGPT提问技巧：行业热门应用提示词案例--咨询法律知识
  • git进阶--5---git reset 和 git revert 的区别与联系
  • TypeScript 学习指南
  • 【Python深入浅出】解锁Python3模块：从入门到实战的进阶指南
  • OSPF基础（2）
  • python venv 虚拟环境安装以及使用
  • Linux 系统上安装 Docker 方法详解与比较
  • C++ 类与对象（中）
  • oracle: 索引失效的情况
  • python-异常处理笔记