这是悦乐书的第195次更新，第201篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第57题（顺位题号是232）。使用栈实现队列的以下操作。

push（x） - 将元素x推送到队列的后面。

pop（） - 从队列前面删除元素。

peek（） - 获取前面的元素。

empty（） - 返回队列是否为空。

例如：

MyQueue queue = new MyQueue（）;

queue.push（1）;

queue.push（2）;

queue.peek（）; //返回1

queue.pop（）; //返回1

queue.empty（）; //返回false

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

队列的特性是先进先出，而栈的特性是先进后去，在使用栈进行队列的出队列和队顶操作时，需要借助另外一个栈来进行反转然后再还原，而入队列的操作还是无需特殊处理。

class MyQueue {    private Stack
    
      stack;    /** Initialize your data structure here. */    public MyQueue() {        stack = new Stack
     
      ();    }    /** Push element x to the back of queue. */    public void push(int x) {        stack.push(x);    }    /** Removes the element from in front of queue and returns that element. */    public int pop() {        Stack
      
        temp = new Stack
       
        ();        while (!stack.isEmpty()) {            temp.push(stack.pop());        }        int tem = temp.pop();        while (!temp.isEmpty()) {            stack.push(temp.pop());        }        return tem;    }    /** Get the front element. */    public int peek() {        Stack
        
          temp = new Stack
         
          (); while (!stack.isEmpty()) { temp.push(stack.pop()); } int tem = temp.peek(); while (!temp.isEmpty()) { stack.push(temp.pop()); } return tem; } /** Returns whether the queue is empty. */ public boolean empty() { return stack.isEmpty(); }}
         
        
       
      
     
    

03 第二种解法

此解法和上面的第一种解法正好相反，是在入队列的时候，借助另外一个栈来进行反转操作，而出队列和获取队列顶的操作可以直接使用栈的方法，无需特殊处理。

class MyQueue2 {    Stack
    
      stack;    /** Initialize your data structure here. */    public MyQueue2() {        stack = new Stack
     
      ();    }    /** Push element x to the back of queue. */    public void push(int x) {        Stack
      
        temp=new Stack<>();        while(!stack.isEmpty()){            temp.push(stack.pop());        }        temp.push(x);        while(!temp.isEmpty()){            stack.push(temp.pop());        }    }    /** Removes the element from in front of queue and returns that element. */    public int pop() {        return stack.pop();    }    /** Get the front element. */    public int peek() {        int a = stack.pop();        stack.push(a);        return a;    }    /** Returns whether the queue is empty. */    public boolean empty() {        return stack.isEmpty();    }}
      
     
    

04 第三种解法

此解法使用两个栈s1、s2来实现队列的相关操作。

入队列时，如果s2不为空，那么先把s2中的元素pop出来在push进s1，然后才去将当前要插入的数据push进s1。

出队列时，如果s2为空，即此前没有进行出队列操作或者获取队列顶的操作，那么就需要将s1反转，即将s1的元素pop出来，然后push进s2中，此时再返回s2的pop操作即可。如果s2不为空，即说明上一次操作不是入队列，而是出队列或获取队列顶的操作，直接返回s2的pop操作即可。

获取队列顶时，和入队列操作时的判断一致，只不过最后返回s2的peek操作即可。

class MyQueue3 {    private Stack
    
      s1;    private Stack
     
       s2;    /** Initialize your data structure here. */    public MyQueue3() {        s1 = new Stack
      
       ();        s2 = new Stack
       
        ();    }    /** Push element x to the back of queue. */    public void push(int x) {        while(!s2.empty()) {            s1.push(s2.pop());        }        s1.push(x);    }    /** Removes the element from in front of queue and returns that element. */    public int pop() {        if (s2.empty()) {            while (!s1.empty()) {                s2.push(s1.pop());            }        }         return s2.pop();    }    /** Get the front element. */    public int peek() {        if (s2.empty()) {            while (!s1.empty()) {                s2.push(s1.pop());            }        }        return s2.peek();    }    /** Returns whether the queue is empty. */    public boolean empty() {        return (s1.empty() && s2.empty());    }}
       
      
     
    

05 第四种解法

在入队列时，始终往第一位插入元素，而其他的出队列、获取队列的顶、判空这些操作都可以直接使用栈的方法，而无需重新实现。

class MyQueue4 {    private Stack
    
      stack;    /** Initialize your data structure here. */    public MyQueue4() {        stack = new Stack
     
      ();    }    /** Push element x to the back of queue. */    public void push(int x) {        stack.add(0, x);    }    /** Removes the element from in front of queue and returns that element. */    public int pop() {        return stack.pop();    }    /** Get the front element. */    public int peek() {        return stack.peek();    }    /** Returns whether the queue is empty. */    public boolean empty() {        return stack.isEmpty();    }}
     
    

06 小结

算法专题目前已连续日更超过一个月，算法题文章57+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！