An algorithm to implement two stacks with a single array.
We are going to create a data structure called twoStacks which will be using only a single array to store the data but will act as two different stacks.
The twoStacks data structure will perform the following operations.
- push1(elm): This will add data in the first stack.
- push2(elm): This will add data in the second stack.
- pop1(): This will remove the data from the first stack.
- pop2(): This will remove the data from the second stack.
Example
Implementation of two stacks with an array.
There are two different ways in which we can implement this.
Method 1: By dividing the array into two equal halves
The simplest way is to implement two stacks in an array is by dividing the array into two equal halves and using these halves as two different stacks to store the data.
This method works fine, however, it is not space-efficient because suppose we have two stacks with 4 and 6 elements and our array is of 10 lengths. No, if we divide our array into two equal halves then it is going to have two stacks of length 5. If we push only 4 items in the first stack then it has one space vacant and when we try to push 6 items in the second stack it will overflow because it only has a capacity of 5. We could have used the 1 vacant space of the first stack to store the data.
Method 2: Space-efficient method.
This method is very space-efficient and it does not overflow if there is space available in the array or any of the stack.
The concept we use here is we store the data on the two different ends in the array (from start and from end).
The first stack stores the data from the front that is at index 0 and the second stack stores the data from the end that is the index ArraySize-1.
Both stack push and pop data from opposite ends and to prevent the overflow we just need to check if there is space in the array.
Time complexity
| # | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Average | Θ(N) | Θ(N) | Θ(1) | Θ(1) |
| Worst | O(N) | O(N) | O(N) | O(N) |
Space complexity
| # | Space |
|---|---|
| Worst | O(N) |
Preparing for javascript interview then do checkout learnersbucket.com for 150+ solved problems for practice. I am sure it may help you .😎.
I started to share the solved examples in javascript only because I failed many interviews initially.
If you feel this is a helpful resource then please share these with others who are actively interviewing.
Also, follow me on Twitter for tips and tricks to solve the coding interviews and more solved examples of Algorithms. I write 2 - 3 post weekly on my blog learnersbucket.com.
Top comments (1)
can't we use 2 nested arrays , one for each stack ?