《数据结构》第三章 栈和队列

存储结构:

#define MaxSize 50
//栈的顺序存储
typedef struct{
	ElemType data[MaxSize];
	int top;
}SqStack;
//栈的链式存储
typedef struct Linknode{
	ElemType data;
	struct Linknode *next;
}*LiStack;
//队列的顺序存储
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;
//队列的链式存储
typedef struct{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{
	LinkNode *front,*rear;
}LinkQueue;

3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答:
      (1) 如果进站的车厢序列为123,则可能得到的出站车厢序列是什么?
           123 231 321 213 132
      (2) 如果进站的车厢序列为123456,则能否得到435612和135426的出站序列,并请说明为什么不能得到或者如何得到(即写出以 ‘S’表示进栈和以 ‘X’表示出栈的栈操作序列)。
           可以得到135426的出站序列,但不能得到435612的出站序列。

3.2 简述栈和线性表的差别。

线性表是具有相同特性的数据元素的一个有限序列。栈是一种仅允许在表的一端进行插入和删除的受限的线性表。

3.3 写出下列程序段的输出结果(栈的元素类型SElemType为char)。

void main()
	{
		Stack S;
		char x,y;
		InitStack(S);
		x= ‘c’; y= ‘k’;
		Push(S,x);	Push(S, ‘a’);	Push(S,y);
		Pop(S,x);	Push(S, ‘t’);	Push(S,x);
		Pop(S,x);	Push(S, ‘s’);
		while(!StackEmpty(S)) { Pop(S,y); printf(y); }
		printf(x);
	}

stack

3.4 简述以下算法的功能(栈的元素类型SElemType为int)。

(1) status algo1(Stack S)
 {
        int i,n,A[255];
	n=0;
	while(!StackEmpty(S)) { n++; Pop(S,A[n]); }
	for(i=1;i<=n;i++) Push(S,A[i]);
}

栈中数据元素逆置

(2) status algo2(Stack S,int e)
		{
			Stack T; int d;
			InitStack(T);
			while(!StackEmpty(S)){
				Pop(S,d);
				if(d!=e) Push(T,d);
			}
			while(!StackEmpty(T)){
				Pop(T,d);
				Push(S,d);
			}
		}

如果栈中存在数据元素e,则删除

3.5 假设以S和X分别表示入栈和出栈的操作,则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列(例如,SXSX为合法序列,SXXS为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则,并证明:两个不同的合法(栈操作)序列(对同一输入序列)不可能得到相同的输出元素(注意:在此指的是元素实体,而不是值)序列。

3.6  试证明:若借助栈由输入序列12…n得到的输出序列为p_{1},p_{2}...p_{n}(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i<j<k,使p_{j}<p_{k}<p_{i}

3.7 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,并仿照教科书3.2节例3-2的格式,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程:
            A-B×C/D+E↑F

3.8 试推导求解n阶梵塔问题至少要执行的move操作的次数。

2^{n}-1

3.9 试将下列递推过程改写为递归过程。

void ditui(int n)
	{
		int i;
		i = n;
		while(i>1)
			cout<<i--;
	}

递归:

void ditui(int j)
{
	if(j>1){
		cout<<j;
		ditui(j-1);
	}
	return;
}

3.10 试将下列递归过程改写为非递归过程。

void test(int &sum)
	{
		int x;
		cin>>x;
		if(x==0) sum=0;
		else
		{
			test(sum);
			sum+=x;
		}
		cout<<sum;
	}

非递归:

void test(int &sum)
{
	Stack s;
	InitStack(s);
	int x;
	do{
		cin>>x;
		Push(s,x);
	}while(x>0);
	while(!StackEmpty(s)){
		Pop(s,x);
		sum+=x;
		cout<<sum<<endl;
	}
	DestoryStack(s);
}

3.11 简述队列和堆栈这两种数据类型的相同点和差异处。

栈和队列均是受限的线性表,栈允许在表的一端进行插入和删除,队列允许在表的一段进行插入,在表的另一端进行删除。

3.12 写出以下程序段的输出结果(队列中的元素类型QElemType为char)。

void main()
	{
		Queue Q;
		InitQueue(Q);
		char x= ‘e’, y= ‘c’;
		EnQueue(Q, ‘h’);
		EnQueue(Q, ‘r’);
		EnQueue(Q, y);
		DeQueue(Q, x);
		EnQueue(Q, x);
		DeQueue(Q, x);
		EnQueue(Q, ‘a’);
		While(!QueueEmpty(Q))
		{
			DeQueue(Q,y);
			cout<<y;
		}
		cout<<x;
	}

hrceeeae

3.13 简述以下算法的功能(栈和队列的元素类型均为int)。

void algo3(Queue &Q)
	{
		Stack S;
		int d;
		InitStack(S);
		while(!QueueEmpty(Q))
		{
			DeQueue(Q, d);
			Push(S, d);
		}
		while(!StackEmpty(S))
		{
			Pop(S, d);
			EnQueue(Q, d);
		}
	}

队列逆置

3.14 若以1234作为双端队列的输入序列,试分别求出满足以下条件的输出序列:
    (1) 能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列。
    (2) 能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列。
    (3) 既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列。

3.15 假设以顺序存储结构实现一个双向栈,即在一维数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作:初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法,其中i为0或1,用以分别指示设在数组两端的两个栈,并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。

typedef struct{
	ElemType *base[2];
	ElemType *top[2];
}BDStacktype; //双向栈类型
int Init_Stack(BDStacktype &tws,int m){
	//初始化一个大小为m 的双向栈tws
	tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype));
	tws.base[1]=tws.base[0]+m;
	tws.top[0]=tws.base[0];
	tws.top[1]=tws.base[1];
	return 1;
}
int push(BDStacktype &tws,int i,Elemtype x){
	//x 入栈,i=0 表示低端栈,i=1 表示高端栈
	if(tws.top[0]>tws.top[1]) 
		return 0; 
	if(i==0) 
		*tws.top[0]++=x;
	else if(i==1) 
		*tws.top[1]--=x;
	else 
		return 0;
	return 1;
}
int pop(BDStacktype &tws,int i,Elemtype &x){
	//x 出栈,i=0 表示低端栈,i=1 表示高端栈
	if(i==0){
	if(tws.top[0]==tws.base[0]) 
		return 0;
		x=*--tws.top[0];
	}
	else if(i==1){
		if(tws.top[1]==tws.base[1]) 
			return 0;
		x=*++tws.top[1];
	}
	else 
		return 0;
	return 1;
}

3.16 假设如题3.1所属火车调度站的入口处有n节硬席或软席车厢(分别以H和S表示)等待调度,试编写算法,输出对这n节车厢进行调度的操作(即入栈或出栈操作)序列,以使所有的软席车厢都被调整到硬席车厢之前。

void trainArrange(char *train){
	//train表示列车
	p=train;
	q=train;
	InitStack(s);
	while(*p){
		if(*p=='H')
			push(s,*p);
		else 
			*(q++)=*p;
		p++;
	}
	while(!StackEmpty(s)){
		pop(s,c);
		*(q++)=c;
	}
}

3.17 试写一个算法,识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’,且序列2是序列1的逆序列。例如,‘a+b&b+a’是属该模式的字符序列,而‘1+3&3-1’则不是。

int isReverse(){
	//判断输入的字符串中'&'前和'&'后部分的字符串是否互逆。
	InitStack(s);
	while((e=getchar())!='&'){
		if(e=='@')
			return 0;
		push(s,e);
	}
	while((e=getchar())1='@'){
		if(StackEmpty(s))
			return 0;
		pop(s,c);
		if(e!=c)
			return 0
	}
	if(!StackEmpty(s))
		return 0;
	return 1;
}

3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。

int bracketTest(char *str){
	//判断表达式中的小括号是否匹配
	count=0;
	for(p=str;*p;p++){
		if(*p=='(')
			count++;
		else if(*p==')')
			count--;
		if(count<0)
			return 0;
	}
	if(count)
		return 0;
	return 1;
}

3.19 假设一个算术表达式中可以包含三种括号:圆括号'('和')'、方括号'[‘和’]'、花括号'{'和'}',且这三种括号可按任意的次序嵌套使用。编写判别给定的表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)。

