225. 用队列实现栈

  1. class MyStack {
  2. public:
  3.     /** Initialize your data structure here. */
  4.     MyStack() {
  6.     }
  8.     /** Push element x onto stack. */
  9.     void push(int x) {
  10.         q.push(x);
  11.         for(int i=0;i<q.size()-1;i++){
  12.             q.push(q.front());
  13.             q.pop();
  14.         }
  15.     }
  17.     /** Removes the element on top of the stack and returns that element. */
  18.     int pop() {
  19.         int x = q.front();
  20.         q.pop();
  21.         return x;
  22.     }
  24.     /** Get the top element. */
  25.     int top() {
  26.         return q.front();
  27.     }
  29.     /** Returns whether the stack is empty. */
  30.     bool empty() {
  31.         return q.empty();
  32.     }
  33.     private:
  34.     std::queue<int> q;
  35. };
  37. /**
  38.  * Your MyStack object will be instantiated and called as such:
  39.  * MyStack* obj = new MyStack();
  40.  * obj->push(x);
  41.  * int param_2 = obj->pop();
  42.  * int param_3 = obj->top();
  43.  * bool param_4 = obj->empty();
  44.  */

232. 用栈实现队列

  1. class MyQueue {
  2. public:
  3.     /** Initialize your data structure here. */
  4.     MyQueue() {
  6.     }
  8.     /** Push element x to the back of queue. */
  9.     void push(int x) {
  10.         while(!s.empty()) {
  11.             temp.push(s.top());
  12.             s.pop();
  13.         }
  14.         temp.push(x);
  15.         while(!temp.empty()){
  16.             s.push(temp.top());
  17.             temp.pop();
  18.         }
  19.     }
  21.     /** Removes the element from in front of queue and returns that element. */
  22.     int pop() {
  23.         int x = s.top();
  24.         s.pop();
  25.         return x;
  26.     }
  28.     /** Get the front element. */
  29.     int peek() {
  30.         return s.top();
  31.     }
  33.     /** Returns whether the queue is empty. */
  34.     bool empty() {
  35.         return s.empty();
  36.     }
  37.     private:
  38.     std::stack<int> s,temp;
  39. };
  41. /**
  42.  * Your MyQueue object will be instantiated and called as such:
  43.  * MyQueue* obj = new MyQueue();
  44.  * obj->push(x);
  45.  * int param_2 = obj->pop();
  46.  * int param_3 = obj->peek();
  47.  * bool param_4 = obj->empty();
  48.  */

155. 最小栈

使用另外一个栈保存最小值

  1. #include <limits.h> // INT_MAX =2147483647  的头文件
  2. class MinStack {
  3. public:
  4.     /** initialize your data structure here. */
  5.     MinStack() {
  6.         mins.push(INT_MAX);
  7.     }
  9.     void push(int x) {
  10.         s.push(x);
  11.         mins.push(min(mins.top(),x));
  13.     }    
  14.     void pop() {
  15.         s.pop();
  16.         mins.pop();
  17.     }
  19.     int top() {
  20.         return s.top();
  21.     }
  23.     int getMin() {
  24.         return mins.top();
  25.     }
  26.     private:
  27.     std::stack<int> s,mins;
  28. };
  30. /**
  31.  * Your MinStack object will be instantiated and called as such:
  32.  * MinStack* obj = new MinStack();
  33.  * obj->push(x);
  34.  * obj->pop();
  35.  * int param_3 = obj->top();
  36.  * int param_4 = obj->getMin();
  37.  */

合法的出栈序列

已知从1到n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法？

  1. //
  2. // Created by er on 2020/5/26.
  3. //判断正常序列
  4. // 使用栈和队列模拟过程
  5. //
  7. #include <iostream>
  8. #include <queue>
  9. #include <stack>
  10. using namespace std;
  11.  bool check_is_valid_order(queue<int> &order){
  12.      stack<int > s;
  13.      int n=order.size();
  14.      for(int i=i;i<=n;i++){
  15.          s.push(i);
  16.          while(!s.empty()&&s.top()== order.front()){
  17.              s.pop();
  18.              order.pop();
  19.          }
  20.      }
  21.      if(!s.empty()) return false;
  22.      else return true;
  23.  }
  24. int main(){
  26.     return 0;
  27. }

224. 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式的值

//
// Created by er on 2020/6/4.
//

#include <iostream>
#include <string>
#include <stack>
using namespace std;

class solution{
public:
    int calculate(string s){
        stack<int> st;
        int sign = 1;
        int res =0;// 保存结果
        for(int i=0;i<s.size();i++){
            //数字
            int num =0;//记录中间变量
            if(s[i] >= '0'&&s[i] <= '9'){
                while(s[i]>='0'&&s[i]<='9'&&i < s.size()){
                     num = num * 10 +(s[i]-'0');
                     i++;
                }
                i--;
                res = res + sign * num;
            } else if(s[i]== '+'){
                sign =1;
            } else if(s[i] == '-'){
                sign = -1;
            } else if(s[i]== '('){ // 将当前的结果先保存到栈中，并且置res 为0，计算括号内的值
                st.push(res);
                st.push(sign);
                res = 0;
                sign =1;// 恢复初始状态
            } else if(s[i] == ')'){
                res *= st.top();st.pop();
                res+= st.top(); st.pop();

            } else cout << "Eroor Input!" << endl;
        }
        return res;
    }
};
int main(){
    string s= "3+5-(2+3)";
    string s1 = "-3+5+3";
    string s2 = "((-33+5)-(5+2)-1)";
    solution cal;
    int res = cal.calculate(s2);
    cout << res << endl;
    return 0;
}

215. 数组中的第K个最大元素

使用最小堆优先级队列实现

//
// Created by er on 2020/6/4.
//

// 优先级队列最小堆实现无序数组中第k大的数
#include <iostream>
#include <vector>
#include <queue>
using  namespace std;

class solution{
public:
    int KstNumArray(vector<int> &v,int k){
        priority_queue<int,vector<int>,greater<int>> pq;
        for(int i=0;i<k;i++){
            pq.push(v[i]);
        }
        for(int i=k;i<v.size();i++){
            if(v[i]>pq.top()){
                pq.pop();
                pq.push(v[i]);
            }
        }
        return pq.top();

    }
};
int main(){
    vector<int > v={1,2,5,3,55,46,66};
    solution s;
    int res = s.KstNumArray(v,4);
    cout << res << endl;
    return 0;
}