数据结构之栈模拟队列,队列模拟栈轻松攻破_怎么用两个栈模仿队列

题外话

最近博客写的还是很频繁的,就是没太大技术活,等我多学学,现学现卖

正题

大家需要熟练掌握队列先进先出原则,栈先入后出原则,并且在模拟的时候能转变思维

栈模拟队列

思路

要注意我们是用栈去实现队列的底层,栈遵循先进后出原则而队列遵循先进先出原则,当我们删除元素,查看队头元素时,一定要记住它们遵循的原则!!

栈模拟队列需要用两个栈,一个入栈,一个出栈

建立s1和s2两个栈,让s1作为入队,s2作为出队

public class MyQueue {

Stack<Integer> s1;
Stack<Integer> s2;
//实例化s1和s2
        public MyQueue() {
            s1=new Stack<>();
            s2=new Stack<>();
        }
//入队只需要把元素添加到s1即可
        public void push(int x) {

                s1.push(x);
        }
//出队
        public int pop() {
//当s1和s2都为空时返回-1
      if (empty()) {
          return -1;
      }
s2作为出队如果里面为空
            if (s2.empty())
            {
//s1里面不为空如上图我们要把1删除,只需要直接把s1内的元素,3,2,1的顺序拿出放入s2中,而s2.pop()就是1
                while (!s1.empty())
                {
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }

        public int peek() {
//两个栈都为空时直接返回-1
            if (empty())
            {
                return -1;
            }
//s1里面不为空如上图我们要查看1,只需要直接把s1内的元素,3,2,1的顺序拿出放入s2中,而s2.peek()就是1
            if(s2.empty())
            {
                while (!s1.empty())
                {
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }

只需要判断s1和s2是否都为空即可
        public boolean empty() {
     return s1.empty()&&s2.empty();

        }
}

队列实现栈

思路

只需要熟练运用队列和栈的原则,还有一些差异即可

public class stackTest02 {
    //创建q1和q2两个队
   Queue<Integer> q1;
   Queue<Integer> q2;


        public stackTest02() {
            //给q1,q2进行实例化
       q1=new LinkedList<>();
       q2=new LinkedList<>();
        }

        //push的时候只需要把元素放入空的队即可,如果两个队都为空放入q1中
        public void push(int x) {
        if (!q1.isEmpty())
        {
            q1.offer(x);
        }
        else if (!q2.isEmpty())
        {
            q2.offer(x);
        }
        else {
            q1.offer(x);
        }
        }
    //删除元素,我们需要先判断q1和q2哪个不为空或者都为空,
    //队列是先进先出,栈是先进后出
    //找到不为空的队列,把队列内只留一个元素,剩下都放入另一个队列,最后把队列内剩的一个元素删除即可
        public int pop() {
        if (!q1.isEmpty())
        {
            while (q1.size()-1!=0) {
                q2.offer(q1.poll());
            }
            return q1.poll();
        }
        else if (!q2.isEmpty())
        {
            while (q2.size()-1!=0) {
                q1.offer(q2.poll());
            }
           return q2.poll();        }
        else {
            return -1;
        }
        }
    //查看栈顶元素,只需要把不为空的队列内元素留下一个,剩下的全部放入另一个队列中,剩下的元素即是栈顶元素,记录下栈顶元素,放入另一个队列中即可
        public int top() {
            if (!q1.isEmpty()) {
                while (q1.size() - 1 != 0) {
                    q2.offer(q1.poll());
                }
                int x = q1.poll();
                q2.offer(x);
                return x;
            } else if (!q2.isEmpty()) {
                while (q2.size() - 1 != 0) {
                    q1.offer(q2.poll());
                }
                int x = q2.poll();
                q1.offer(x);
                return x;
            }
            else
            {
                return -1;
            }
        }
//只需要检测q1和q2是否都为空即可
        public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
        }

}

小结

这一次一点要赢,

十年磨一剑