栈和队列(使用C++实现)

😲示例

栈是一种先进后出(后进先出)的结构, 与之对应, 队列是一种先进先出(后进后出)的结构

STL中的栈的底层实现可以是vector，deque，list

可以使用下面语句指定栈的底层实现

1
std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

缺省状态下将会使用deque为栈的底层实现
deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了

栈的常用方法示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <stack>

int main() {
    std::stack<int> myStack;

    // 入栈
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);

    // 访问栈顶元素
    std::cout << "Top element: " << myStack.top() << std::endl;

    // 出栈
    myStack.pop();

    // 检查栈是否为空
    if (myStack.empty()) {
        std::cout << "Stack is empty" << std::endl;
    } else {
        std::cout << "Stack is not empty" << std::endl;
    }

    return 0;
}

队列的常用方法示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    // 入队
    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);

    // 访问队首元素
    std::cout << "Front element: " << myQueue.front() << std::endl;

    // 出队
    myQueue.pop();

    // 检查队列是否为空
    if (myQueue.empty()) {
        std::cout << "Queue is empty" << std::endl;
    } else {
        std::cout << "Queue is not empty" << std::endl;
    }

    return 0;
}

🤔一些疑问解答

pop()函数是否可以返回值?

C++中pop()不能返回值, 只是删除一个元素而已, 这也符合最基本的弹出功能, 想要查看元素, 栈stack使用top(), 队列queue使用front()

💪力扣刷题

232. 用栈实现队列

力扣传送门

入栈操作都放到stack_in里面, 查看栈顶或者弹出操作, 都放到另一个stack_out中, 第二个栈由第一个栈一个一个弹出所填充, 所哟它的弹出顺序使相反的, 两个栈都是后进先出, 两个栈串联起来就是先进先出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class MyQueue {
public:
    stack<int> in;
    stack<int> out;
    MyQueue() {

    }
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        if(!out.empty()){
            int a = out.top();
            out.pop();
            return a;
        }
        else{
            int a;
            while(!in.empty()){
                a = in.top();
                in.pop();
                out.push(a);
            }
            a = out.top();
            out.pop();
            return a;
        }
    }
    
    int peek() {
        if(!out.empty())
            return out.top();
        else{
            while(!in.empty()){
                int a = in.top();
                in.pop();
                out.push(a);
            }
            return out.top();
        }
    }
    
    bool empty() {
        return in.empty() && out.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();
 */

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

力扣传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string removeDuplicates(string s) {
        int delete_num = 0;
        stack<char> st;
        int len = s.size();
        for(int i=0; i<len; i++){
            if(st.empty())
                st.push(s[i]);
            else if(st.top()==s[i]){
                st.pop();
                delete_num+=2;    
            }
            else
                st.push(s[i]);
        }
        s.resize(len-delete_num);
        len = s.size();
        for(int i=len-1; i>=0; i--){
            s[i] = st.top();
            st.pop();
        }
        return s;
    }
};

20. 有效的括号

力扣传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isValid(string s) {
        stack<char> myStack;
        for(char a : s){
            if(a=='(' || a=='[' || a=='{')
                myStack.push(a);
            else if(myStack.empty())
            	return false;  
            else if(a==')' && myStack.top()=='(')
                myStack.pop();
            else if(a==']' && myStack.top()=='[')
                myStack.pop();
            else if(a=='}' && myStack.top()=='{')
                myStack.pop();
            else return false;
        }
        if(myStack.empty())
            return true;
        return false;
    }
};

150. 逆波兰表达式求值

力扣传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;               // 栈s用于存数字
        int len = tokens.size();    // 向量长度
        int a,b;                    // 用于保存取出来的两个数, 提前创建变量, 防止在循环中反复创建变量浪费时间
        for(int i=0; i<len; i++){
            if(tokens[i]=="+"){         // +
                a = s.top();
                s.pop();
                b = s.top();
                s.pop();
                s.push(a+b);
            }else if(tokens[i]=="-"){   // -
                a = s.top();
                s.pop();
                b = s.top();
                s.pop();
                s.push(b-a);
            }else if(tokens[i]=="*"){   // *
                a = s.top();
                s.pop();
                b = s.top();
                s.pop();
                s.push(a*b);
            }else if(tokens[i]=="/"){   // /
                a = s.top();
                s.pop();
                b = s.top();
                s.pop();
                s.push(b/a);
            }else{                      // 遇到数字需要转换
                s.push(turn_to_num(tokens[i]));
            }
        }
        return s.top();
    }
    int turn_to_num(string s){          // 将字符串转换为数字
        int start = (s[0]=='-')?1:0;    // 如果是负数则从索引为1的位置开始表示数字部分
        int len = s.size();             // 字符串长度
        int num = 0;                    // 记录解析到的数字, 会随着解析的位数增加而增加
        int a;                          // 用于保存某一位的数字, 提前创建防止在循环中反复创建浪费时间
        for(int i=start; i<len; i++){
            a = s[i]-'0';               // 第i位数字
            num = num*10+a;             // num*10+a为新的数字
        }
        return (start==1)?(0-num):num;  // 返回数字, 注意正负
    }
};

347. 前 K 个高频元素

力扣传送门

1