int allBracketsTest(char *str){
	//判别表达式中三种括号是否匹配
	InitStack(s);
	for(p=str;*p;p++){
		if(*p=='(' || *p=='[' || *p=='{')
			push(s,*p);
		else if(*p==')' || *p==']' || *p=='}'){
			if(StackEmpty(s))
				return 0;
			pop(s,c);
			if(*p==')' && c!='(')
				return 0;
			if(*p==']' && c!= '[')
				return 0;
			if(*p=='}' && c!='{')
				return 0;
		}
	}
	if(!StackEmpty(s))
		return 0;
	return 0;
}

3.20 假设以二维数组g(1…m, 1…n)表示一个图像区域,g[i,j]表示该区域中点(i,j)所具颜色,其值为从0到k的整数。编写算法置换点\left ( i_{0},j_{0} \right )所在区域的颜色,约定和\left ( i_{0},j_{0} \right )同色的上、下、左、右的邻接点为同色区域的点。

typedef struct{
	int x;
	int y;
}coordinate;
int replaceColor(int g[m][n],int i,int j,int color){
	//把点(i,j)相邻区域的点置换为color
	coordinate a;
	old=g[i][j];
	a.x=i;a.y=j;
	InitiQueue(Q);
	EnQueue(Q,a);
	while(!QueueEmpty(Q)){
		DeQueue(Q,a);
		x=a.x;
		y=a.y;
		if(x>1)
			if(g[x-1][y]==old){//修改左邻点的颜色
				g[x-1][y]=color;
				a.x=x-1;a.y=y;
				EnQueue(Q,a);
			}
		if(y>1)
			if(g[x][y-1]==old){//修改上邻点的颜色
				g[x][y-1]=color;
				a.x=x;a.y=y-1;
				EnQueue(Q,a);
			}
		if(x<m)
			if(g[x+1][y]==old){//修改右邻点的颜色
				g[x+1][y]=color;
				a.x=x+1;a.y=y;
				EnQueue(Q,a);
			}
		if(y<n)
			if(g[x][y+1]==old){//修改下邻点的颜色
				g[x][y+1]=color;
				a.x=x;a.y=y+1;
				EnQueue(Q,a);
			}
	}
	return 1;
}

