Leetcode刷题——栈与队列

Leetcode刷题——栈与队列

Leetcode刷题——栈与队列

一、栈与队列定义二、Leetcode题目

1.用栈实现队列2.用队列实现栈

一、栈与队列定义

栈：先进后出，栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。队列：先进先出，同样不允许有遍历行为，不提供迭代器, STL中队列一样是以deque为缺省情况下的底部结构。 二、Leetcode题目 1.用栈实现队列

232. 用栈实现队列

利用两个栈实现队列push实现很简单，pop实现较为复杂pop:将s1元素d出压入到s2中，再d出s2的栈顶元素即可实现队列pop.注：先确认s2是空栈，再while循环将s1所有元素压入s2中。peek:取队列头元素再使用pop后需要再把pop的元素压回去。empty:s1.empty()&s2.empty()

class MyQueue {
    stacks1;
    stacks2;
public:
    MyQueue() {
        
    }
    void push(int x) {
        s1.push(x);
    } 
    int pop() {
        if(s2.empty()){
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }}
        int result=s2.top();
        s2.pop();
        return result;
    }
    int peek() {
        int res=this->pop();
        s2.push(res);
        return res;
    }
    bool empty() {
        return s1.empty()&&s2.empty();
    }
};

2.用队列实现栈

225. 用队列实现栈

使用一个队列实现栈push实现很简单，pop实现较为复杂由于栈是先进后出，所以想办法将队列的尾元素放到队列首部。即进行q.size()-1次循环完成。循环结束后pop出q.front()元素。top:栈的顶即为队列的尾，q.back()取出，也可使用pop再pushempty:q.empty()

class MyStack {
    queueq;
public:
    MyStack() {
    }
    void push(int x) {
        q.push(x);
    }
    int pop() {
        int size=q.size()-1;
        while(size>0){
            int temp=q.front();
            q.push(temp);
            q.pop();
            size--;
        }
        int res=q.front();
        q.pop();
        return res;
    }
    int top() {
        return q.back();
    }
    bool empty() {
        return q.empty();
    }
};