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

题目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;