算法题--用两个栈实现一个队列

> 阿里本地生活一面

A栈入，B栈出。B栈出时做如下检测：若B栈有元素，则出栈；若B栈没有元素，则将A栈中的元素入B栈，然后从B栈出。

### 2021.8.24改良
> 增加队列在特殊场景下储存容量的大小。之前无论如何不能储存2n个元素，通过特殊操作最多同时储存2n-1个；现在可以一次性添加2n个元素。

使用Java模拟栈：
```java
package xyz.riun.demo;

/**
 * @author: HanXu
 * on 2021/8/24
 * Class description: 栈
 * 先写简单的 储存数字的栈。先写入栈。
 */
public class Stack {

private int[] arr = new int[length];
    private int index = 0;
    private static final int length = 10;

public void push(int num) {
        if (size() >= length) {
            throw new RuntimeException("栈满");
        }
        arr[index] = num;
        index ++;
    }
    public int pop() {
        if (size() <= 0) {
            throw new RuntimeException("栈空");
        }
        index--;
        return arr[index];
    }

public int size() {
        return index;
    }

public boolean isFull() {
        return size() == length;
    }

public boolean isEmpty() {
        return size() == 0;
    }
}
```

使用两个栈模拟一个队列：

```java
package xyz.riun.demo;

/**
 * @author: HanXu
 * on 2021/8/24
 * Class description: 队列：两栈实现
 * 使用了两个栈的空间，但是却无法保证一定能使用到两栈空间
 * 最坏储存n + 1个元素
 * 最好储存2n个元素
 * n为栈的容量
 */
public class StackQueue {
    private Stack stack1 = new Stack();//入队列
    private Stack stack2 = new Stack();//出队列

//优化后的入队
    public void push(int num) {
        if (stack1.isFull()) {
            if (stack2.isEmpty()) {
                while (stack1.size() > 0) {
                    stack2.push(stack1.pop());
                }
            } else {
                throw new RuntimeException("队列已满");
            }
        }
        /*if (stack1.isFull()) {
            throw new RuntimeException("队列已满");
        }*/
        stack1.push(num);
    }

public int pop() {
        if (stack1.isEmpty() && stack2.isEmpty()) {
            throw new RuntimeException("队列已空");
        }
        if (stack2.size() > 0) {
            return stack2.pop();
        }
        while (stack1.size() > 0) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }

public int size() {
        return stack1.size() + stack2.size();
    }

//两栈实现的队列没有是否满的判断，因为有时候满了，在进行弹出一个的操作后还能在添加多于一个的元素
    public boolean canAdd() {
        return !stack1.isFull();
    }

public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}
```

测试：
```java
package xyz.riun.demo;

/**
 * @author: HanXu
 * on 2021/8/24
 * Class description:
 */
public class StackQueueDemo {
    public static void main(String[] args) {
        StackQueue stackQueue = new StackQueue();

//改良后的只有在特定条件下才能存20个元素
        /*for (int i = 0; i < 20; i++) {
            stackQueue.push(i + 1);
        }
        while (!stackQueue.isEmpty()) {
            System.out.println(stackQueue.pop());
        }*/

//储存元素容量[n+1, 2n]
        stackQueue.push(1);
        stackQueue.push(2);
        System.out.println(stackQueue.pop());
        for (int i = 0; i < 10; i++) {
            stackQueue.push(i + 3);
        }
        System.out.println(stackQueue.canAdd());
        //stackQueue.push(13);//java.lang.RuntimeException: 队列已满
        while (!stackQueue.isEmpty()) {
            System.out.println(stackQueue.pop());//11个元素
        }
    }
}
```

### 原版
使用Java模拟栈：

```java
package com.demo.StackQueue;

/**
 * @author: HanXu
 * on 2021/2/24
 * Class description: 栈
 */
public class Stack {

private int[] arr = new int[10];
    private int index = 0;

public int size() {
        return index > 0 ? index : 0;
    }

public void push(int e) {
        arr[index] = e;
        index ++;
    }

public int pop() {
        index --;
        return arr[index];
    }

public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(1);
        stack.push(2);
        stack.push(3);

System.out.println(stack.pop()); // 3
        System.out.println(stack.pop()); // 2
        System.out.println(stack.pop()); // 1
        // 先进后出
    }
}
```

使用两个栈模拟一个队列：

```java
package com.demo.StackQueue;

/**
 * @author: HanXu
 * on 2021/2/24
 * Class description: 使用两个栈实现一个队列
 */
public class StackQueueDemo {

private Stack A = new Stack();
    private Stack B = new Stack();

public void push(int e) {
        A.push(e);
    }

public int pop() {
        if (A.size() == 0 && B.size() == 0) {
            throw new  RuntimeException("队列已空");
        }

// 出队列，优先弹出B栈的元素
        if (B.size() != 0) {
            return B.pop();
        }
        // B没有元素时，将A栈中元素装入B栈中，这样元素的入栈顺序就颠倒了，所以使用B栈出栈时才会有“先进先出”的现象
        while (A.size() != 0) {
            B.push(A.pop());
        }
        // A->B 装完后，像上面一样弹出B栈元素
        return B.pop();
    }

public static void main(String[] args) {
        StackQueueDemo stackQueueDemo = new StackQueueDemo();
        stackQueueDemo.push(1);
        stackQueueDemo.push(2);
        stackQueueDemo.push(3);

System.out.println(stackQueueDemo.pop()); // 1
        System.out.println(stackQueueDemo.pop()); // 2
        System.out.println(stackQueueDemo.pop()); // 3
        // 先进先出
    }

}
```

栈和队列，栈和队列，栈和队列。脑子里想的是栈和队列，怎么说成了堆和栈，啊。。。

![](/image/8822df16-935f-47ab-82d5-08ea6d7ad9f7.jpg)

算法题--用两个栈实现一个队列

文章目录

发表评论