本文共 5704 字，大约阅读时间需要 19 分钟。

目录

leetcode 225 用队列实现栈

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空

注意:

• 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

思考：

栈是特性是先进后出，队列的特性是先进先出。可以用两个队列来实现栈的功能。

push和pop功能——用一个队列保持为空，另一个队列负责入栈操作。当有出栈操作时，将非空队列中的元素依次出队，存入那个空队列中，最后一个元素出队的时候返回给客户端。这样就可以一直保持一个队列是空的，返回给客户端的元素也是最后入队的那个元素。

top功能——返回非空队列的back元素即可。

class MyStack {public:	/** Initialize your data structure here. */	MyStack() {}	/** Push element x onto stack. */	void push(int x) {		if (q1.empty()) {			q2.push(x);		}		else {			q1.push(x);		}	}	/** Removes the element on top of the stack and returns that element. */	int pop() {		if (q1.empty()) {			while (q2.size() != 1) {				q1.push(q2.front());				q2.pop();			}			res = q2.front();			q2.pop();		}		else if (q2.empty()) {			while (q1.size() != 1) {				q2.push(q1.front());				q1.pop();			}			res = q1.front();			q1.pop();		}		else {			res = 0;		}		return res;	}	/** Get the top element. */	int top() {		if (q1.empty()) {			if (q2.empty()) {				return 0;			}			else {				return q2.back();			}		}		else {			return q1.back();		}	}	/** Returns whether the stack is empty. */	bool empty() {		if (q1.empty() && q2.empty())			return true;		return false;	}private:	queue
   
    q1;	queue
    
     q2;	int res;};
    
   

leetcode 232 用栈实现队列

使用栈实现队列的下列操作：

• push(x) -- 将一个元素放入队列的尾部。
• pop() -- 从队列首部移除元素。
• peek() -- 返回队列首部的元素。
• empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();queue.push(1);queue.push(2);  queue.peek();  // 返回 1queue.pop();   // 返回 1queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

思路：

一个栈作为出队栈，一个栈作为入队栈。

push操作——向入队栈中压入元素

pop操作——若出队栈为空，则将入队栈中的元素全部存入出队栈中，然后返回出队栈的栈顶元素。

                    若出队栈不为空，则返回栈顶元素。

peek操作——返回出队栈的栈顶元素

class MyQueue {public:    /** Initialize your data structure here. */    MyQueue() { }        /** Push element x to the back of queue. */    void push(int x) {        in.push(x);    }        /** Removes the element from in front of queue and returns that element. */    int pop() {        if(out.empty()){            while(!in.empty()){                out.push(in.top());                in.pop();            }        }        res=out.top();        out.pop();        return res;    }        /** Get the front element. */    int peek() {        if(out.empty()){            while(!in.empty()){                out.push(in.top());                in.pop();            }        }        res=out.top();        return res;    }        /** Returns whether the queue is empty. */    bool empty() {        if((in.empty())&&(out.empty()))            return true;        return false;    }private:    stack
   
    in;    stack
    
     out;    int res;};
    
   

leetcode 155最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) -- 将元素 x 推入栈中。
• pop() -- 删除栈顶的元素。
• top() -- 获取栈顶元素。
• getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();   --> 返回 -3.minStack.pop();minStack.top();      --> 返回 0.minStack.getMin();   --> 返回 -2.

思路：（主要是考察你的细心程度，细心，细心啊~~~~~~~~~~~~~~~）

写一个类，里面包含两个栈，一个栈用于正常的栈功能，一个栈用于存储当前栈中最小元素，名为最小栈。

push操作——正常栈入栈，如果最小值为空，则入栈，如果最小栈非空，则检查该元素的值是否小于最小栈的栈顶元素的值，如果小，则入栈，否则，入栈一个最小栈的栈顶元素（保持两个栈中的元素个数相同）

pop操作——若正常栈非空，则正常栈出栈，最小栈出栈（保持两个栈中的元素个数相同）

top操作——若正常栈的元素非空，则返回正常栈的栈顶

getmin操作——若最小栈的元素非空，返回最小栈的栈顶。

class MinStack {public:    /** initialize your data structure here. */    MinStack() { }        void push(int x) {        normal.push(x);        if(!min.empty()){            if(x