剑指offer——用两个栈实现队列

我会带着你远行 2022-05-17 10:21 317阅读 0赞

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

实现及原理

  • 栈，具有先进后出的特点；而队列具有先进先出的特点
  • 通过两个栈实现队列的特点，那么一个栈就需要作为压入栈，一个栈作为弹出栈。压入数据进压入栈，弹出数据从弹出栈出。
  • 在弹出数据时，需要判断弹出栈中是否还有数据，若还有剩余数据未被弹出，则直接弹出数据。否则，需要从压入栈中将数据导入弹出栈，再进行数据的弹出。

参考代码

  1. import java.util.Stack;
  3. /**
  4.  * 
  5.  * @author LXH
  6.  *
  7.  */
  8. public class StackToQueue {
  9.     // 压入栈
  10.     Stack<Integer> stack1 = new Stack<Integer>();
  11.     // 弹出栈
  12.     Stack<Integer> stack2 = new Stack<Integer>();
  14.     public void push(int node) {
  15.         stack1.push(node);
  16.     }
  18.     public int pop() {
  19.         // 如果两个队列均为空，则不能在进行弹出操作，抛出运行时异常。
  20.         if(stack1.empty() && stack2.empty()) {
  21.             throw new RuntimeException("Queue is Empty");
  22.         }
  23.         // 若弹出栈不为空，则直接从弹出站中弹出相应的数据即可。
  24.         if(!stack2.empty()) {
  25.             return stack2.pop();
  26.         }
  27.         // 否则，需要将数据从压入栈中倒进弹出栈。
  28.         while(!stack1.isEmpty()) {
  29.             stack2.push(stack1.pop());
  30.         }
  31.         return stack2.pop();
  32.     }
  34.     public static void main(String[] args) {
  35.         StackToQueue stackToQueue = new StackToQueue();
  37.         stackToQueue.push(0);
  38.         stackToQueue.push(1);
  39.         stackToQueue.push(2);
  40.         stackToQueue.push(3);
  41.         stackToQueue.push(4);
  42.         stackToQueue.push(5);
  43.         stackToQueue.push(6);
  45.         System.out.println(stackToQueue.pop());
  46.         System.out.println(stackToQueue.pop());
  47.         System.out.println(stackToQueue.pop());
  48.         System.out.println(stackToQueue.pop());
  49.         System.out.println(stackToQueue.pop());
  50.     }
  51. }

运行结果

70

  1.    本题作为剑指offer中的题目，还是很受面试官们的青睐的，前一段时间的京东面试官就问到了这个题目的变形题目，不过万变不离其宗。把握住其中心思想，相信其他变形题目大家也是可以解决的。

发表评论

表情：
评论列表 （有 0 条评论，317人围观）

还没有评论，来说两句吧...

相关阅读