Go语言视频零基础入门到精通

五菱

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

}

}