# Solution: Implement Two Stacks Using One List

Let’s solve the Implementing Two Stacks Using One List problem.

## We'll cover the following

## 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:

Initialize the

`arr`

array with a specified size`n`

.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).`push1`

: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`

:If yes, increment

`top1`

by 1 and insert the element in the array at this index.If no, print “Stack Overflow” and exit the operation.

`push2`

: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`

:If yes, decrement

`top2`

by 1 and insert the element in the array at this index.If no, print “Stack Overflow” and exit the operation.

`pop1`

:Check if stack1 is not empty by verifying if the

`top1`

is greater than or equal to$0$ :If yes, retrieve the element in the array at

`top1`

, decrement`top1`

by 1, and return the retrieved element.If no, print “Stack Underflow” and exit the operation.

`pop2`

:Check if stack2 is not empty by verifying if the

`top2`

is less than the size of the array:If yes, retrieve the element in the array at

`top2`

, increment`top2`

by 1, and return the retrieved element.If no, print “Stack Underflow” and exit the operation.

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

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.