3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算法,将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。

char *RPExpression(char *e){
	//将中缀表达式转化为后缀表达式
	//参数为传入的中缀表达式,设置两个栈,分别存放操作符和逆波兰式
	Stack s1,s2;
	InitStack(s1);//存放操作符
	InitStack(s2);//存放逆波兰式
	Push(s1,'#');
	
	char *p=e,ch;
	int length=0;//表达式长度
	for(*p!='\0';p++){
		switch(*p){
		//遇"("则直接入栈
		case '(':
			push(s1,*p);
			break;
		//遇")"则将距离s1栈顶的最近的"("之间的运算符,逐个出栈,依次送入栈s2,并放弃"("
		case ')':
			while(GetTop(s1)!='('){
				pop(s1,ch);
				push(s2,ch);
			}
			pop(s1,ch);
			break;
		//若当前栈s1的栈顶元素是'(',则当前运算符直接压入栈s1
		//否则,将当前运算符与栈s1的栈顶元素比较,若优先级较栈顶元素大,则直接压入栈s1中
		//  否则将s1栈顶元素弹出,并压入栈s2中,直到栈顶运算符的优先级别低于当前运算符,然后再将当前运算符压入栈s1中
		case '+':
		case '-':
			for(ch=GetTop(s1);ch!='#';ch=GetTop(s1)){
				if(ch=='('){
					break;
				}else{
					pop(s1,ch);
					push(s2,ch);
				}
			}
			push(s1,*p);
			length++;
			break;
		case '*':
		case '/':
			for(ch=GetTop(s1);ch!='#'&&ch!='+'&&ch!='-';ch=GetTop(s1)){
				if(ch=='('){
					break;
				}else{
					pop(s1,ch);
					push(s2,ch);
				}
			}
			push(s1,*p);
			length++;
			break;
		//遇操作数则直接压入栈s2中
		default:
			push(s2,*p);
			length++;
		}
	}
	//若栈s1非空,则将栈中元素依次弹出并压入栈s2中
	while(!StackEmpty(s1)&&GetTop(s1)!='#'){
		pop(s1,ch);
		push(s2,ch);
	}
	//最后将栈s2输出,逆序排列成字符串;
	char *result;
	result=(char *) malloc(sizeof(char)*(length+1));
	result+=length;
	*result='\0';
	result--;
	for(;!StackEmpty(s2);result--){
		pop(s2,ch);
		*result=ch;
	}
	++result;
	return result;
}

