Java 程序实现一个数组中的两个栈

在本节中，我们将创建一个在数组中实现两个栈的 Java 程序。

两个栈的含义是指两个栈都应使用相同的数组来存放元素。以下是这两个栈必须实现的一些方法。

push1(int i) -> 将 i 推入第一个栈

push2(int j) -> 将 j 推入第二个栈

pop1() -> 从第一个栈中移除顶部元素，然后返回弹出的元素。

pop2() -> 从第二个栈中移除顶部元素，然后返回弹出的元素。

注意：两个栈的实现应具有空间效率。

朴素方法

简单的做法是将给定的数组分成两半，然后将这些半部分用作栈。但是，这可能会导致内存使用效率低下。例如，假设给定数组的大小为 6。因此，每个栈的大小将为 3。另外，假设我们需要将 4 个元素推入第一个栈，将 1 个元素推入第二个栈。我们可以轻松地将 1 个元素放入第二个栈。

但是，我们只能将 3 个元素推入第一个栈。推入第 4 个元素将导致溢出。理想情况下，这种情况不应该发生，因为第二个栈中存在一些空闲区域（仍有 2 个元素的空间为空），可以使用。但是，我们不能将其用于第一个栈，因为它已经分配给了第二个栈。因此，我们可以说，两个栈的简单实现方法将没有空间效率。

为了使实现具有空间效率，需要根据需要分配两个栈的空间。该概念是将两个栈从输入 arr[] 的两个极端侧开始。栈 1 从左侧开始，这意味着栈 1 中的第一个元素推入索引 0。栈 2 从右侧开始。栈 2 中的第一个元素推入索引 size - 1。

两个栈都从相反的方向收缩或增长。为了检查溢出，需要关注位于两个栈顶部之间的元素空间。以下程序显示了这一点。

文件名： TwoStacksArray.java

输出

The popped element from the stack 1 is: 191
The popped element from the stack 2 is: 40

复杂度分析： 对于 push 和 pop 操作，需要恒定时间。因此，对于这些操作，时间复杂度为 O(1)。