Java中基于栈和队列的排序算法

Java中基于栈和队列的排序算法2011-04-13题目1:使用一个辅助栈和一些附加非数组变量将堆栈S中的元素按升序存储.

题目2:使用一个辅助队列和一些附加非数组变量将队列Q中的元素按升序存储.

1.用Java实现,首先使用链表LinkedList构造栈数据结构.

import java.util.LinkedList;
public class IntStack {
   private LinkedList<Integer> storage = new LinkedList<Integer> （）;
   /** 入栈 */
   public void push（int v） {
     storage.addFirst（v）;
   }
   /** 出栈，但不删除 */
   public int peek（） {
     return storage.getFirst（）;
   }
   /** 出栈 */
   public int pop（） {
     return storage.removeFirst（）;
   }
   /** 栈是否为空 */
   public boolean empty（） {
     return storage.isEmpty（）;
   }
   /** 打印栈元素 */
   public String toString（） {
     return storage.toString（）;
   }
}

2.使用两个栈进行排序操作.

2.1方法init（int[] ints, IntStack stack）将数据存入栈1;

2.2方法sort（）进行排序,主要算法是:

[1]sizeOne和sizeTwo记录当前两个栈中待排序的数据数目;

[2]做循环,直到某个栈中待排序的数据数目为1,说明排序完成;

[3]排序的过程为,

[3.1]首先从栈1中依次取出所由未排序数据,找到最大者,存入max,而其余入栈2;

[3.2]此时已经找到数据的最大者;

[3.3]再次,从栈2中依次取出所由未排序数据,找到最大者,存入max,而其余入栈1;

[3.4]此时已经找到数据的次大者;

[3.5]依次交替往复,直到满足中止条件[2];

[3.6]此时sizeOne和sizeTow中必然一个为0,一个为1;