Sort a stack in ascending order. You may only use one additional stack to hold items.
Any comments on my solution? Worst case complexities: Memory complexity: O(n) Runtime complexity: O(n^2)
Also, I implemented the Stack class as having Object items and then cast these into Integers to be more general. Is this a good way of doing this?
import org.junit.Test;
public class Solution {
// Sort a stack in ascending order
// May only use one additional stack to hold items
// Stack supports push, pop, peek, and isEmpty
private Stack stack;
private Stack auxiliaryStack;
@Test
void testStackIncreasingOrder() {
stack = new Stack();
stack.push(3);
stack.push(2);
stack.push(1);
System.out.println("original stack");
printStack();
sortStack();
System.out.println("Sorted stack");
printStack();
}
@Test
void testEmptyStack(){
stack = new Stack();
System.out.println("original stack");
printStack();
sortStack();
System.out.println("Sorted stack");
printStack();
}
@Test
void testStackRandomOrder() {
stack = new Stack();
stack.push(3);
stack.push(2);
stack.push(1);
stack.push(5);
stack.push(1);
stack.push(1);
stack.push(12);
stack.push(0);
System.out.println("original stack");
printStack();
sortStack();
System.out.println("Sorted stack");
printStack();
}
public static void main(String[] args) {
Solution e = new Solution();
System.out.println("Test reverse sorted stack");
e.testStackIncreasingOrder();
System.out.println("Test empty stack");
e.testEmptyStack();
System.out.println("Test randomly ordered stack");
e.testStackRandomOrder();
}
public void sortStack() {
auxiliaryStack = new Stack();
if (stack.isEmpty()) {
return;
}
while (!stack.isEmpty()) {
Object topOfStack = stack.pop();
if (auxiliaryStack.top != null) {
Object topOfAuxiliary = auxiliaryStack.peek();
if ((Integer) topOfStack > (Integer) topOfAuxiliary) {
emptyAuxiliary();
}
}
auxiliaryStack.push(topOfStack);
}
// System.out.println("AuxiliaryStack");
// printAuxiliaryStack();
emptyAuxiliary();
}
public void emptyAuxiliary() {
// Put all the elements of the auxiliary stack back in
// the original one
while (!auxiliaryStack.isEmpty()) {
Object element = auxiliaryStack.pop();
stack.push(element);
}
}
public Stack getStack() {
return stack;
}
public void printStack() {
Node current = stack.top;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
public void printAuxiliaryStack() {
Node current = auxiliaryStack.top;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
}
class Stack {
Node top;
Object pop() {
if (top != null) {
Object item = top.data;
top = top.next;
return item;
}
return null;
}
void push(Object item) {
Node t = new Node(item);
t.next = top;
top = t;
}
Object peek() {
return top.data;
}
boolean isEmpty() {
if (top == null) {
return true;
}
return false;
}
}
class Node {
Object data;
Node next;
public Node(Object item) {
data = item;
}
public Node(Object item, Node n) {
data = item;
next = n;
}
}
1 Answer 1
Generics
Generics... you want them. In your solution, they would be relatively easy to apply too. Consider your Node class:
class Node { Object data; Node next; public Node(Object item) { data = item; } public Node(Object item, Node n) { data = item; next = n; } }
Now, that Node only works on Object values, but you want it to be an Integer. Using generics, this is a treat (while we are at it, we will make data and next private and final, and add getters for them...):
class Node<T> {
private final T data;
private final Node<T> next;
public Node(T item) {
data = item;
}
public Node(T item, Node<T> n) {
data = item;
next = n;
}
public T getData() {
return data;
}
public Node<T> getNext() {
return next;
}
}
There, now Node is self contained, immutable, and generic. It can contain any object type, just specify the type you want when you construct it, for example:
Node<Integer> node = new Node<>(10);
Applying the same logic to your Stack class, we get:
class Stack<T> {
Node<T> top;
T pop() {
if (top != null) {
T item = top.getData();
top = top.getNext();
return item;
}
return null;
}
void push(T item) {
Node t = new Node(item, top);
// commented out, make Node immutable, pass in as constructor
// t.next = top;
top = t;
}
T peek() {
return top.getData();
}
boolean isEmpty() {
if (top == null) {
return true;
}
return false;
}
}
Right, that makes it generic, there are still a bunch of problems... but, it can be easy to use with:
Stack<Integer> stack = new Stack<>();
With the above stack, you should not need any casts from Object to Integer
Simplifications
Now, looking at some other parts of your code, let's simplify...
Chained constructors: whenever possible, have just one constructor that "does stuff" for your class, and have your other constructors call the main one. Your constructors look like:
public Node(Object item) { data = item; } public Node(Object item, Node n) { data = item; next = n; }
Note that they both access the data = item item directly. It would be better to change your first constructor to be:
public Node(T item) {
this(item, null);
}
The above constructor calls the second one with a null value.
Boolean expressions are boolean. If statements test a boolean condition. Why do both?
boolean isEmpty() { if (top == null) { return true; } return false; }
This is a good one, it can be simply:
boolean isEmpty() {
return top == null;
}
The push can be simplified too:
void push(T item) { Node t = new Node(item, top); // commented out, make Node immutable, pass in as constructor // t.next = top; top = t; }
That can be simply:
void push(T item) {
top = new Node(item, top);
}
Note that there is no need for the one-argument constructor now in the Node class.
Code duplication is always a red flag. Consider the following methods:
public void printStack() { Node current = stack.top; while (current != null) { System.out.println(current.data); current = current.next; } } public void printAuxiliaryStack() { Node current = auxiliaryStack.top; while (current != null) { System.out.println(current.data); current = current.next; } }
Why have the method twice, when instead you can have just:
public void printStack(Node<T> current) {
while (current != null) {
System.out.println(current.getData());
current = current.getNext();
}
}
Now, you can call that method with either the stack or the auxilliaryStack top nodes... but, that method really belongs on the stack itself, not outside the stack. Move it to the stack, and it becomes:
public void printStack() {
Node<T> current = top;
while (current != null) {
System.out.println(current.getData());
current = current.getNext();
}
}
Now you can simply do:
stack.printStack();
auxilliaryStack.printStack();
Bugs
The following is a bug:
Object peek() { return top.data; }
What if the stack is empty? You will get a NullPointerException!
Instead, do:
T peek() {
return top == null ? null : top.getData();
}
Sorting
Your algorithm looks sane, but the interface is ... cumbersome. You have a stack, and auxilliaryStack declared as members of the Solution class. Now, the rules of object orientation indicate that the data should be encapsulated. There are two logical ways to implement the sort that I can see. The one is to have a static method that takes a Stack as input, and sorts it in place (creating a temporary, and method-private auxStack to sort with). The other solution adds the sort method to the Stack class itself (and also has an internal auxStack). The second route is the better one.
public void sort() {
if (isEmpty()) {
return;
}
Stack<T> auxStack = new Stack<>();
.....
}
I recommend you make the changes and see how it works out for you. You will find that the logic and flow of the structure is neater, and more manageable.