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;

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 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<Integer> storage = new LinkedList<Integer> ();
　　 /** 將指定的元素插入隊尾 */
　　 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();
　　 }
}