Solution: Implement Two Stacks Using One Array
Let’s solve the Implementing Two Stacks Using One Array 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 integervalue
and inserts it into the first stack.push2(value)
: Takes an integervalue
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:
list.length
value
,value2
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 sizen
.Initialize two pointers,
top1
andtop2
, wheretop1
is set to -1 (indicating an empty stack1) andtop2
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 thetop2 - 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 thetop2 - 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: If yes, retrieve the element in the array at
top1
, decrementtop1
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
, incrementtop2
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.