3.22 如题3.21的假设条件,试写一个算法,对以逆波兰式表示的表达式求值。

int getValueNiBoLan(char *str){
	//对逆波兰表达式*str求值
	p=str;
	InitStack(s);//s为操作数栈
	while(*p){
		if(*p>=48 &&*p<=57)
			push(s,*p);
		else{
			pop(s,a);
			pop(s,b);
			r=compute(a,b,*p);//计算
			push(s,r);
		}
		p++;
	}
	pop(s,r);
	return r;
}

3.23 如题3.21的假设条件,试写一个算法,判断给定的非空后缀表达式是否为正确的逆波兰表达式(后缀表达式),如果是,则将它转化为波兰式(前缀表达式)。

int NiBoLanToBoLan(char *str,char *new){
	//将逆波兰表达式str转化为波兰表达式new
	p=str;
	InitStack(s);
	while(*p){
		if(*p>=97 && *p<=122)//是字母
			push(s,*p);
		else{
			if(StackEmpty(s))
				return 0;
			pop(s,a);
			if(StackEmpty(s))
				return 0;
			pop(s,b);
			c=link(link(*p,b),a);//字母连接
			push(s,c);
		}
		p++;
	}
	pop(s,*new);
	new++;
	if(!StackEmpty(s))
		return 0;
}

3.24 试编写如下定义的递归函数的递归算法,并根据算法画出求g(5,2)时栈的变化过程。
g(m,n)=\left\{\begin{matrix} 0 & m=0,n\geq 0 \\g(m-1,2n)+n & m>0,n\geq 0 \end{matrix}\right.

int g(int m,int n){
	if(m==0&&n>=0)
		s=0;
	else if(m>0&&n>=0)
		s=n+g(m-1,2*n);
	else 
		return;
	return s;
}

3.25 试写出求递归函数F(n)的递归算法,并消除递归:
F(n)=\left\{\begin{matrix} n+1 & n=0 \\n\cdot F(\frac{n}{2}) & n>0 \end{matrix}\right.

int FRecursive(int n,int &s){
	//递归算法
	if(n<0)
		return 0;
	if(n==0)
		s=n+1;
	else{
		FRecusive(n/2,r);
		s=n*r;
	}
	return s;
}
int FNonrecursive(int n,int s){
	//非递归算法
	if(n<0)
		return 0;
	if(n==0)
		s=n+1;
	else{
		InitStack(s);
		while(n!=0){
			a=n;
			b=n/2;
			push(s,{a,b});
			n=b;
		}
		s=1;
		while(!StackEmpty(s)){
			pop(s,t);
			s*=t.a;
		}
		return 1;
	}
}

3.26 求解平方根\sqrt{A}的迭代函数如下:
sqrt\left ( A,p,e \right )=\left\{\begin{matrix} p & \left | p^{2}-A\right |< e \\sqrt\left ( A,\frac{1}{2}\left ( p+\frac{A}{p} \right ),e \right ) & \left | p^{2} -A\right |\geq e \end{matrix}\right.
其中,p是A的近似平方根,e是结果允许误差。试写出相应的递归算法,并消除递归。

float sqrtRecursive(float A,float p,float e){
	//递归方法求平方根
	if(abs(p*p-A)<=e)
		return p;
	else
		return sqrtRecursive(A,(p+A/p),e);
}
float sqrtNonRecursive(float A,float p,float e){
	//非递归方法求平方根
	while(abs(p*p-A)>=e)
		p=(p+A/p)/2;
	return p;
}

3.27 已知Ackerman函数的定义如下:
akm\left ( m,n \right )=\left\{\begin{matrix} n+1 & m=0 \\ akm(m-1,1) & m\neq 0,n=0 \\ akm(m-1,akm(m,n-1)) & m\neq 0,n\neq 0 \end{matrix}\right.

 (1) 写出递归算法;
 (2) 写出非递归算法;
 (3) 根据非递归算法,画出求akm(2,1)时栈的变化过程。

//递归算法
int akm(int m,int n){
	if(m==0)
		akm=n+1;
	else if(n==0)
		akm=akm(m-1,1);
	else{
		g=akm(m,n-1);
		akm=akm(m-1,g);
	}
	return akm;
}
//非递归算法
int akm(int m,int n){
	//利用栈实现递归算法
	top=0;
	s[top].mval=m;
	s[top].nval=n;
	do{
		while(s[top].mval){
			while(s[top].nval){
				top++;
				s[top].mval=s[top-1].mval;
				s[top].nval=s[top-1].nval-1;
			}
			s[top].mval--;
			s[top].nval=1;
		}
		if(top>0){
			top--;
			s[top].mval--;
			s[top].nval=s[top+1].nval+1;
		}
	}while(top!=0||s[top].mval1=0);
	akm=s[top].nval+1;
	top--;
	return akm;
}

3.28 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出处队列的算法。

typedef struct{
	ElemType data;
	LinkNode *next;
}LinkNode,*LinkQueue;
void InitQueue(LinkQueue &q){//初始化队列 
	Q=(LinkNode *) malloc(sizeof(LinkNode));
	Q->next=Q;
}
void enQueue(LinkQueue &q,int x){
	//入队列
	//q指向循环队列队尾元素结点
	p=(LinkNode *) malloc(sizeof(LinkNode));
	p->data=x;
	p-next=q->next;
	q->next=p;
	q=p;
}
int deQueue(LinkQueue &q,int &x){
	//出队列
	//q指向循环队列队尾元素结点
	//如果队列中只有一个元素,则另作特殊处理。
	LinkQueue p;
	if(q=q->next){//队空
		return 0;
	}
	if(q=q->next->next){//只有一个元素
		x=q->data;
		q=q->next;
	}
	p=q->next->next;
	x=p->data;
	q->next->next=p->next;
	free(p);
	return 1;
}

3.29 如果希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0和1来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法,并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围(如当循环队列容量较小而队列中每个元素占的空间较多时,哪一种方法较好)。

typedef struct{
	ElemType base[MaxSize];
	int front;
	int rear;
	int tag;
}DQueue;
//当入队时,如果front=rear,则置tag=1 队满
//当出队时,如果front=rear,则置tag=0 队空
int enDQueue(DQueue &q,int x){
	//带tag的循环队列入队
	if(q.front==q.rear && q.tag==1)//队满
		return 0;
	q.rear=(q.rear+1)%MaxSize;
	q.base[q.rear]=x;
	if(q.front==q.rear)
		q.tag=1;
	return 1;
}
int deDQueue(DQueue &q,int &x){
	if(q.front==q.rear && q.tag==0)//队空
		return 0;
	x=q.base[q.front];
	q.front=(q.front+1)%MaxSize;
	if(q.front==q.rear)
		q.tag=0;
	return 1;
}

3.30 假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件,并写出相应的入队列和出队列的算法(在出队列的算法中要返回队头元素)。

typedef struct{
	ElemType base[MaxSize];
	int rear;
	int length;
}Queue;//将长度的循环队列
//队满条件:length=MaxSize
int enQueue(Queue &Q,int x){
	//循环队列入队
	if(Q.length==MazSize)//队满
		return 0;
	Q.rear=(Q.rear+1)%MaxSize;
	Q.base[Q.rear]=x;
	Q.length++;
	return 1;
}
int deQueue(Queue &Q,int &x){
	//循环队列出队
	if(Q.length==0)
		return 0;
	head=((Q.rear+MaxSize)-Q.length+1)%MaxSize;//算头结点的位置
	x=Q.base[head];
	Q.length--;
}

3.31 假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

int isPalindrome(){
	//判断输入的字符串是否是回文
	//分别将字符串存入栈和队列,然后依次出栈和队列,判断两元素是否相等
	InitStack(S);
	InitQueue(Q);
	char a,b,c;
	while((c.getchar())!='@'){
		push(S,c);
		enQueue(Q,c);
	}
	while(!StackEmpty(S)){
		pop(S,a);
		deQueue(Q,b);
		if(a!=b)
			return 0;
	}
	return 1;
}

3.32 试利用循环队列编写求k阶菲波那契序列中前n+1项的算法,要求满足:f_{n}\leq maxf_{n+1} > max,其中max为某个约定的常数。(注意:本题所用循环队列的容量仅为k,则在算法执行结束时,留在循环队列中的元素应是所求k阶菲波那契序列中的最后k项f_{n-k-1},...f_{n})。

void getFibQueue(int k,int n){
	//求以循环队列存储的菲波那契数列的前n+1项
	InitDQueue(Q);//MAXSIZE=k
	for(i=0;i<k-1;i++){
		Q.base[i]=0;
	}
	for(i=k;i<=n;i++){
		m=j%k;
		sum=0;
		for(j=0;j<k;j++)
			sum+=Q.base[(m+j)%k];
		Q.base[m]=sum;
	}
}

3.33 在顺序存储结构上实现输出受限的双端循环队列的入列和出列(只允许队头出列)算法。设每个元素表示一个待处理的作业,元素值表示作业的预计时间。入队列采取简化的短作业优先原则,若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间,则插入在队头,否则插入在队尾。

int enDQueue(DQueue &Q,int x){
	//输出受限的双端队列的插入
	if((Q.rear+1)%MAXSIZE==Q.front)
		return 0;//队列满
	aver=(Q.base[Q.rear+1]+Q.base[Q.front])/2;
	if(x>=aver){//插入队尾
		Q.base[Q.rear]=x;
		Q.rear=(Q.rear+1)%MAXSIZE;
	}else{//插入队首
		Q.front=(Q.front-1)%MAXSIZE;
		Q.base[Q.front]=x;
	}
	return 1;
}

3.34 假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入端有n节车厢:硬座、硬卧和软卧(分别以P,H和S表示)等待调度,要求这三种车厢在输出端铁道上的排列次序为:硬座在前,软卧在中,硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度,编写算法输出调度的操作序列:分别以字符‘E’和‘D’表示对双端队列的头端进行入队列和出队列的操作;以字符A表示对双端队列的尾端进行入队列的操作。

void trainRearrange(char *train){
	//扫描队列,把S从头端出入队列,把H从尾端插入队列,然后从头端输出队列,则总的顺序为PSH
	t=train;
	InitDQueue(Q);
	while(*r){
		if(*r=='P'){
			printf('E');
			printf('D');
			printf(*r);//直接输出P
		}else if(*r=='S'){
			printf('E');
			EnDQueue(Q,*r,0);//从队首插入S
		}else{
			printf('A');
			EnDQueue(Q,*r,1);//从队尾插入H
		}
		r=r+1;
	}
	while(!DQueueEmpty(Q)){//从队首依次输出元素
		printf("D");
		DeDQeue("Q");
	}
}