for data structure and algorithms

Question

Write an algorithm that reads numbers from the screen and sorts them at the same time by using two stacks.

Answer 1

The master list of sorted numbers must be a queue. If it is also a stack, then you only need one Stack to sort them, not two.

If the master list is a QUEUE, use the following algorithm:

(1st number in the list is the TOP of the stack or queue}

Given input value X;

Stack A and Stack B are initially empty;

Queue may contain sorted data or may be empty;

if queue is empty, puts input value in the queue...DONE

ELSE

step 1:

pops off all items that are LESS

than the input value X off of the

queue and pushed them onto stack A

step 2:

moves all items from stack A to stack B

step 3:

pops off all of the remaining number from the queue to stack A

step 4:

moves all items from stack B to queue

step 5:

adds the new input value to queue

step 6:

moves all items from stack A to stack B

step 7:

moves all items from stack B to queue

EX.

input value 5;

queue { 1,2,3,4,6,8,10,12,13,15,16,18,20}

THe queue is clearly not empty.

step 1:

queue {6,8,10,12,13,15,16,18,20}

stack A {4,3,2,1}

stack B is empty

step 2:

queue {6,8,10,12,13,15,16,18,20}

stack A is empty

stack B {1,2,3,4}

step 3:

queue is empty

stack A {20,18,16,15,13,12,10,8,6}

stack B {1,2,3,4}

step 4:

queue {1,2,3,4}

stack A {20,18,16,15,13,12,10,8,6}

stack B is empty

step 5:

queue {1,2,3,4,5}

stack A {20,18,16,15,13,12,10,8,6}

stack B is empty

step 6:

queue {1,2,3,4,5}

stack A is empty

stack B {6,8,10,12,13,15,16,18,20}

step 7: queue {1,2,3,4,5,6,8,10,12,13,15,16,18,20}

list sorted

--------------------------------------------------------------

-----------------------------------------------------------------

If the master list also a stack, then you only need ONE STACK...

Step 1:

step 1:

pops off all items that are LESS

than the input value X off of the

list and push them onto the stack

step 2:

pushes the input value onto the list

step 3:

moves all of the numbers from the stack to the list.

Ex.

List {1,2,3,4,6,8,10,12,13,15,16,18,20}

input x=5

step 1:

List {6,8,10,12,13,15,16,18,20}

stack {4,3,2,1}

step 2:

List {5,6,8,10,12,13,15,16,18,20}

step 3:

{1,2,3,4,5,6,8,10,12,13,15,16,18,20}

List sorted