编辑代码

/*=============== 队列的应用 =========================
               利用队列实现一组整数排序
用队列排序的思想就是每取一个数据，就和队列A中的元素作比较，
将小的元素移到另外一个空队列B中，再将这个元素放到B的队尾，
将A中的其他元素逐次移到B中。如此循环，直到处理完所有元素。
======================================================*/

#include <stdlib.h>
#include <stdio.h>

#define datatype int

#define maxsize 10

/*===============顺序队列的结构类型定义（99页）=======
======================================================*/
typedef struct {
	datatype  data[maxsize];
	int front;
	int rear;
} SeQueue;

/*===============算法4.11（100页）=======
建立空循环队列
======================================================*/
void InitQueue(SeQueue *&sq) { //建立空循环队列sq
	sq = (SeQueue *)malloc(sizeof(SeQueue));
	sq->front = sq->rear = 0;
}

/*===============算法4.12（100页）=======
循环队列置空
======================================================*/
void SetNull (SeQueue *sq) { //置队列sq为空队
	sq->front = sq->rear = 0;
}

/*===============算法4.13（100页）=======
循环队列长度
======================================================*/
int Length (SeQueue *sq) {
	return (sq->rear - sq->front + maxsize) % maxsize;
}

/*===============算法4.14（100页）=======
循环队列入队
======================================================*/
int EnQueue(SeQueue *sq, datatype x)

// 将新元素x插入队列 *sq 的队尾，入队成功返回1，不成功返回0
{
	if (sq->front == (sq->rear + 1) % maxsize) {
		printf("队列上溢");
		return (0);
	} else {
		sq->rear = (sq->rear + 1) % maxsize;
		sq->data[sq->rear] = x;
		return (1);
	}
}


/*===============算法4.15（101页）=======
循环队列出队
======================================================*/
int DeQueue (SeQueue *sq, datatype &x)

// 通过参数x带回元素值，出队成功返回1，否则返回0
{
	if (sq->front == sq->rear) {
		printf("队列下溢");
		return (0);
	} else {
		sq->front = (sq->front + 1) % maxsize;
		x = sq->data[sq->front];
		return (1);
	}
}

/*===============算法4.16（101页）=======
取循环队列的队头元素
======================================================*/
int GetFront (SeQueue *sq, datatype &x)

// 通过参数x带回元素值，取对头元素成功返回1，否则返回0
{
	if (sq->front == sq->rear) {
		printf("队列下溢");
		return (0);
	} else {
		x = sq->data[(sq->front + 1) % maxsize];
		return (1);
	}
}


void RankSeQueue(datatype a[], int n) { //将a[]中元素从小到大输出
	SeQueue *Q[2]; // 队列数组，两个队列
	InitQueue(Q[0]);
	InitQueue(Q[1]);
	int k = 0, j;
	datatype t;
	EnQueue(Q[k], a[0]); //第一个元素入第一个队列
	int i;
	for (i = 1; i < n; i++) {      //对其他元素
		j = (k + 1) % 2; //j为当前的空队列号；k为有序元素的队列号
		GetFront(Q[k], t);
		while (Q[k]->front != Q[k]->rear && a[i] > t) { //移动前面小的元素
			DeQueue(Q[k], t);
			EnQueue(Q[j], t);
			if (Q[k]->front != Q[k]->rear)
				GetFront(Q[k], t);
		}
		EnQueue(Q[j], a[i]);         //放当前的元素
		while (Q[k]->front != Q[k]->rear) {
			DeQueue(Q[k], t);    //移到后面最大的元素
			EnQueue(Q[j], t);
		}
		k = j;
	}
	while ((Q[k]->front != Q[k]->rear)) { //输出
		DeQueue(Q[k], t);
		printf("%5d", t);
	}
	printf("\n");
}


int main() {

	// /*
	int k, n = maxsize - 1;
	datatype a[n];
	for (k = 0; k < n; k++) {
		a[k] = n - k;
	}
	// */

	/*
	int n = maxsize - 1;
	datatype a[n] = {4, 3, 2, 9, 6, 1, 7, 5, 8};
	*/

	printf("数组元素从小到大输出为：\n");
	RankSeQueue(a, n);

	return 0;
}