返回首页

基于栈和队列的排序算法

时间:2009-01-08 19:19来源:51cto 作者:zhangjunhd 点击:
题目1:使用一个辅助栈和一些附加非数组变量将堆栈S中的元素按升序存储. 题目2:使用一个辅助队列和一些附加非数组变量将队列Q中的元素按升序存储. 1.用Java实现,首先使用链表LinkedList构造栈数据结构. import java.util.LinkedList; public class IntStack {  &nb
  题目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();
    }
}

本文出自 “子 孑” 博客,请务必保留此出处http://zhangjunhd.blog.51cto.com/113473/81750

顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 密码: 验证码:
发布者资料
小朱 查看详细资料 发送留言 加为好友 用户等级:超级会员 注册时间:2008-11-18 17:11 最后登录:2012-02-06 13:02
推荐内容
热点内容