232.用栈实现队列[easy]

2019-04-28 阅读量32

LeetCode 算法题停止更新，请移步至 GitHub。

题目描述

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

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

示例

MyQueue queue = new MyQueue();

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

说明

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

解题方法

1.使用 stack

队列，先进先出；栈，先进后出；用栈实现队列，需要将栈中的元素顺序颠倒一下，由此可以想出使用两个栈来完成。
push：直接使用栈 a 的 push 方法即可。
pop：需要将栈 a 中的栈顶元素出栈，放入栈 b 中，即完成了一次倒序。（注意这种情况，当 pop 了一次之后，又进行一次 push 操作，再进行 pop 操作，如果是直接将 a 中的栈顶元素压如 b 中，会导致最后 pop 的是上次 push 进来的值，导致顺序错乱。所以只有当 b 为空时，才能将 a 栈顶元素压入 b 中，保证顺序不错乱）
peek：返回队列第一个元素，也就是返回 b 中的栈顶元素。注意，这里只是返回栈顶元素，而不是弹出栈顶元素，不需要进行 pop，否则后面进行判空时会出现问题。
empty：一开始的思路是将栈 a 中的所有元素压入栈 b 中进行判断，但是这样会改变数据的位置，不仅增加了多余的操作，还可能会对后面的操作产生影响。后面直接判断两个栈是否都为空就好了。

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        a.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (b.empty()) {
            while (!a.empty()) {
                int tmp = a.top();
                a.pop();
                b.push(tmp);
            }
        }
        
        int tmp = b.top();
        b.pop();
        return tmp;
    }
    
    /** Get the front element. */
    int peek() {
        if (b.empty()) {
            while (!a.empty()) {
                int tmp = a.top();
                a.pop();
                b.push(tmp);
            }
        }

        int tmp = b.top();
        return tmp;
        
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return a.empty() && b.empty();
    }
    
private:
    stack<int> a;
    stack<int> b;
};

/**
 * 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();
 */

状态	执行用时	内存消耗
通过	8 ms	8.9 MB

2.使用 deque

这是范例代码，用双向队列来实现队列，个人觉得有些不符合题目要求，欠妥。

deque 也是顺序容器的一种，同时也是一个可变长数组。要使用 deque，需要包含头文件 deque。所有适用于 vector 的操作都适用于 deque。

deque 和 vector 有很多类似的地方。在 deque 中，随机存取任何元素都能在常数时间内完成（但慢于vector）。它相比于 vector 的优点是，vector 在头部删除或添加元素的速度很慢，在尾部添加元素的性能较好，而 deque 在头尾增删元素都具有较好的性能（大多数情况下都能在常数时间内完成）。它有两种 vector 没有的成员函数：

1 2	void push_front (const T & val); //将 val 插入容器的头部 void pop_front(); //删除容器头部的元素


class MyQueue {
private:
	deque<int> di;
public:

	
		/** Initialize your data structure here. */
		MyQueue() {

	}

	/** Push element x to the back of queue. */
	void push(int x) {
		di.push_back(x);
	}

	/** Removes the element from in front of queue and returns that element. */
	int pop() {
		int num = peek();
		di.pop_front();
		return num;
	}

	/** Get the front element. */
	int peek() {
		return di.front();
	}

	/** Returns whether the queue is empty. */
	bool empty() {
		return di.empty();
	}
};