Problem Definition: Sort a Stack using standard operations push,pop,isEmpty and peek.
This question is asked in cracking the coding interview.
Other ways of asking the question
Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that
should be used to write this program: push | pop | peek | isEmpty
Note - peek is equivalent to top() function in java, where you dont pop out the element but peek and see.
Solutions
- Use an additional array of size n, insert into array (Time Complexity O(n)). Use Counting Sort (Complexity O(n)). Memory overhead of O(m+n). OR O(n log n) if stack doesnt contains integer.
- Using the extra stack with time complexity of O(n^2)
- Use recursion with no additional space. The time complexity is O(n) and O(1) space complexity.
- Using quicksort in O(n logn)
** Method 1 - using the array and sort**
- Pop out all the elements from the stack and put in array- O(n)
- Sort the array - O(n) in case of counting sort for integer OR O(n log n) in case of other element.
- Push the elements in stack again (O (n)
Method 2 - Using extra stack
Here we are using 1 aux stack. Then we pop items from the original stack and push into the auxiliary stack into the correct position.
**Code : ** (credits)
public static Stack<Integer> sort(Stack<Integer> stack) {
Stack<Integer> auxiliary = new Stack<Integer>();
while (!stack.isEmpty()) {
Integer value = stack.pop();
while (!auxiliary.isEmpty() && value < auxiliary.peek())
stack.push(auxiliary.pop());
auxiliary.push(value);
}
return auxiliary;
}
Time complexity : O(n2) , Space complexity - O(n)
Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2
original\_stack : 2 1 9 8 5 3 7
|
top
Popping out 2
original\_stack : 1 9 8 5 3 7
|
top
aux\_stack : 2
|
top
Pop out 1 from original stack, and put it in right position. First we compare if elements in original stack is less than element at top of aux stack. If so we push the data in original stack from aux stack, and push the current top of original stack in aux stack.
value = original stack.pop = 1
original\_stack : 9 8 5 3 7
|
top
aux\_stack : 2
|
top
value < auxStack.top() i.e.1 <, 2 => , push value in aux stack.
original\_stack : 2 9 8 5 3 7
|
top
aux\_stack : 1
|
top
```And so on. Now we will insert 1,2,9,...and again 8 pops up, which pushes out 9 and inserts itself in aux stack. Finally we will get the proper stack. Here is the [**code**](https://github.com/kinshuk4/DataStructures/blob/master/src/com/vaani/ds/stack/application/SortAStack.java) on github in java, regarding the same.
**Method 3 - Using recursion and internal stack**
Here insert function does a trick, which inserts the element smaller than its top, below the top and larger element than the top at the top of the stack.
package com.vaani.ds.stack.application;
package com.vaani.ds.stack.application;
import java.util.Stack;
/**
* Sorts a stack using operations push,pop,peek and isEmpty
*
*/
public class StackSort {
public static void sort(Stack s){
int x=0;
if (!s.isEmpty()){
x=s.pop();
sort(s);
insert(s,x);
}
}
//At each step check if stack.peek > x, and insert below top recursively
public void insert(Stack s,int x){
//peek function returns the value of the top element without removing it
if (!s.isEmpty() && s.peek()>= x){
int y=s.pop();
insert(s, x);
s.push(y);
}else {
s.push(x);
}
}
public static void main(String[] a){
StackSort ss=new StackSort();
//initiate the stack of integers
Stack stack=new Stack();
//push the elements
stack.push(3);stack.push(4);stack.push(1);stack.push(2);
//sort the stack
ss.sort(stack);
for(int val: stack){
System.out.print(val+” “);
}
}
}
Time complexity - O(n)
Space complexity - O(1) \[if we are not considering the stack used while recursion\]
**_Understanding the logic_**
1. Pop out the current element x
2. Again call the sort recursively
3. After popping out, insert it if current top is more than x
**Method 4 - Mimic-ing quicksort ([credit](http://blog.pengyifan.com/sort-a-stack-in-ascending-order-in-on-log-n/))**
Can we do better? We can mimic the way of **[quicksort](http://en.wikipedia.org/wiki/Quicksort)** by picking a pivot from the stack (using _pop_) first. Then we conduct the _partition_ operation by _push_ing all elements in the stack with values less than the pivot into one stack, while all elements with values greater than the pivot into the other. After that, we recursively sort two sub-stacks and merge two at last with the pivot in the middle.
Because we can only use the stack structure, I pick the pivot using _pop_. The _merge_ operation is tricky and I am not sure if we can have a better way to combine two stacks. So if you have any idea, please let me know.
On average, this algorithm makes _O(n log n)_ comparisons to sort _n_ items. In the worst case, it makes _O(n2)_ comparisons, though this behavior is rare.
public static Stack sort(Stack s) {
if (s.isEmpty()) {
return s;
}
int pivot = s.pop();
// partition
Stack left = new Stack();
Stack right = new Stack();
while(!s.isEmpty()) {
int y = s.pop();
if (y < pivot) {
left.push(y);
} else {
right.push(y);
}
}
sort(left);
sort(right);
// merge
Stack tmp = new Stack();
while(!right.isEmpty()) {
tmp.push(right.pop());
}
tmp.push(pivot);
while(!left.isEmpty()) {
tmp.push(left.pop());
}
while(!tmp.isEmpty()) {
s.push(tmp.pop());
}
return s;
}
Thanks