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;
Java中基于栈和队列的排序算法(2)
时间:2011-04-13
2.3 打印数据,依据[3.6]从为值为1的那个栈中开始取一个数据,再从另一个栈中取一个数 据,如此交替直到取完两个栈中所由数据;
2.4测试,执行程序输出:
Original:3 1 7 1
Result :1 1 3 7
Original:3 1 9
Result :1 3 9
public class StackSort {
private IntStack stackOne;
private IntStack stackTwo;
private int size = 0;
private static final int START_ONE = 1;
private static final int START_TWO = 2;
public StackSort(int[] ints) {
stackOne = new IntStack();
stackTwo = new IntStack();
init(ints, stackOne);
}
private void init(int[] ints, IntStack stack) {
System.out.print("Original:");
for (int i : ints) {
System.out.print(i + " ");
stack.push(i);
size++;
}
System.out.println();
}
public int sort() {
if (size == 0)
throw new UnsupportedOperationException("Stack empty");
int sizeOne = size;
int sizeTwo = 0;
while (sizeOne != 1 && sizeTwo != 1) {
int max = stackOne.pop();
sizeOne--;
while (sizeOne > 0) {
int value = stackOne.pop();
if (value > max) {
stackTwo.push(max);
max = value;
} else
stackTwo.push(value);
sizeOne--;
sizeTwo++;
}
stackOne.push(max);
if (sizeTwo == 1)
return
|
