从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(下)

简介: 从C语言到C++_18(stack和queue的常用函数+相关练习)力扣

从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(中):https://developer.aliyun.com/article/1521377


150. 逆波兰表达式求值 - 力扣(LeetCode)

难度中等

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

  • 有效的算符为 '+''-''*''/'
  • 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1:

输入:tokens = ["2","1","+","3","*"]

输出:9

解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例 2:

输入:tokens = ["4","13","5","/","+"]

输出:6

解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

示例 3:

输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

输出:22

解释:该算式转化为常见的中缀算术表达式为:

 ((10 * (6 / ((9 + 3) * -11))) + 17) + 5

= ((10 * (6 / (12 * -11))) + 17) + 5

= ((10 * (6 / -132)) + 17) + 5

= ((10 * 0) + 17) + 5

= (0 + 17) + 5

= 17 + 5

= 22

提示:

  • 1 <= tokens.length <= 10^4
  • tokens[i] 是一个算符("+""-""*""/"),或是在范围 [-200, 200] 内的一个整数

逆波兰表达式:

逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 )
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * )

逆波兰表达式主要有以下两个优点:

  • 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
 
    }
};

解析代码:

思路:逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时,

使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下操作:

如果遇到操作数,则将操作数入栈;

如果遇到运算符,则将两个操作数出栈,其中先出栈的是右操作数,

后出栈的是左操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后,栈内只有一个元素,该元素即为逆波兰表达式的值。

简单来说就是:① 操作数入栈

② 遇到操作符就取栈顶两个操作数运算

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& e: tokens)
        {
            if(e == "+" || e == "-" || e == "*" || e == "/")
            {
                int right = st.top();//右操作数先出栈
                st.pop();
                int left = st.top();
                st.pop();
                
                switch(e[0])
                {
                    case '+':
                        st.push(left + right);
                        break;
                    case '-':
                        st.push(left - right);
                        break;
                    case '*':
                        st.push(left * right);
                        break;
                    case '/':
                        st.push(left / right);
                        break;
                }
            }
            else
            {
                st.push(stoi(e));
            }
        }
        return st.top();
    }
};

这题已经简化了,有可能给你一个中缀表达式:

225. 用队列实现栈 - 力扣(LeetCode)

难度简单

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

注意:

  • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis 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
  • 最多调用100pushpoptopempty
  • 每次调用 poptop 都保证栈不为空

进阶:你能否仅用一个队列来实现栈。

class MyStack {
public:
    MyStack() {
 
    }
    
    void push(int x) {
 
    }
    
    int pop() {
 
    }
    
    int top() {
 
    }
    
    bool 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();
 */

解析代码:法一(两个队列)

这道题和下面的栈实现队列,以前都用C语言写过了,但现在我们换个思路

以前的思路:(先入先出转为先入后出)

1.入数据,往不为空的队列入,保持另一个队列为空

2.出数据,依次出队头的数据,转移到另一个队列保存,只剩最后一个时Pop掉

数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)_GR C的博客-CSDN博客

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
 
    MyStack() {
 
    }
    
  void push(int x) {
    q2.push(x); // q2入队列
    while (!q1.empty()) // 把q1的元素全入到q2
    {
      q2.push(q1.front());
      q1.pop();
    }
    swap(q1, q2); // 交换q1和q2
  }
    
  int pop() {
    int r = q1.front();
    q1.pop();
    return r;
  }
    
    int top() {
        //题目要求int top() 返回栈顶元素。(队列尾)队列不能删尾,能取尾
        return q1.front();
    }
    
    bool empty() {
        return q1.empty();
    }
};

解析代码:法二(一个队列)

使用一个队列时,为了满足栈的特性,即最后入栈的元素最先出栈,同样需要满足队列前端的元素是最后入栈的元素。

入栈操作时,首先获得入栈前的元素个数 n,然后将元素入队到队列,再将队列中的前 n 个元素(即除了新入栈的元素之外的全部元素)依次出队并入队到队列,此时队列的前端的元素即为新入栈的元素,且队列的前端和后端分别对应栈顶和栈底。


由于每次入栈操作都确保队列的前端元素为栈顶元素,因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可,获得栈顶元素操作只需要获得队列的前端元素并返回即可(不移除元素)。


由于队列用于存储栈内的元素,判断栈是否为空时,只需要判断队列是否为空即可。

class MyStack {
public:
    queue<int> q;
 
    MyStack() {
 
    }
    
  void push(int x) {
    q.push(x);
        int n = q.size() - 1;
        while(n--)
        {
            q.push(q.front());
            q.pop();
        }
  }
    
  int pop() {
    int r = q.front();
    q.pop();
    return r;
  }
    
    int top() {
        //题目要求int top() 返回栈顶元素。(队列尾)队列不能删尾,能取尾
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};

232. 用栈实现队列 - 力扣(LeetCode)

难度简单

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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
  • 最多调用 100pushpoppeekempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

进阶:

  • 你能否实现每个操作均摊时间复杂度为 O(1) 的队列?换句话说,执行 n 个操作的总时间复杂度为 O(n) ,即使其中一个操作可能花费较长时间。
class MyQueue {
public:
    MyQueue() {
 
    }
    
    void push(int x) {
 
    }
    
    int pop() {
 
    }
    
    int peek() {
 
    }
    
    bool 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();
 */

解析代码:

class MyQueue {
public:
    stack<int> inStack, outStack;
 
    MyQueue() {
 
    }
    
    void push(int x) {
        inStack.push(x);
    }
    
    int pop() {
        if (outStack.empty())
        {
            while (!inStack.empty()) 
            {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }
    
    int peek() {
        if (outStack.empty()) 
        {
            while (!inStack.empty()) 
            {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        return outStack.top();
    }
    
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

本章完。

下一部分先讲讲STL六大组件之一的容器适配器双端队列deque优先级队列priority_queue,再模拟实现stack和queue,最后模拟实现优先级队列priority_queue,

目录
相关文章
|
5天前
|
算法 Unix Linux
C语言随机数的产生(rand、srand、time函数细节讲解)
C语言随机数的产生(rand、srand、time函数细节讲解)
|
4天前
|
安全 C语言
【C语言基础】:内存操作函数
【C语言基础】:内存操作函数
|
4天前
|
编译器 C语言 C++
【C语言基础】:字符函数和字符串函数-2
【C语言基础】:字符函数和字符串函数
|
4天前
|
C语言
【C语言基础】:字符函数和字符串函数-1
【C语言基础】:字符函数和字符串函数
TU^
|
4天前
|
编译器 程序员 Serverless
C语言之函数
C语言之函数
TU^
4 0
TU^
|
4天前
|
机器学习/深度学习 C语言
C语言之函数递归
C语言之函数递归
TU^
7 1
|
4天前
|
C语言
C语言——字符串操作函数
C语言——字符串操作函数
5 0
|
4天前
|
机器学习/深度学习 算法 C语言
【C语言基础】:函数递归详解
【C语言基础】:函数递归详解
|
4天前
|
编译器 程序员 C语言
【C语言基础】:函数详解
【C语言基础】:函数详解
|
4天前
|
存储 API C语言
C语言函数大全--f开头的函数(上)
【6月更文挑战第7天】本篇介绍 C语言中 f 开头的函数(上篇)【C语言函数大全】
15 3
C语言函数大全--f开头的函数(上)