This is my attempted solution to cracking the coding interview exercise 3.5. Looking for any feedback on coding style or the algorithm anywhere I can improve really.
The problem specification is as follows.
Write a program to sort a stack such that the smallest items are on the top. You can use an additional temp stack, but you may not copy the elements into any other data structure (such as an array). The stack supports push, pop, peek and isEmpty.
MyStack.java
package problem_2_8;
import java.util.ArrayList;
import java.util.EmptyStackException;
public class MyStack<T extends Comparable<T>> {
private static class StackNode<T extends Comparable<T>> {
T data;
StackNode<T> next;
StackNode(T data){
this.data = data;
}
}
private StackNode<T> top = null;
private int size;
public MyStack(){}
public int size(){
return size;
}
T pop(){
if(top == null) throw new EmptyStackException();
T item = top.data;
top = top.next;
size--;
return item;
}
void push(T data){
StackNode<T> node = new StackNode<T>(data);
if(top != null){
node.next = top;
}
top = node;
size++;
}
T peek(){
if(top == null) throw new EmptyStackException();
return top.data;
}
boolean isEmpty(){
return size == 0;
}
void sortStack(){
MyStack<T> tempStack = new MyStack<T>();
while(!isEmpty()){
tempStack.insertToSortedStack(this, pop());
}
while(!tempStack.isEmpty()){
push(tempStack.pop());
}
}
void insertToSortedStack(MyStack<T> auxStack, T item){
int countPops = 0;
while(!isEmpty() && item.compareTo(peek()) < 0){
auxStack.push(pop());
countPops++;
}
push(item);
for(int i = 0; i < countPops; i++){
push(auxStack.pop());
}
}
void printStack(){
StackNode<T> current = top;
ArrayList<String> stackAsString = new ArrayList<String>();
while(current != null){
stackAsString.add(current.data.toString());
current = current.next;
}
System.out.println("Top -> " + String.join(", ", stackAsString));
}
}
I ran the code as follows to test that the sorting works as expected.
Main.java
package problem_2_8;
public class Main {
public static void main(String[] args) {
MyStack<Integer> myStack = new MyStack<Integer>();
myStack.push(5);
myStack.push(7);
myStack.push(11);
myStack.push(5);
System.out.println("Stack before sorting: ");
myStack.printStack();
myStack.sortStack();
System.out.println("Stack after sorting: ");
myStack.printStack();
MyStack<String> myStackOfStrings = new MyStack<String>();
myStackOfStrings.push("x");
myStackOfStrings.push("c");
myStackOfStrings.push("y");
myStackOfStrings.printStack();
myStackOfStrings.sortStack();
myStackOfStrings.printStack();
}
}
