算法模型总结：栈与队列

1.栈实现队列

232. 用栈实现队列

使用两个栈来实现队列，其中一个栈用来入，一个栈用来出，当要插入或者删除数据的时候，将数据从一个栈导入到要操作的栈即可。‘

class MyQueue {
private: 
    stack s1;
    stack s2;
public:
    MyQueue() {
        
    }
    void exchange(stack& s1,stack& s2)
    {
        int temp;
        while(!s1.empty())
        {
            temp=s1.top();
            s1.pop();
            s2.push(temp);
        }
    }
    void push(int x) {
        exchange(s2,s1);
        s1.push(x);
    }
    
    int pop() {
        exchange(s1,s2);
        int temp=s2.top();
        s2.pop();
        return temp;
    }
    int peek() {
        exchange(s1,s2);
        return s2.top();
    }
    bool empty() {
        return s1.empty()&&s2.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();
 */
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

2.队列实现栈

225. 用队列实现栈

使用一个队列就可以实现栈，当入栈的时候再队尾插入，出栈的时候依次将队首的元素移动到队尾，当找到最后一个元素的时候将它出栈。

class MyStack {
private:
    queue q;
public:
    MyStack() {

    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size=q.size()-1;
        while(size--)
        {
            int tmp=q.front();
            q.pop();
            q.push(tmp);
        }
        int tmp=q.front();
        q.pop();
        return tmp;
    }
    
    int top() {
        return q.back();
    }
    
    bool empty() {
        return q.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();
 */
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

3.有效的括号

20. 有效的括号

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

有效字符串需满足：

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

遍历整个数组，如果遇到左括号，则将括号入栈，如果遇到右括号，看栈顶元素是不是该右括号，是则出栈，不是则退出。

class Solution {
public:
    bool isValid(string s) {
        stack S;
        for(int i=0;i

class Solution {
public:
    string removeDuplicates(string s) {
        stack S;
        for(int i=0;i