Solution: Implement Two Stacks Using One List

Statement

Design a data structure TwoStacks, that represents two stacks using a single list, where both stacks share the same list for storing elements.

The following operations must be supported:

• push1(value): Takes an integer value and inserts it into the first stack.

• push2(value): Takes an integer value and inserts it into the second stack.

• pop1(): Removes the top element from the first stack and returns it.

• pop2(): Removes the top element from the second stack and returns it.

Note: Perform all operations in-place without resizing the underlying list, maintaining a fixed size throughout.

Constraints:

• $1 \leq$ list.length $\leq 10^3$

• $-10^5\leq$ value, value2$\leq 10^5$

Solution: Stacks on opposite ends

The algorithm initializes an array with a specified size and two pointers, representing two empty stacks (one at the beginning and one at the end of the array). Pushing an element onto Stack 1 increments the first pointer to the next index within the array, while pushing onto Stack 2 decrements the second pointer to the previous index within the array. When popping from Stack 1, the top element at the first pointer’s position is returned, and the pointer is decremented to move one step backward in the array. Similarly, popping from Stack 2 retrieves the top element at the second pointer’s position, and the pointer is incremented to move one step forward in the array.

Here’s the algorithm:

1. Initialize the arr array with a specified size n.

2. Initialize two pointers, top1 and top2, where top1 is set to -1 (indicating an empty stack1) and top2 is set to the array size (indicating an empty stack2).

3. push1:

   1. Check if there is at least one empty space for the new element in stack1 by verifying if the top1 is less than the top2 - 1:

      1. If yes, increment top1 by 1 and insert the element in the array at this index.

      2. If no, print “Stack Overflow” and exit the operation.

4. push2:

   1. Check if there is at least one empty space for the new element in stack2 by verifying if the top1 is less than the top2 - 1:

      1. If yes, decrement top2 by 1 and insert the element in the array at this index.

      2. If no, print “Stack Overflow” and exit the operation.

5. pop1:

   1. Check if stack1 is not empty by verifying if the top1 is greater than or equal to $0$:

      1. If yes, retrieve the element in the array at top1, decrement top1 by 1, and return the retrieved element.

      2. If no, print “Stack Underflow” and exit the operation.

6. pop2:

   1. Check if stack2 is not empty by verifying if the top2 is less than the size of the array:

      1. If yes, retrieve the element in the array at top2, increment top2 by 1, and return the retrieved element.

      2. If no, print “Stack Underflow” and exit the operation.

Let’s look at the illustration below to better understand the solution: