通过代码快速上手C语言数据结构-栈与队列

太过爱你忘了你带给我的痛 2023-01-16 02:40 132阅读 0赞

# 3.1-3.4顺序栈 #

## 3.1初始化顺序栈 ##

## 3.2顺序栈进栈运算 ##

## 3.3顺序栈出栈运算 ##

## 3.4顺序栈取栈顶元素运算 ##

顺序栈头文件

#define TRUE 1
    #define FALSE 0
    #define Stack_Size 50
    
    /*顺序栈*/
    
    typedef struct
    {
    	StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
    	int top;          		/*用来存放栈顶元素的下标，top为-1表示空栈*/
    }SeqStack;
    
    
    /*初始化*/
    void InitStack(SeqStack *S)
    {
    	/*构造一个空栈S*/
      	S->top = -1;
    }
    
    /*判栈空*/
    int IsEmpty(SeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
    {
    	return(S->top==-1?TRUE:FALSE);
    }
    
    /*判栈满*/
    int IsFull(SeqStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
    {
    	return(S->top==Stack_Size-1?TRUE:FALSE);
    }
    
    int Push(SeqStack *S,StackElementType x)
    {
    	if(S->top==Stack_Size-1)  
    		return(FALSE);  /*栈已满*/
    	S->top++;
    	S->elem[S->top] = x;
    	return(TRUE);
    }
    
    int Pop(SeqStack *S,StackElementType *x)
    {  
    	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
    	if(S->top == -1)  /*栈为空*/
    		return(FALSE);
    	else
    	{
      		*x = S->elem[S->top];
    		S->top--;    /* 修改栈顶指针 */
      		return(TRUE);
    	}
    }
    
    /*取栈顶元素。*/
    int GetTop(SeqStack *S,StackElementType *x)
    {  
    	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
    	if(S->top == -1)  /*栈为空*/
    		return(FALSE);
    	else
    	{
      		*x = S->elem[S->top];
      		return(TRUE);
    	}	
    }
    
    /*进行匹配*/
    int Match(char ch,char str)
    {		
    	if(ch=='(' && str==')')
    	{
    		return TRUE;
    	}
    	else if(ch=='[' && str==']')
    	{
    		return TRUE;
    	}
    	else if(ch=='{' && str=='}')
    	{
    		return TRUE;
    	}
    	else 
    		return FALSE;
    }

# 3.5-3.7双端顺序栈 #

## 3.5双端顺序栈初始化 ##

## 3.6双端顺序栈进栈操作 ##

## 3.7双端顺序栈出栈操作 ##

#define TRUE 1
    #define FALSE 0
    #define M 100
    
    typedef struct
    {
    	StackElementType Stack[M];
    	StackElementType top[2];  /*top[0]和top[1]分别为两个栈顶指示器*/
    }DqStack;
    
    /*初始化操作。*/
    void InitStack(DqStack *S)
    {
    	S->top[0]=-1;
    	S->top[1]=M;
    }
    
    /*进栈操作。*/
    int Push(DqStack *S,StackElementType x,int i)
    {
    	/*把数据元素x压入i号堆栈*/
    	if(S->top[0]+1==S->top[1]) /*栈已满*/
    		return(FALSE);
    	switch(i)
    	{
    	case 0:
    		S->top[0]++;
    		S->Stack[S->top[0]]=x;
    		break;
    	case 1:
    		S->top[1]--;
    		S->Stack[S->top[1]]=x;
    		break;
    	default:  /*参数错误*/
            return(FALSE)
     	}
    	return(TRUE);
    }
    
    /*出栈操作。*/
    int Pop(DqStack *S,StackElementType *x,int i)
    {
    	/* 从i 号堆栈中弹出栈顶元素并送到x中 */
    	switch(i)
    	{
    	case 0:
    		if(S->top[0]==-1)  
    			return(FALSE);
    		*x=S->Stack[S->top[0]];
    		S->top[0]--;
    		break;
    	case 1:
    		if(S->top[1]==M)  
    			return(FALSE);
    		*x=S->Stack[S->top[1]];
    		S->top[1]++;
    		break;
    	default:
    		return(FALSE);
    	}
    	return(TRUE);
    }

# 3.8-3.11链栈 #

## 3.8链栈进栈操作 ##

## 3.9链栈出栈操作 ##

## 3.10第i号栈进栈操作 ##

## 3.11第i号栈出栈操作 ##

#define TRUE 1
    #define FALSE 0
    
    typedef struct node
    {
    	StackElementType data;
    	struct node *next;
    }LinkStackNode;
    
    typedef LinkStackNode *LinkStack;
    
    /*进栈操作。*/
    int Push(LinkStack top, StackElementType x)/* 将数据元素x压入栈top中 */ 
    {
    	LinkStackNode *temp;
    	temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
     	if(temp==NULL)  
     		return(FALSE);   /* 申请空间失败 */
    	temp->data=x;
    	temp->next=top->next;
    	top->next=temp;   /* 修改当前栈顶指针 */ 
    	return(TRUE);
    }
    
    /*出栈操作。*/
    int Pop(LinkStack top, StackElementType *x)
    {  
    	/* 将栈top的栈顶元素弹出，放到x所指的存储空间中 */
    	LinkStackNode * temp;
    	temp=top->next;
    	if(temp==NULL)  /*栈为空*/
    		return(FALSE);
    	top->next=temp->next;
    	*x=temp->data;
    	free(temp);   /* 释放存储空间 */
    	return(TRUE);
    }

# 3.1-3.11完整实现 #

#include <stdio.h>
    #include <malloc.h>
    #include <conio.h>
    #include <dos.h>
    #define N 5
    #define PRICE 5
    //#define NULL 0
    
    /****************************************/
    typedef struct{
    	int boardnumber;
    	int arritime;
    }car;
    
    typedef struct{
    	car elem[N];
    	int top;
    }seqstack;
    
    typedef struct node{
    	car data;
    	struct node *next;
    }linkqueuenode;
    
    typedef struct{
    	linkqueuenode *front;
    	linkqueuenode *rear;
    }linkqueue;
    /*****************************************/
    void initstack(seqstack *s){
    	s->top=-1;
    }
    
    void initqueue(linkqueue *q){
    	q->front=(linkqueuenode*)malloc(sizeof(linkqueuenode));
    	if(q->front!=NULL){
    		q->rear=q->front;
    		q->front->next=NULL;
    	}
    }
    
    void enterqueue(linkqueue *q,car *x){
    	linkqueuenode *new1;
    	new1=(linkqueuenode *)malloc(sizeof(linkqueuenode));
    	if(new1!=NULL){
    		new1->data.boardnumber=x->boardnumber;
    		new1->data.arritime=x->arritime;
    		new1->next=NULL;
    		q->rear->next=new1;
    		q->rear=new1;
    	}
    }
    
    void deletequeue(linkqueue *q,car *p){	
    	    linkqueuenode *x;
    		if(q->front==q->rear) return 0;
    		x=q->front->next;
    		q->front->next=x->next;
    		if(q->rear==x)q->rear=q->front;
    		p->boardnumber=x->data.boardnumber;
    		p->arritime=x->data.arritime;
    	    free(x);
    }
    
    void pushstack(seqstack *s,car *x){
    	s->top++;
    	s->elem[s->top].boardnumber=x->boardnumber;
    	s->elem[s->top].arritime=x->arritime;
    }
    
    void popstack(seqstack *s,car *x){
    	x->boardnumber=s->elem[s->top].boardnumber;
    	x->arritime=s->elem[s->top].arritime;
    	s->top--;
    }
    
    void leave(seqstack *cheku,car *x){
    	int time,pay,leavetime;
    	printf("please input the leavetime:\n");
    	scanf("%d",&leavetime);
    	popstack(cheku,x);
    	time=leavetime-x->arritime;
    	pay=time*PRICE;
    	printf("Boardnumber   Arritime   Leavetime  Pay\n");
    	printf("%4d %14d %10d %8d\n",x->boardnumber,x->arritime,leavetime,pay);
    }
    /*************************************************************/
    main(){
    	seqstack cheku,chedao;
    	linkqueue biandao;
    	car x,y;
    	car xx;
    	//char b;
    	int k,m,j=1,p=0;
    	int choice=0;
    	//clrscr();
    	initstack(&cheku);
    	initstack(&chedao);
    	initqueue(&biandao);
    	while(choice!=4){
    		printf("/****************/\n");
    		printf("1.Enter Cheku\n");
    		printf("2.Enter Biandao\n");
    		printf("3.Leave\n");
    		printf("4.Exit\n");
    		printf("5.Print Out\n");
    		printf("Your selection:");
    		scanf("%d",&choice);
    		switch(choice){
    			case 1:
                                    p++;
                                    if(p>0&&p<6){
    					printf("please input the boardnumber and arritime of cars that go into cheku:\n");
    					scanf("%d,%d",&x.boardnumber,&x.arritime);
    					pushstack(&cheku,&x);
    					printf("\nBnum Intime No.InCheku\n");
    					printf("%6d %10d %10d\n",x.boardnumber,x.arritime,cheku.top+1);
    				}
    				else{
    					printf("/***************************************************/\n");
    					printf("Illegal input!There is only %d rooms in the cheku.\n",N);
    					printf("/***************************************************/\n");
    					p--;
    				}
    				break;
    			case 2:
    				printf("please input the boardnumber and arritime of cars that go into biandao:\n");
    				scanf("%d,%d",&y.boardnumber,&y.arritime);x=y;
    				enterqueue(&biandao,&x);
    				printf("\nBnum Intime No.InBiandao\n");
    				printf("%-6d %-10d %-10d\n",biandao.rear->data.boardnumber,biandao.rear->data.arritime,j);
    				j++;
    				break;
    			case 3:
    				printf("please input the position of the leaving car in cheku:\n");
    				scanf("%d",&k);
    				while(cheku.top>k){
    					popstack(&cheku,&x);
    					pushstack(&chedao,&x);
    					printf("chedao:%d %d %d\n",chedao.elem[chedao.top].boardnumber,chedao.elem[chedao.top].arritime,chedao.top);
    				}
    					y=cheku.elem[cheku.top];
    					leave(&cheku,&y);
    				while(chedao.top>=0){
    					popstack(&chedao,&x);
    					pushstack(&cheku,&x);
    					printf("cheku:%d %d %d\n",cheku.elem[cheku.top].boardnumber,cheku.elem[cheku.top].arritime,cheku.top);
    				}
    				if(biandao.front!=biandao.rear)
    					{
    						deletequeue(&biandao,&xx);
    						printf("XX:%d,%d\n",xx.boardnumber,xx.arritime);
    						pushstack(&cheku,&xx);
    					}
    				
    				
    				break;
    			case 4:
    				break;
    			case 5:  m=cheku.top;
    				while(m>-1){
    					printf("%d %d %d\n",cheku.elem[m].boardnumber,cheku.elem[m].arritime,m);
    					m--;
    				}
    		}
    	}
    }

# 3.12括号匹配算法 #

#define TRUE 1
    #define FALSE 0
    #define Stack_Size 50
    
    #define StackElementType char
    
    /*顺序栈*/
    
    typedef struct
    {
    	StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
    	int top;          		/*用来存放栈顶元素的下标，top为-1表示空栈*/
    }SeqStack;
    
    
    /*初始化*/
    void InitStack(SeqStack *S)
    {
    	/*构造一个空栈S*/
      	S->top = -1;
    }
    
    /*判栈空*/
    int IsEmpty(SeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
    {
    	return(S->top==-1?TRUE:FALSE);
    }
    
    /*判栈满*/
    int IsFull(SeqStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
    {
    	return(S->top==Stack_Size-1?TRUE:FALSE);
    }
    
    int Push(SeqStack *S,StackElementType x)
    {
    	if(S->top==Stack_Size-1)  
    		return(FALSE);  /*栈已满*/
    	S->top++;
    	S->elem[S->top] = x;
    	return(TRUE);
    }
    
    int Pop(SeqStack *S,StackElementType *x)
    {  
    	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
    	if(S->top == -1)  /*栈为空*/
    		return(FALSE);
    	else
    	{
      		*x = S->elem[S->top];
    		S->top--;    /* 修改栈顶指针 */
      		return(TRUE);
    	}
    }
    
    /*取栈顶元素。*/
    int GetTop(SeqStack *S,StackElementType *x)
    {  
    	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
    	if(S->top == -1)  /*栈为空*/
    		return(FALSE);
    	else
    	{
      		*x = S->elem[S->top];
      		return(TRUE);
    	}	
    }
    
    /*进行匹配*/
    int Match(char ch,char str)
    {		
    	if(ch=='(' && str==')')
    	{
    		return TRUE;
    	}
    	else if(ch=='[' && str==']')
    	{
    		return TRUE;
    	}
    	else if(ch=='{' && str=='}')
    	{
    		return TRUE;
    	}
    	else 
    		return FALSE;
    }
    #include <stdio.h>
    
    void BracketMatch(char *str);
    
    void BracketMatch(char *str) /* str[]中为输入的字符串，利用堆栈技术来检查该字符串中的括号是否匹配*/
    {
    	SeqStack S; 
    	int i; 
    	char ch;
    	
    	InitStack(&S);
    	
    	for(i=0; str[i]!='\0'; i++)   /*对字符串中的字符逐一扫描*/
    	{
        	switch(str[i])
        	{
    		case '(':
    		case '[':
    		case '{':
    			Push(&S,str[i]);  
    	        break;
          	case ')':
          	case ']':
          	case '}':
    			if(IsEmpty(&S))
    		    { 
    				printf("\n右括号多余!");  
    		        return;
    		    }
    			else
    			{
    				GetTop(&S,&ch);
    				if(Match(ch,str[i]))  /*用Match判断两个括号是否匹配*/
    					Pop(&S,&ch);      /*已匹配的左括号出栈*/
    	            else
    		        {
    		            printf("\n对应的左右括号不同类!");  
    		            return;
    		        }
    			}
    		}/*switch*/
    	}/*for*/
    	if(IsEmpty(&S))
    		printf("\n括号匹配!");
    	else
    		printf("\n左括号多余!");
    }
    
    void main()
    {
    	char str[100];
    	printf("please input:");
    	gets(str);
    	BracketMatch(str);
    }

# 3.13无括号算术表达式处理算法 #

#define TRUE 1
    #define FALSE 0
    #define Stack_Size 50
    
    
    /*顺序栈-整型*/
    typedef struct
    {
    	int elem[Stack_Size];  /*用来存放栈中元素的一维数组*/
    	int  top;          /*用来存放栈顶元素的下标，top为-1表示栈是空栈*/
    }nStack;
    
    /*初始化*/
    void  nInitStack(nStack *S)
    {
    /*构造一个空栈S*/
      	S->top=-1;
    }
    
    /*判栈空*/
    int nIsEmpty(nStack *S)	/*判断栈S为空栈时返回值为真，反之为假*/
    {
    	return(S->top==-1?TRUE:FALSE);
    }
    
    /*判栈满*/
    int nIsFull(nStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
    {
    	return(S->top==Stack_Size-1?TRUE:FALSE);
    }
    
    int nPush(nStack * S, int x)
    {
    	if(S->top== Stack_Size-1)  return(FALSE);  /*栈已满*/
    	S->top++;
    	S->elem[S->top]=x;
    	return(TRUE);
    }
    
    int nPop(nStack * S, int *x)
    {  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
    	if(S->top==-1)  /*栈为空*/
    		return(FALSE);
    	else
    	{
      		*x= S->elem[S->top];
    		S->top--;    /* 修改栈顶指针 */
      		return(TRUE);
    	}
    }
    
    int nGetTop(nStack *S, int *x)
    {  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
    	if(S->top==-1)  /*栈为空*/
    		return(FALSE);
    	else
    	{
      		*x = S->elem[S->top];
      		return(TRUE);
    	}
    }
    
    
    /*顺序栈-字符型*/
    typedef struct
    {
    	char elem[Stack_Size];  /*用来存放栈中元素的一维数组*/
    	int  top;          /*用来存放栈顶元素的下标，top为-1表示栈是空栈*/
    }strStack;
    
    /*初始化*/
    void strInitStack(strStack *S)
    {
    /*构造一个空栈S*/
      	S->top=-1;
    }
    
    /*判栈空*/
    int strIsEmpty(strStack *S)	/*判断栈S为空栈时返回值为真，反之为假*/
    {
    	return(S->top==-1?TRUE:FALSE);
    }
    
    /*判栈满*/
    int strIsFull(strStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
    {
    	return(S->top==Stack_Size-1?TRUE:FALSE);
    }
    
    char strPush(strStack * S, char x)
    {
    	if(S->top== Stack_Size-1)  return(FALSE);  /*栈已满*/
    	S->top++;
    	S->elem[S->top]=x;
    	return(TRUE);
    }
    
    char strPop(strStack * S, char *x)
    {  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
    	if(S->top==-1)  /*栈为空*/
    		return(FALSE);
    	else
    	{
      		*x= S->elem[S->top];
    		S->top--;    /* 修改栈顶指针 */
      		return(TRUE);
    	}
    }
    
    int strGetTop(strStack *S, char *x)
    {  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
    	if(S->top==-1)  /*栈为空*/
    		return(FALSE);
    	else
    	{
      		*x = S->elem[S->top];
      		return(TRUE);
    	}
    }
    
    /*功能函数*/
    int Match(char ch,char str)
    {		
    	if(ch=='('&&str==')')
    	{
    		return TRUE;
    	}
    	else if(ch=='['&&str==']')
    	{
    		return TRUE;
    	}
    	else if(ch=='{'&&str=='}')
    	{
    		return TRUE;
    	}
    	else return FALSE;
    }
    
    int In(char ch)
    {
    	if(ch=='+')
    	{
    		return TRUE;	
    	}
    	else if(ch=='-') 
    	{
    		return TRUE;	
    	}
    	else if(ch=='*')
    	{
    		return TRUE;	
    	}
    	else if(ch=='/')
    	{
    		return TRUE;	
    	}
    	else if(ch=='(')
    	{
    		return TRUE;	
    	}
    	else if(ch==')')
    	{
    		return TRUE;	
    	}
    	else if(ch=='#')
    	{
    		return TRUE;	
    	}
    	else return FALSE;
    }
    
    char Compare(char x,char ch)
    {
    	switch(x)
    	{
    	case '+':
    		if(ch=='+'||ch=='-'||ch==')'||ch=='#')
    			return '>';	
    		else if(ch=='*'||ch=='/'||ch=='(')
    				return '<';	
    		break;
    	case '-':
    		if(ch=='+'||ch=='-'||ch==')'||ch=='#')
    			return '>';	
    		else if(ch=='*'||ch=='/'||ch=='(')
    			return '<';	
    		break;
    	case '*':
    		if(ch=='(')
    		{
    			return '<';
    		}
    		else
    		{
    			return '>';
    		}
    		break;
    	case '/':
    		if(ch=='(')
    				return '<';	
    		else
    				return '>';	
    		break;
    	case '(':
    		if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='(')
    			return '<';	
    		else if(ch==')')
    			return '=';	
    		else if(ch=='#')
    			return '0';	
    		break;
    	case ')':
    		if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch==')'||ch=='#')
    			return '>';	
    		else if(ch=='(')
    			return '0';	
    		break;
    	case '#':
    		if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='(')
    			return '<';	
    		else if(ch=='#')
    			return '=';	
    		else if(ch==')')
    			return '0';	
    		break;	
    	default:
    		return '0';
    		break;
    	}
    
    }	
    
    int Execute(int a,char op,int b)
    {
    	switch(op)
    	{
    	case '+':
    		return (a+b);
    		break;
    	case '-':
    		return (a-b);
    		break;
    	case '*':
    		return (a*b);
    		break;
    	case '/':
    		return (a/b);
    		break;
    	}
    }
    #include "stdio.h"
    #include <conio.h>
    
    
    char ch;
    
    int ExpEvaluation()/*读入一个简单算术表达式并计算其值。operatsign和operatdata分别为运算符栈和运算数栈，OPS为运算符集合*/
    {
    	char x,y;
    	char op;
    	int a,b,v;
    	
    	nStack operatdata;
    	strStack operatsign;
    	nInitStack(&operatdata);
    	strInitStack(&operatsign);
    	strPush(&operatsign,'#');
    	
    	printf("\nPlease input an expression (Ending with #) :\n");
        ch=getchar();
    
     	
     	strGetTop(&operatsign,&y);
    
     	while(ch!='#'||y!='#') /* strGetTop()通过函数值返回栈顶元素*/
       	{
    		if(!In(ch))                   /*不是运算符，是运算数*/
    		{
    			
    			int temp; 		   /*存放数字的临时变量*/
    			temp=ch-'0';
    			/*将字符转换为十进制数*/
    			fflush(stdin);
    			ch=getchar();
    			while(!In(ch))  //用ch逐个读入运算数的各位数码，并转化为十进制数temp
    			{
    				temp=temp*10+ch-'0'; // 将逐个读入运算数的各位转化为十进制数
    	 			fflush(stdin);
    				ch=getchar();
    			}  
       			nPush(&operatdata,temp);
    		}
    		else
          		switch(Compare(y,ch))
    			{
    	 			case '<': 
    					strPush(&operatsign,ch); 
                  		fflush(stdin);
    					ch=getchar();
    					break;
    	 			case '=': 
    					strPop(&operatsign,&x); 
    					fflush(stdin);
    					ch=getchar(); 
    					break;
    				case '>': 
    					strPop(&operatsign,&op);
    					nPop(&operatdata,&b);
    					nPop(&operatdata,&a);
    					v=Execute(a,op,b);  /* 对a和b进行op运算 */
    					nPush(&operatdata,v);
    					break;
    			}
    		strGetTop(&operatsign,&y);
    	}
    	nGetTop(&operatdata,&v);
    	return (v);
    }
    
    void main()
    {
    	int result;   
        result=ExpEvaluation();
        printf("\n%d",result);
    }

# 3.14-3.15汉诺塔 #

## 3.14汉诺塔递归算法 ##

## 3.15汉诺塔非递归算法示意 ##

#include "stdio.h"
    
    
    move(char a,char c,FILE **fp,int *count)
    {
    (*count)++;
    printf("%6d:%c-->%c\n",*count,a,c);
    fprintf(*fp,"%6d:%c-->%c\n",*count,a,c);
    }
    
    
    hanoi(int n, char a, char b, char c, FILE **fp, int *count)
    {
    if(n==1) move(a,c,fp,count);
    else
    {
    hanoi(n-1,a,c,b,fp,count);
    move(a,c,fp,count);
    hanoi(n-1,b,a,c,fp,count);
    }
    }
    
    
    main()
    {
    int n,count=0; /*count用来记录移动次数*/
    FILE *fp;
    fp=fopen("hanoi.txt","w");
    printf("Input the number of disk:");
    scanf("%d",&n);
    fprintf(fp,"%d disks hanoi tower:\n",n);
    hanoi(n,'A','B','C',&fp,&count);
    fclose(fp);
    }

# 3.16斐波那契数列的非递归算法 #

# 3.17求n!非递归算法 #

# 3.18-3.20链队 #

## 3.18链队列初始化 ##

## 3.19链队列入队操作算法 ##

## 3.20链队列出队操作算法 ##

#define  TRUE 1
    #define  FALSE 0
    
    #define MAXSIZE 50  /*队列的最大长度*/
    
    typedef struct Node
    {
    	QueueElementType data;     /*数据域*/
    	struct Node *next;     /*指针域*/
    }LinkQueueNode;
    
    typedef struct 
    {
    	LinkQueueNode *front;
    	LinkQueueNode *rear;
    }LinkQueue;
    
    /*初始化操作。*/
    int InitQueue(LinkQueue *Q)
    { 
    	/* 将Q初始化为一个空的链队列 */
    	Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    	if(Q->front!=NULL)
    	{
    		Q->rear=Q->front;
    		Q->front->next=NULL;
     		return(TRUE);
    	}
    	else return(FALSE);    /* 溢出！*/
    }
    
    /*入队操作。*/
    int EnterQueue(LinkQueue *Q,QueueElementType x)
    {  
    	/* 将数据元素x插入到队列Q中 */
    	LinkQueueNode *NewNode;
    	NewNode=(LinkQueueNode * )malloc(sizeof(LinkQueueNode));
    	if(NewNode!=NULL)
    	{
    		NewNode->data=x;
    		NewNode->next=NULL;
    		Q->rear->next=NewNode;
    		Q->rear=NewNode;
    		return(TRUE);
    	}
    	else  return(FALSE);    /* 溢出！*/
    }
    
    /*出队操作。*/
    int DeleteQueue(LinkQueue *Q,QueueElementType *x)
    {  
    	/* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */
    	LinkQueueNode * p;
    	if(Q->front==Q->rear)
    		return(FALSE);
    	p=Q->front->next;
    	Q->front->next=p->next;  /* 队头元素p出队 */
    	if(Q->rear==p)  /* 如果队中只有一个元素p，则p出队后成为空队 */
    		Q->rear=Q->front;  
    	*x=p->data;
    	free(p);   /* 释放存储空间 */
    	return(TRUE);	
    }
    
    int GetHead(SeqQueue *Q, int *x)
    { 
    	/*提取队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(FALSE);
    	*x=Q->element[Q->front];
    	return(TRUE);  /*操作成功*/
    }

# 3.21-3.23循环队列 #

## 3.21循环队列初始化操作 ##

## 3.22循环队列入队操作 ##

## 3.23循环队列出队操作 ##

#define  TRUE 1
    #define  FALSE 0
    
    #define MAXSIZE 50  /*队列的最大长度*/
    
    typedef struct
    {
    	QueueElementType  element[MAXSIZE];  /* 队列的元素空间*/
    	int front;  /*头指针指示器*/
    	int rear;  /*尾指针指示器*/
    }SeqQueue;
    
    
    /*初始化操作*/
    void InitQueue(SeqQueue *Q)
    {  
    	/* 将*Q初始化为一个空的循环队列 */
    	Q->front=Q->rear=0;
    }
    
    /*入队操作*/
    int EnterQueue(SeqQueue *Q, QueueElementType x)
    {  
    	/*将元素x入队*/
    	if((Q->rear+1)%MAXSIZE==Q->front)  /*队列已经满了*/
    		return(FALSE);
    	Q->element[Q->rear]=x;
    	Q->rear=(Q->rear+1)%MAXSIZE;  /* 重新设置队尾指针 */
    	return(TRUE);  /*操作成功*/
    }
    
    /*出队操作*/
    int DeleteQueue(SeqQueue *Q, QueueElementType *x)
    { 
    	/*删除队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(FALSE);
    	*x=Q->element[Q->front];
    	Q->front=(Q->front+1)%MAXSIZE;  /*重新设置队头指针*/
    	return(TRUE);  /*操作成功*/
    }
    
    int GetHead(SeqQueue *Q, QueueElementType *x)
    { 
    	/*提取队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(FALSE);
    	*x=Q->element[Q->front];
    	return(TRUE);  /*操作成功*/
    }
    
    int IsEmpty(SeqQueue *Q)
    { 
    	/*提取队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(TRUE);
    	else
    		return(FALSE);  /*操作成功*/
    }

# 3.18-3.23实现 #

#define FALSE  0
    #define TURE   1
    #define N     3
    
    #include<malloc.h>
    #include<stdio.h>
    
    /***************************************************************/
    
    typedef struct    /* 定义数据汽车类数据类型  */
    {
          int  number;
          int  t_come;
          int  t_go;
    } car,*CAR;
    
    
    typedef struct Stack    /*模拟栈 */
    {
       CAR c[N];
       int n;
    }Stack;
    
    
    typedef struct Node
    {
        car *Car;
        struct Node *next;
    
    }LinkQueueNode;
    
    typedef struct
    {
    	LinkQueueNode *front;
    	LinkQueueNode *rear;
    }LinkQueue;
    
    
    
    
    
    Stack S;
    LinkQueue Q;
    int   Time;
    
    /*******************************************************************/
    
    void print();
    int Init_queue()
    {
    	Q.front=(LinkQueueNode *)
    		malloc(sizeof(LinkQueueNode));
    	if(Q.front !=NULL)
    	{
    		Q.rear =Q.front ;
    		Q.front ->next =NULL;
                    return( TURE );
         }
      	else return(FALSE);
    }
    
    /*=====================================================================*/
    
    int Enter_queue( car x) /*入队，成功返回在对中的位置，否则返回 0 */
    {
    	LinkQueueNode *p=Q.front;
        int i=0;
        LinkQueueNode *temp;
        temp=(LinkQueueNode *)
    	    malloc(sizeof(LinkQueueNode));
    	if(temp == NULL)
    		return( FALSE);
    	else
    	{
    		*(temp->Car) = x;
                    temp->next = NULL;
    		Q.rear ->next=temp;
    		Q.rear=temp;
                    while(p!=Q.rear)
                    {
                       p=p->next;
                       i++;
                    }
    		return(i);
    
    	}
    }
    
    /*=================================================================*/
    
    CAR DeletQueue()
    {
    	LinkQueueNode *p;
    	if(Q.front == Q.rear)
    	    return( FALSE);
        p=Q.front->next;
    	Q.front ->next=p->next ;
    	if(Q.rear==p)
    		Q.rear=Q.front;
    	p->Car->t_come =Time;
        return(p->Car);
    }
    
    /*=================================================================*/
    
    comein()
    {
           car mm;
    
    
           printf("\n\tPlease put in the coming car's number: ");
    	   scanf("%d",&mm.number);
    
    
           printf("\n\tPlease put in the car's come time: ");
    	      scanf("%d",&mm.t_come);
    	   Time=mm.t_come ;            /*全局时间变量*/
           if(S.n<N)
           {
               car *temp;
    		   temp=(car *)malloc(sizeof(car));
    		   *temp=mm;
    	       S.c[S.n]=temp;
                  S.n++;
    	       printf("\nThe car insert the stack %d",S.n);
           }
           else
           {
    	       printf("\n\rThe car insert the queue %d",Enter_queue(mm));
           }
    
    }
    
    /*----------------------------------------------------------------------*/
    
    goout()
    {
          int i,j;
          int str;
          CAR mm;
          printf("\n\tPlease put in the number of the going car: ");
                 scanf("%d",&str);
          for(i=0;i<S.n;i++)
          {
               if(str == S.c[i]->number)
               {
    	       printf("\n\tPlease put in the go time: ");
    		   scanf("%d",&Time);
    		   S.c[i]->t_go=Time;
    	       printf("\n Stop time is %d",S.c[i]->t_go - S.c[i]->t_come);
    	       for(j=i;j<S.n-1;j++)
    	         S.c[j]=S.c[j+1];
    	       S.n--;
    
    	       break;
               }
    
          }
          if(Q.rear != Q.front)
          {
             S.c[S.n]=DeletQueue();
             S.n++;
    
          }
          if(i==N || S.n==0)
                 printf(" Not in the stack");
    
    }
    
    /*=====================================================================*/
    void print()
    {
       int i;
       LinkQueueNode *temp=Q.front;
       printf("\n\n----------------------------------------\n");
       printf("The cars in the Stack\n");
       printf("place \t number\n");
       for(i=0;i<S.n;i++)
         printf("%4d\t %4d \n",i+1, S.c[i]->number);
       i=0;
    
       if(Q.front != Q.rear)
       {
           printf("\nThe cars in the queue:\n");
           printf("place \t number\n");
           while(temp!=Q.rear)
           {
    	     i++;
    	     temp=temp->next;
    	     printf("%4d \t %4d \n",i, temp->Car->number);
           }
       }
       else
         printf("\nThere is no car in the queue.");
       printf("\n------------------------ok------------");
    }
    main()
    {
        int k;
        char ch;
        S.n=0;
        Init_queue();
    
        while(1)
        {
           printf("\n\n\rPLEASE CHOSE:\n\tC: COME IN\n\tG: GO OUT \n\tF: LOOK\n\t0: EXIT");
           ch=getch();
    
           if(ch=='c'||ch=='C')
    	   comein();
           else if(ch=='g'||ch=='G')
    	   goout();
           else if(ch=='f'||ch=='F')
    	    print();
           else if(ch=='0'||ch=='O' || ch=='o'||ch==27)
    	   break;
         }
    
         for(k=0;k<N;k++)
         {
              printf("%d",S.c[k]->number);
         }
    }
    /*the end*/

# 3.24打印杨辉三角前n行算法 #

#define  TRUE 1
    #define  FALSE 0
    
    #define MAXSIZE 50  /*队列的最大长度*/
    
    typedef struct
    {
    	int element[MAXSIZE];  /* 队列的元素空间*/
    	int front;  /*头指针指示器*/
    	int rear;  /*尾指针指示器*/
    }SeqQueue;
    
    
    /*初始化操作*/
    void InitQueue(SeqQueue *Q)
    {  
    	/* 将*Q初始化为一个空的循环队列 */
    	Q->front=Q->rear=0;
    }
    
    /*入队操作*/
    int EnterQueue(SeqQueue *Q, int x)
    {  
    	/*将元素x入队*/
    	if((Q->rear+1)%MAXSIZE==Q->front)  /*队列已经满了*/
    		return(FALSE);
    	Q->element[Q->rear]=x;
    	Q->rear=(Q->rear+1)%MAXSIZE;  /* 重新设置队尾指针 */
    	return(TRUE);  /*操作成功*/
    }
    
    /*出队操作*/
    int DeleteQueue(SeqQueue *Q, int *x)
    { 
    	/*删除队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(FALSE);
    	*x=Q->element[Q->front];
    	Q->front=(Q->front+1)%MAXSIZE;  /*重新设置队头指针*/
    	return(TRUE);  /*操作成功*/
    }
    
    int GetHead(SeqQueue *Q, int *x)
    { 
    	/*提取队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(FALSE);
    	*x=Q->element[Q->front];
    	return(TRUE);  /*操作成功*/
    }
    
    #include <stdio.h>
    
    void YangHuiTriangle( )
    { 
    	int n;
    	int i;
    	int temp;
    	int x;
    	int N;
    	SeqQueue Q;
    	InitQueue(&Q);
    	EnterQueue(&Q,1);  /* 第一行元素入队*/
    	printf("please input N:");
    	scanf("%d",&N);
    	for(n=2;n<=N;n++)   /* 产生第n行元素并入队，同时打印第n-1行的元素*/
    	{
    		EnterQueue(&Q,1);   /* 第n行的第一个元素入队*/
    		for(i=1;i<=n-2;i++)  /* 利用队中第n-1行元素产生第n行的中间n-2个元素并入队*/
    		{
    			DeleteQueue(&Q,&temp);
    			printf("%6d",temp);     /* 打印第n-1行的元素*/
    			GetHead(&Q,&x);
    			temp=temp+x;      /*利用队中第n-1行元素产生第n行元素*/
    			EnterQueue(&Q,temp);  
    		}
    		DeleteQueue (&Q,&x);  
    		printf("%6d",x);    /* 打印第n-1行的最后一个元素*/
    		EnterQueue(&Q,1);   /* 第n行的最后一个元素入队*/
    		printf("\n");
    	}
    }
    
    void main()
    {
    	YangHuiTriangle( );
    }

# 3.25键盘输入循环缓冲区算法 #

#include "stdio.h"
    #include "conio.h"
    
    #define  TRUE 1
    #define  FALSE 0
    #define  QueueElementType char
    
    #define MAXSIZE 50  /*队列的最大长度*/
    
    typedef struct
    {
    	QueueElementType  element[MAXSIZE];  /* 队列的元素空间*/
    	int front;  /*头指针指示器*/
    	int rear;  /*尾指针指示器*/
    }SeqQueue;
    
    
    /*初始化操作*/
    void InitQueue(SeqQueue *Q)
    {  
    	/* 将*Q初始化为一个空的循环队列 */
    	Q->front=Q->rear=0;
    }
    
    /*入队操作*/
    int EnterQueue(SeqQueue *Q, QueueElementType x)
    {  
    	/*将元素x入队*/
    	if((Q->rear+1)%MAXSIZE==Q->front)  /*队列已经满了*/
    		return(FALSE);
    	Q->element[Q->rear]=x;
    	Q->rear=(Q->rear+1)%MAXSIZE;  /* 重新设置队尾指针 */
    	return(TRUE);  /*操作成功*/
    }
    
    /*出队操作*/
    int DeleteQueue(SeqQueue *Q, QueueElementType *x)
    { 
    	/*删除队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(FALSE);
    	*x=Q->element[Q->front];
    	Q->front=(Q->front+1)%MAXSIZE;  /*重新设置队头指针*/
    	return(TRUE);  /*操作成功*/
    }
    
    int GetHead(SeqQueue *Q, QueueElementType *x)
    { 
    	/*提取队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(FALSE);
    	*x=Q->element[Q->front];
    	return(TRUE);  /*操作成功*/
    }
    
    int IsEmpty(SeqQueue *Q)
    { 
    	/*提取队列的队头元素，用x返回其值*/
    	if(Q->front==Q->rear)  /*队列为空*/
    		return(TRUE);
    	else
    		return(FALSE);  /*操作成功*/
    }
    
    main()
    {
    	char ch1,ch2;
    	SeqQueue  Q;
    	int f;
    	InitQueue (&Q);
    
    	while(TRUE)
    	{
    		while(TRUE)
    		{
    			printf("A");
    
    			if(kbhit())
    			{
    				ch1=getch();
    				if(ch1==';'||ch1=='.')
    					break;
    				f= EnterQueue(&Q,ch1);
    				if(f==FALSE)
    				{
    					printf("full");
    					break;
    				}
    			}
    
    		}
    		while (!IsEmpty(&Q))
    		{
    			DeleteQueue(&Q,&ch2);
    			putchar(ch2);
    		}
    		getch();
    		if(ch1=='.') break;
    	}
    }

# 多链栈头文件模板 #

#define  M  10   /*M个链栈*/
    #define TRUE 1
    #define FALSE 0
    
    typedef struct node
    {
    	StackElementType data;
    	struct node *next;
    }LinkStackNode,  *LinkStack;
    LinkStack  top[M];
    
    /*第i号栈的进栈操作*/
    int  pushi(LinkStack top[M],int i,StackElementType x)
    {
    	/*将元素x进入第i号链栈*/
    	LinkStackNode  *temp;
    	temp=(LinkStackNode * )malloc(sizeof(LinkStackNode));
    	if(temp==NULL)  
    		return(FALSE);   /* 申请空间失败 */
    	temp->data=x;
    	temp->next=top[i]->next;
    	top[i]->next=temp;   /* 修改当前栈顶指针 */ 
    	return(TRUE);
    }
    
    /*第i号栈元素的出栈操作*/
    int Pop(LinkStack top[M],int i,StackElementType *x)
    {  
    	/* 将栈top的栈顶元素弹出，放到x所指的存储空间中 */
    	LinkStackNode *temp;
    	temp=top[i]->next;
    	if(temp==NULL)  /*第i号栈为空栈*/
    		return(FALSE);
    	top[i]->next=temp->next;
    	*x=temp->data;
    	free(temp);   /* 释放存储空间 */
    	return(TRUE);
    }

# 链队列头文件模板 #

# 循环队列头文件模板 #