We will consider the stack ADT and implement sorting using only stack operations:
push, pop, peek and isEmpty.
Today's example
package lab03;
import java.util.*;
public class LabExample {
public static void main( String [] args )
{
// Create three Integer stacks
Stack<Integer> stackA = new Stack<Integer>();
Stack<Integer> stackB = new Stack<Integer>();
Stack<Integer> stackC = new Stack<Integer>();
Random rand = new Random();
// Push random integers on stackA
for( int i = 0 ; i < 20; i++ )
stackA.push(new Integer(rand.nextInt(1000)));
// Example: to "transfer" element from stackA to stackB
stackB.push( stackA.pop() );
// Example: to "compare" element at top of stackA to top of stackB
if( stackA.peek() < stackB.peek() ) { }
// Example: to check if stackA is empty
if( stackA.isEmpty() ) { }
/* ************** Task for today's lab ****************
Transfer numbers from stackA to stackC such that the numbers in
stackC are in ascending order.
You are only allowed the following stack operations:
push(), pop(), peek() and isEmpty()
*/ // Loop until all numbers have been transferred out of stackA
while( !stackA.isEmpty() )
{
//Step 1: Transfer a number (call it N) from stackA to stackB //Step 2: Transfer numbers on stackC smaller than N to stackA //Step 3: Transfer number N from stackB to stackC//Step 4: Transfer back as many numbers as possible// from stackA to stackC ensuring sorted order on stackC
}
//Print numbers in stackC
while( !stackC.isEmpty() )
System.out.println(stackC.pop());
}
}