3.3栈和队列的应用

1、栈在括号匹配中的应用

1、假设一个算术表达式中包含圆括号、方括号、花括号3种类型的括号，编写一个算法来判断表达式中的括号是否匹配，以字符‘\0’作为算术表达式的结束符

bool BracketCheck(char *str)
{
	int i=0;
	while(str[i]!='\0'){
		switch(str[i]){
			//左括号入栈
			case '(':Push(S,'(');break;
			case '[':Push(S,'[');break;
			case '{':Push(S,'{');break;
			//遇到右括号，检测栈顶
			case ')':Pop(S,e);
				if(e!='(') return false;
			break;
			case ']':Pop(S,e);
				if(e!='[') return false;
			case '}':Pop(S,e);
				if(e!='(') return false;
			break;
			default:
			break; 
			}
			i++; 
		}
		if(!IsEmpty(S)){
			printf("括号不匹配\n");
			return false;
		}
		else{
			printf("括号匹配\n");
			return true;
		}
	}
}
 

2、栈在表达式求值中的应用

3、栈在递归中的应用

算法思想：设置一个栈用于保存n和对应的P（x）值，栈中相邻元素p（x)有题中关系。然后边出栈边计算P（x），栈空后该值就计算出来了

double p(int n,double x)
{
	struct stack{
		int no;//保存n 
		double val;//保存p（x）值 
	}st[MaxSize];
	int top=-1,i;//top为栈st的下标值变量 
	double fv1=1,fv2=2*x;//n=0，n=1时的初值 
	for(i=n;i>=2;i--){
		top++;
		st[top].no=i;
	}					//入栈 
	while(top>=0){
		st[top].val=2*x*fv2-2*[st[top].no-1]*fv1;
		fv1=fv2;
		fv2=st[top].val;
		top--;			//出栈 
	}
	if(n==0){
		return fv1;
	}
	return fv2;
}

4、队列在层次遍历中的应用

5、队列在计算机系统中的应用

两侧的铁道均为单向行使道，且两侧不相通。所有车辆都必须通过‘栈道’进行调度。算法的基本思想：所有车厢依次前进并逐一检查，若为硬座车厢则入栈，等待最后调度。检查完后，所有的硬座车厢已全部入栈道，车道中的车厢均为软座车厢，此时将栈道的车厢调度出来，调整到软座车厢之后。

void Train_Arrange(char *train)
{//用字符串train表示火车，H表示硬座，S表示软座 
	char *p=train,*q=train,c;
	stack s;
	InitStack(s);//初始化栈结构 
	 while(*p){
	 	if(*p=='H')
	 		Push(s,*p);
	 	else
	 	 	*(q++)=*p;//把S调到前部 
		p++; 
	 }
	 while(!StackEmpty(s)){
	 	Pop(s,c);
	 	*(q++)=c;//把H接在后部 
	 } 
}

算法思想：假设数组q的最大下标为10，恰好是每次载度的最大量。假设客车的队列为q1，火车的队列为q2.若q1充足，则取4个q1元素后再去一个q2元素，直到q的长度为10.若q1不充足，则直接用q2补齐

Queue q;//过江渡船载度队列 
Queue q1;//客车队列 
Queue q2;//货车队列 
void manager()
{
	int i=0,j=0;//j表示渡船上的总车辆数 
	while(j<10){//不足10辆时 
		if(!QueueEmpty(q1)&&i<4){//客车队列不空，则未上足4辆 
			DeQueue(q1,x);//从客车队列出队 
			EnQueue(q,x);//客车上渡船 
			i++;//客车数加1 
			j++; //渡船上的总车辆数加1 
		}
		else if(i==4&&!QueueEmpty(q2)){//客车已上足4两 
			DeQueue(q2,x);//从货车队列出队 
			EnQueue(q,x);//货车上渡船 
			j++;//渡船上的总车辆数加1 
			i=0;//每上一辆货车，i重新计数 
		}
		else{//其他情况 （客车队列空或货车队列空） 
			while(j<10&&i<4&&!QueueEmpty(q2)){//客车队列空 
				DeQueue9(q2,x);//从货车队列出队 
				EnQueue(q,x);// 货车上渡船 
				i++;//i计数，i>4,退出本循环 
				j++; //渡船上的总车辆数加1 
			}
			i=0;
		}
		if(QueueEmpty(q1)&&QueueEmpty(q2))
			j=11; //若货车和客车加起来不足10两 
	}
}