• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

    用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail 和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。

    二、解题思路

    栈1用于存储元素,栈2用于弹出元素,负负得正。

    说的通俗一点,现在把数据1、2、3分别入栈一,然后从栈一中出来(3、2、1),放到栈二中,那么,从栈二中出来的数据(1、2、3)就符合队列的规律了,即负负得正。

    三、解题代码

    1. public class Test {
    2. public static class MList<T> {
    3. // 插入栈,只用于插入的数据
    4. private Stack<T> stack1 = new Stack<>();
    5. // 弹出栈,只用于弹出数据
    6. private Stack<T> stack2 = new Stack<>();
    7. public MList() {
    8. }
    9. // 添加操作,成在队列尾部插入结点
    10. public void appendTail(T t) {
    11. stack1.add(t);
    12. }
    13. // 删除操作,在队列头部删除结点
    14. public T deleteHead() {
    15. // 先判断弹出栈是否为空,如果为空就将插入栈的所有数据弹出栈,
    16. // 并且将弹出的数据压入弹出栈中
    17. if (stack2.isEmpty()) {
    18. while (!stack1.isEmpty()) {
    19. stack2.add(stack1.pop());
    20. }
    21. }
    22. // 如果弹出栈中还没有数据就抛出异常
    23. if (stack2.isEmpty()) {
    24. throw new RuntimeException("No more element.");
    25. }
    26. // 返回弹出栈的栈顶元素,对应的就是队首元素。
    27. return stack2.pop();
    28. }
    29. }
    30. }