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

LeetCode刷题记录：232. Implement Queue using Stacks

目录前言题目思路源码后记

前言从今天开始学习用C++来打代码，虽然已经学习过C和Java了，但在写的时候，脑子里总是想着面对对象，写来写去又感觉再写C一样。还是很不熟练，希望能边学边练。

题目用两个栈来实现队列。这是一个经典的数据结构问题。用栈来模拟队列，因为队列是先进先出，而栈是后进先出，所以需要巧妙地利用两个栈的特性来实现。

思路做这题得先理解栈和队列各自的特点。栈后进先出，队列先进先出。用两个栈来实现队列的操作，一个s1一个s2。

使用两个栈来实现队列操作，方法是：

• push操作：将x放在队列的最后。先将s2中的元素全部出栈到s1，然后将x进栈到s1，x就放在队尾。

• pop操作：将s1中的元素全部出栈到s2，将s2弹出一个元素，返回这个元素。

• peek操作：将s1有元素的部分全部出栈到s2，然后返回s2的top元素。

• empty操作：s1和s2均为空，则返回true，否则返回false。

源码

#include 
   
    using namespace std;class MyQueue {private:  stack
    
      s1;  stack
     
       s2;public:  MyQueue() {}    void push(int x) {    while (!s2.empty()) {      s1.push(s2.top());      s2.pop();    }    s1.push(x);  }  int pop() {    int item;    while (!s1.empty()) {      s2.push(s1.top());      s1.pop();    }    item = s2.top();    s2.pop();    return item;  }  int peek() {    while (!s1.empty()) {      s2.push(s1.top());      s1.pop();    }    return s2.top();  }  bool empty() {    return s1.empty() && s2.empty();  }};
     
    
   

后记做这样的栈和队列，主要抓住其各自的特点：栈后进先出，队列先进先出。最好做的时候画画示意图，就很清楚了。

转载地址：http://joyiz.baihongyu.com/