题目1:使用一个辅助栈和一些附加非数组变量将堆栈S中的元素按升序存储.
题目2:使用一个辅助队列和一些附加非数组变量将队列Q中的元素按升序存储.
1.用Java实现,首先使用链表LinkedList构造栈数据结构.
import java.util.LinkedList;public class IntStack { private LinkedList sTorage = new LinkedList (); /** 入栈 */ 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;
2.3 打印数据,依据[3.6]从为值为1的那个栈中开始取一个数据,再从另一个栈中取一个数 据,如此交替直到取完两个栈中所由数据;
2.4测试,执行程序输出:
Original:3 1 7 1Result :1 1 3 7Original:3 1 9Result :1 3 9public 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 START_TWO; max = stackTwo.pop(); sizeTwo--; while (sizeTwo > 0) { int value = stackTwo.pop(); if (value > max) { stackOne.push(max); max = value; } else stackOne.push(value); sizeTwo--; sizeOne++; } stackTwo.push(max); } // sizeOne和sizeTow中必然一个为0,一个为1 return (sizeOne > sizeTwo ? START_ONE : START_TWO); } public void printResult(int start) { System.out.print("Result :"); if (start == START_ONE) printStack(stackOne, stackTwo); else printStack(stackTwo, stackOne); System.out.println(); } private void printStack(IntStack one, IntStack two) { while (one.empty() == false && two.empty() == false) { System.out.print(one.pop() + " "); System.out.print(two.pop() + " "); } if (one.empty() == false) System.out.print(one.pop() + " "); } public static void main(String[] args) { StackSort ssort = new StackSort(new int[] { 3, 1, 7, 1 }); ssort.printResult(ssort.sort()); ssort = new StackSort(new int[] { 3, 1, 9 }); ssort.printResult(ssort.sort()); }}
3.队列的排序算法
每次循环取源队列数据,找出最大者加入目标队列,其余放回源队列,直到源队列空,排序完 成(这种算法适合于实现约瑟夫环).如果每次取出的最大值直接打印,则不需要额外辅助队 列.
3.1所使用的队列数据结构
import java.util.LinkedList;import java.util.Queue;public class IntQueue { private Queue sTorage = new LinkedList (); /** 将指定的元素插入队尾 */ public void offer(int v) { sTorage.offer(v); } /** 检索，但是不移除队列的头，如果此队列为空，则返回 null */ public int peek() { return sTorage.peek(); } /** 检索并移除此队列的头，如果队列为空，则返回 null */ public int poll() { return sTorage.poll(); } /** 队列是否为空 */ public boolean empty() { return sTorage.isEmpty(); } /** 打印队列元素 */ public String toString() { return sTorage.toString(); }}
3.2队列排序
public class QueueSort { private IntQueue queueOne; private IntQueue queueTwo; private int size = 0; public QueueSort(int[] ints) { queueOne = new IntQueue(); queueTwo = new IntQueue(); init(ints, queueOne); } private void init(int[] ints, IntQueue queue) { System.out.print("Original:"); for (int i : ints) { System.out.print(i + " "); queue.offer(i); size++; } System.out.println(); } public void sort() { if (size == 0) throw new UnsupportedOperationException("Stack empty"); int sizeOne = size; while (sizeOne > 0) { int max = queueOne.poll(); int turn = sizeOne - 1;//当前轮次的待比较元素数 while (turn > 0) { int value = queueOne.poll(); if (value > max) { queueOne.offer(max); max = value; } else queueOne.offer(value); turn--; } queueTwo.offer(max); sizeOne--; } } public void printResult() { System.out.print("Result :"); while (queueTwo.empty() == false) System.out.print(queueTwo.poll() + " "); System.out.println(); } public static void main(String[] args) { QueueSort qsort = new QueueSort(new int[] { 3, 1, 7, 1 }); qsort.sort(); qsort.printResult(); qsort = new QueueSort(new int[] { 3, 1, 9 }); qsort.sort(); qsort.printResult(); }}
人生就像一杯没有加糖的咖啡，喝起来是苦涩的，
