《大话数据结构》第四章栈和队列

灰太狼 2022-03-17 15:18 237阅读 0赞

### 《大话数据结构 》 ###

*  第四章 栈和队列
 *   *  栈
     *   *  顺序存储的栈存储空间需要事先确定
         *  两栈共享空间适当会提供空间使用率
         *  链式存储的栈
     *  斐波那契数列
     *  顺序队列存在假溢出
     *  顺序队列改成循环队列解决假溢出问题
     *  链式存储队列
     *  顺序线性表、链表、静态链 表、顺序栈、两栈共享空间、循环队列、链式队列比较

# 第四章 栈和队列 #

**栈：只允许在表尾进行插入和删除操作的线性表。**  
  **队列：只允许在一端进行插入操作、在另一端进行删除操作的线性表。**

## 栈 ##

首先不要定势思维以为最先入栈的元素，最后就只能最后出栈。例如有1、2、3 依次进栈，会有哪些出栈顺序？可以有1进，1出，2进，2出，3进，3出，那么出栈顺序是123。可以有1进，2进，2出，3进，3出，1出，那么出栈顺序是231。诸如这样调整顺序，总共可以有5种，唯一不可能是312，因为要3第一个出来，意味着1、2都还在栈里，那么2肯定是比1更靠近栈顶的，此时3要第一个出来只能是321情形。

### 顺序存储的栈存储空间需要事先确定 ###

顺序栈数据结构：

typedef int SElemType; 
    typedef struct { 
    	SElemType data[MAXSIZE];
    	int top; //栈顶指针
    }Sqstack;  //Sequence 顺序

入栈：Push

Status Push(Sqstack *S,SElemType e)
    { 
    	if(S->TOP == MAXSIZE - 1)  //若栈满
    		return ERROR;
    	S->top ++;
    	S->data[S->top] = e;
    	return OK;
    }

出栈：Pop

Status Pop(Sqstack *S,SElemType e)
    { 
    	if(S->top == -1)   //若栈本身就是空的 出栈报错
    		return ERROR;
    	e = S->data[S->top] ;
    	s->top --;
    	return OK;
    }

**顺序存储的栈还是很方便的，只允许栈顶进出元素，所以不存在线性表插入和删除时需要移动元素问题，不过有个很大的缺陷需要实现确定存储空间。栈的出栈和入栈都没有循环，时间复杂度是O（1）**。

### 两栈共享空间适当会提供空间使用率 ###

上诉的顺序存储的栈若实现分配太大的空间，浪费内存，若太小，扩展麻烦。**若存在两个相同类型的栈，注意是存储相同类型的栈，可以共享空间最大限度利用存储空间**。  
    ![在这里插入图片描述][20190225102458662.png]  
  共享空间时，进栈和出栈相比单个顺序存储需要进行判断是哪个栈。并且栈顶指针一个是一直增加，一个是一直减少。所以，通常这两个栈的空间需求是有相反关系，否则若两个栈都是递增会很快因栈满而溢出。

Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
    { 
    	if(S->top1 +1 == S->top2)    //若栈已满，不能再push新元素
    		return ERROR;
    	if(stackNumber == 1) 		 //栈1 有元素进栈
    		S->data[++S->top1] = e;  //栈1先top1+1后给数组元素赋值
    	else if(stackNumber == 2)    //栈2有元素进栈
    		S->data[-- S->top2] = e;
    	return OK;
    }

出栈：

Status Pop(SqDoubleStack *S,SElemType e,int stackNumber)
    { 
    	if(stackNumber == 1)
    	{ 
    		if(S->top1 == -1)  		 //说明栈1是空栈
    			return ERROR;
    		*e = S->data[S->top1 --];
    	}
    	if(stackNumber == 2)
    	{ 
    		if(S->top2 == MAXSIZE)	 //说明栈2是空栈
    			return ERROR;
    		*e = S->data[S->top2 ++];
    	}
    	return OK;
    }

两栈共享空间实例：

#include "stdio.h" 
 	#include "stdlib.h" 
 	#include "io.h" 
 	#include "math.h" 
 	#include "time.h"
 	
 	#define OK 1
 	#define ERROR 0
 	#define TRUE 1
 	#define FALSE 0
 	#define MAXSIZE 20 /* 存储空间初始分配量 */	
 	typedef int Status; 	
 	typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */		
 	/* 两栈共享空间结构 */
 	typedef struct 
 	{ 
 	 SElemType data[MAXSIZE];
 	 int top1;	/* 栈1栈顶指针 */
 	 int top2;	/* 栈2栈顶指针 */
 	}SqDoubleStack;
 		
 	Status visit(SElemType c)
 	{ 
 	 printf("%d ",c);
 	 return OK;
 	}	
 	/* 构造一个空栈S */
 	Status InitStack(SqDoubleStack *S)
 	{ 
 	 S->top1=-1;
 	 S->top2=MAXSIZE;
 	 return OK;
 	}	
 	/* 把S置为空栈 */
 	Status ClearStack(SqDoubleStack *S)
 	{ 
 	 S->top1=-1;
 	 S->top2=MAXSIZE;
 	 return OK;
 	}	
 	/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
 	Status StackEmpty(SqDoubleStack S)
 	{ 
 	 if (S.top1==-1 && S.top2==MAXSIZE)
 	 return TRUE;
 	 else
 	 return FALSE;
 	}	
 	/* 返回S的元素个数，即栈的长度 */
 	int StackLength(SqDoubleStack S)
 	{ 
 	 return (S.top1+1)+(MAXSIZE-S.top2);
 	}	
 	/* 插入元素e为新的栈顶元素 */
 	Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
 	{ 
 	 if (S->top1+1==S->top2)	/* 栈已满，不能再push新元素了 */
 	 return ERROR;	
 	 if (stackNumber==1)			/* 栈1有元素进栈 */
 	 S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */
 	 else if (stackNumber==2)	/* 栈2有元素进栈 */
 	 S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */
 	 return OK;
 	}	
 	/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
 	Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
 	{ 
 	 if (stackNumber==1) 
 	 { 
 	 if (S->top1==-1) 
 	 return ERROR; /* 说明栈1已经是空栈，溢出 */
 	 *e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
 	 }
 	 else if (stackNumber==2)
 	 { 
 	 if (S->top2==MAXSIZE) 
 	 return ERROR; /* 说明栈2已经是空栈，溢出 */
 	 *e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
 	 }
 	 return OK;
 	}	
 	Status StackTraverse(SqDoubleStack S)
 	{ 
 	 int i;
 	 i=0;
 	 while(i<=S.top1)
 	 { 
 	 visit(S.data[i++]);
 	 }
 	 i=S.top2;
 	 while(i<MAXSIZE)
 	 { 
 	 visit(S.data[i++]);
 	 }
 	 printf("\n");
 	 return OK;
 	}	
 	int main()
 	{ 
 	 int j;
 	 SqDoubleStack s;
 	 int e;
 	 if(InitStack(&s)==OK)
 	 { 
 	 for(j=1;j<=5;j++)
 	 Push(&s,j,1);
 	 for(j=MAXSIZE;j>=MAXSIZE-2;j--)
 	 Push(&s,j,2);
 	 }
 	
 	 printf("栈中元素依次为：");
 	 StackTraverse(s);
 	
 	 printf("当前栈中元素有：%d \n",StackLength(s));
 	
 	 Pop(&s,&e,2);
 	 printf("弹出的栈顶元素 e=%d\n",e);
 	 printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
 	
 	 for(j=6;j<=MAXSIZE-2;j++)
 	 Push(&s,j,1);
 	
 	 printf("栈中元素依次为：");
 	 StackTraverse(s);
 	
 	 printf("栈满否：%d(1:否 0:满)\n",Push(&s,100,1));
 		 
 	 ClearStack(&s);
 	 printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
 	 
 	 return 0;
 	}

运行结果：  
        ![在这里插入图片描述][20190225125053267.png]

### 链式存储的栈 ###

链式存储的栈结构：

/* 链栈结构 */
    	typedef struct StackNode
    	{ 
    	        SElemType data;
    	        struct StackNode *next;
    	}StackNode,*LinkStackPtr;	
    	
    	typedef struct
    	{ 
    	        LinkStackPtr top;   //栈顶指针
    	        int count;
    	}LinkStack;

链式存储栈实例：

#include "stdio.h" 
 	#include "stdlib.h" 
 	#include "io.h" 
 	#include "math.h" 
 	#include "time.h"		
 	#define OK 1
 	#define ERROR 0
 	#define TRUE 1
 	#define FALSE 0
 	#define MAXSIZE 20 /* 存储空间初始分配量 */	
 	typedef int Status; 
 	typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */	
 	/* 链栈结构 */
 	typedef struct StackNode
 	{ 
 	 SElemType data;
 	 struct StackNode *next;
 	}StackNode,*LinkStackPtr;	
 	typedef struct
 	{ 
 	 LinkStackPtr top;
 	 int count;
 	}LinkStack;	
 	Status visit(SElemType c)
 	{ 
 	 printf("%d ",c);
 	 return OK;
 	}	
 	/* 构造一个空栈S */
 	Status InitStack(LinkStack *S)
 	{ 
 	 S->top = (LinkStackPtr)malloc(sizeof(StackNode));
 	 if(!S->top)
 	 return ERROR;
 	 S->top=NULL;
 	 S->count=0;
 	 return OK;
 	}	
 	/* 把S置为空栈 */
 	Status ClearStack(LinkStack *S)
 	{ 
 	 LinkStackPtr p,q;
 	 p=S->top;
 	 while(p)
 	 { 
 	 q=p;
 	 p=p->next;
 	 free(q);
 	 } 
 	 S->count=0;
 	 return OK;
 	}	
 	/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
 	Status StackEmpty(LinkStack S)
 	{ 
 	 if (S.count==0)
 	 return TRUE;
 	 else
 	 return FALSE;
 	}	
 	/* 返回S的元素个数，即栈的长度 */
 	int StackLength(LinkStack S)
 	{ 
 	 return S.count;
 	}	
 	/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
 	Status GetTop(LinkStack S,SElemType *e)
 	{ 
 	 if (S.top==NULL)
 	 return ERROR;
 	 else
 	 *e=S.top->data;
 	 return OK;
 	}	
 	/* 插入元素e为新的栈顶元素 */
 	Status Push(LinkStack *S,SElemType e)
 	{ 
 	 LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); 
 	 s->data=e; 
 	 s->next=S->top;	/* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
 	 S->top=s; /* 将新的结点s赋值给栈顶指针，见图中② */
 	 S->count++;
 	 return OK;
 	}	
 	/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
 	Status Pop(LinkStack *S,SElemType *e)
 	{ 
 	 LinkStackPtr p;
 	 if(StackEmpty(*S))
 	 return ERROR;
 	 *e=S->top->data;
 	 p=S->top;					/* 将栈顶结点赋值给p，见图中③ */
 	 S->top=S->top->next; /* 使得栈顶指针下移一位，指向后一结点，见图中④ */
 	 free(p); /* 释放结点p */ 
 	 S->count--;
 	 return OK;
 	}	
 	Status StackTraverse(LinkStack S)
 	{ 
 	 LinkStackPtr p;
 	 p=S.top;
 	 while(p)
 	 { 
 	 visit(p->data);
 	 p=p->next;
 	 }
 	 printf("\n");
 	 return OK;
 	}	
 	int main()
 	{ 
 	 int j;
 	 LinkStack s;
 	 int e;
 	 if(InitStack(&s)==OK)
 	 for(j=1;j<=10;j++)
 	 Push(&s,j);
 	 printf("栈中元素依次为：");
 	 StackTraverse(s);
 	 Pop(&s,&e);
 	 printf("弹出的栈顶元素 e=%d\n",e);
 	 printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
 	 GetTop(s,&e);
 	 printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
 	 ClearStack(&s);
 	 printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
 	 return 0;
 	}

运行结果：  
      ![在这里插入图片描述][20190225124802601.png]

## 斐波那契数列 ##

假设所有兔子出生两个月后就有繁殖能力，一对兔子每个月能生出一对小兔子。假设所有兔子都不死，开始是一对小兔子，那么一个月后有多少对兔子？  
      ![在这里插入图片描述][20190225130117381.png]  
  斐波那契数列数列明显的特点：前面相邻两项之和等于后一项。

*  F(n) = 0 当n=0时
 *  F(n) = 1 当n = 1时
 *  F(n) = F(n-1)+F(n-2) 当n>1时

用递归实现明显相比迭代会整洁很多。

#include "stdio.h"
 
 int Fbi(int i) /* 斐波那契的递归函数 */
 { 
 	if( i < 2 )
 		return i == 0 ? 0 : 1; 
 return Fbi(i - 1) + Fbi(i - 2); /* 这里Fbi就是函数自己，等于在调用自己 */
 } 
 
 int main()
 { 
 	int i;
 	int a[40]; 
 	printf("迭代显示斐波那契数列：\n");
 	a[0]=0;
 	a[1]=1;
 	printf("%d ",a[0]); 
 	printf("%d ",a[1]); 
 	for(i = 2;i < 13;i++) 
 	{ 
 		a[i] = a[i-1] + a[i-2]; 
 		printf("%d ",a[i]); 
 	} 
 	printf("\n");
 	
 	printf("递归显示斐波那契数列：\n");
 	for(i = 0;i < 13;i++) 
 		printf("%d ", Fbi(i)); 
 return 0;
 }

运行结果：  
      ![在这里插入图片描述][2019022513072716.png]

## 顺序队列存在假溢出 ##

队列数据结构：

/* 循环队列的顺序存储结构 */
    typedef struct
    { 
    	QElemType data[MAXSIZE];
    	int front;    	/* 头指针 */
    	int rear;		/* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
    }SqQueue;

**队列的入队操作：实际上就是在队尾追加一个元素**，不需要移动任何元素。  
队列的出队操作：每次出队都是队头位置，只需要更改对头指针即可，不需要移动任何元素。  
    ![在这里插入图片描述][20190225145250140.png]  
  假设下标0、1为空，rear尾指针移动到队列外，此时若还有入队操作，显然尾指针不能接着向后移动，否则出现数组越界，但是队列0、1时还空着，这种现象称为假溢出。  
    ![在这里插入图片描述][20190225145629684.png]

## 顺序队列改成循环队列解决假溢出问题 ##

解决假溢出的方法显然就是后面满了尝试从头开始，也就是**头尾相接的顺序存储循环结构**。  
  循环结构需要解决一个重要的问题：如何判断队列已满？**队列满的条件是(rear+1)%QueueSize = front**。例如下图右侧，当rear是1，而front是2,则显然是队列已满。**队列是空的标志：Q.front=Q.rear，要执行清空队列操作也是Q->front=Q->rear=0;即可**。  
    ![在这里插入图片描述][20190225150956455.png]  
循环队列的初始化、入队、出队示例代码如下：

#include "stdio.h" 
 	#include "stdlib.h" 
 	#include "io.h" 
 	#include "math.h" 
 	#include "time.h"
 	
 	#define OK 1
 	#define ERROR 0
 	#define TRUE 1
 	#define FALSE 0
 	#define MAXSIZE 10 /* 存储空间初始分配量 */
 	
 	typedef int Status; 
 	typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
 	
 	/* 循环队列的顺序存储结构 */
 	typedef struct
 	{ 
 		QElemType data[MAXSIZE];
 		int front; 	/* 头指针 */
 		int rear;		/* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
 	}SqQueue;
 	
 	Status visit(QElemType c)
 	{ 
 		printf("%d ",c);
 		return OK;
 	}
 	
 	/* 初始化一个空队列Q */
 	Status InitQueue(SqQueue *Q)
 	{ 
 		Q->front=0;
 		Q->rear=0;
 		return OK;
 	}
 	
 	/* 将Q清为空队列 */
 	Status ClearQueue(SqQueue *Q)
 	{ 
 		Q->front=Q->rear=0;
 		return OK;
 	}
 	
 	/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
 	Status QueueEmpty(SqQueue Q)
 	{ 
 		if(Q.front==Q.rear) /* 队列空的标志 */
 			return TRUE;
 		else
 			return FALSE;
 	}
 	
 	/* 返回Q的元素个数，也就是队列的当前长度 */
 	int QueueLength(SqQueue Q)
 	{ 
 		return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
 	}
 	
 	/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
 	Status GetHead(SqQueue Q,QElemType *e)
 	{ 
 		if(Q.front==Q.rear) /* 队列空 */
 			return ERROR;
 		*e=Q.data[Q.front];
 		return OK;
 	}
 	
 	/* 若队列未满，则插入元素e为Q新的队尾元素 */
 	Status EnQueue(SqQueue *Q,QElemType e)
 	{ 
 		if ((Q->rear+1)%MAXSIZE == Q->front)	/* 队列满的判断 */
 			return ERROR;
 		Q->data[Q->rear]=e;			/* 将元素e赋值给队尾 */
 		Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */
 									/* 若到最后则转到数组头部 */
 		return OK;
 	}
 	
 	/* 若队列不空，则删除Q中队头元素，用e返回其值 */
 	Status DeQueue(SqQueue *Q,QElemType *e)
 	{ 
 		if (Q->front == Q->rear)			/* 队列空的判断 */
 			return ERROR;
 		*e=Q->data[Q->front];				/* 将队头元素赋值给e */
 		Q->front=(Q->front+1)%MAXSIZE;	/* front指针向后移一位置， */
 										/* 若到最后则转到数组头部 */
 		return OK;
 	}
 	
 	/* 从队头到队尾依次对队列Q中每个元素输出 */
 	Status QueueTraverse(SqQueue Q)
 	{ 
 		int i;
 		i=Q.front;
 		while((i+Q.front)!=Q.rear)
 		{ 
 			visit(Q.data[i]);
 			i=(i+1)%MAXSIZE;
 		}
 		printf("\n");
 		return OK;
 	}
 	
 	int main()
 	{ 
 		Status j;
 		int i=0,l;
 		QElemType d;
 		SqQueue Q;
 		InitQueue(&Q);
 		printf("初始化队列后，队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
 	
 		printf("请输入整型队列元素(不超过%d个),-1为提前结束符: ",MAXSIZE-1);
 		do
 		{ 
 			/* scanf("%d",&d); */
 			d=i+100;
 			if(d==-1)
 				break;
 			i++;
 			EnQueue(&Q,d);
 		}while(i<MAXSIZE-1);
 	
 		printf("队列长度为: %d\n",QueueLength(Q));
 		printf("现在队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
 		printf("连续%d次由队头删除元素,队尾插入元素:\n",MAXSIZE);
 		for(l=1;l<=MAXSIZE;l++)
 		{ 
 			DeQueue(&Q,&d);
 			printf("删除的元素是%d,插入的元素:%d \n",d,l+1000);
 			/* scanf("%d",&d); */
 			d=l+1000;
 			EnQueue(&Q,d);
 		}
 		l=QueueLength(Q);
 	
 		printf("现在队列中的元素为: \n");
 		QueueTraverse(Q);
 		printf("共向队尾插入了%d个元素\n",i+MAXSIZE);
 		if(l-2>0)
 			printf("现在由队头删除%d个元素:\n",l-2);
 		while(QueueLength(Q)>2)
 		{ 
 			DeQueue(&Q,&d);
 			printf("删除的元素值为%d\n",d);
 		}
 	
 		j=GetHead(Q,&d);
 		if(j)
 			printf("现在队头元素为: %d\n",d);
 		ClearQueue(&Q);
 		printf("清空队列后, 队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
 		return 0;
 	}

运行结果：  
      ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]

## 链式存储队列 ##

链式队列数据结构：

typedef struct QNode	/* 结点结构 */
    { 
       QElemType data;
       struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct			/* 队列的链表结构 */
    { 
       QueuePtr front,rear; /* 队头、队尾指针 */
    }LinkQueue;

链式队列入队、出队与链表入队、出队类似，但是加了队列的头和尾，无疑比链表好用。

#include "stdio.h"    
    	#include "stdlib.h"   
    	#include "io.h"  
    	#include "math.h"  
    	#include "time.h"
    	
    	#define OK 1
    	#define ERROR 0
    	#define TRUE 1
    	#define FALSE 0
    	#define MAXSIZE 20 /* 存储空间初始分配量 */
    	
    	typedef int Status; 	
    	typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */	
    	typedef struct QNode	/* 结点结构 */
    	{ 
    	   QElemType data;
    	   struct QNode *next;
    	}QNode,*QueuePtr;
    	
    	typedef struct			/* 队列的链表结构 */
    	{ 
    	   QueuePtr front,rear; /* 队头、队尾指针 */
    	}LinkQueue;
    	
    	Status visit(QElemType c)
    	{ 
    		printf("%d ",c);
    		return OK;
    	}
    	
    	/* 构造一个空队列Q */
    	Status InitQueue(LinkQueue *Q)
    	{  
    		Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    		if(!Q->front)
    			exit(OVERFLOW);
    		Q->front->next=NULL;
    		return OK;
    	}
    	
    	/* 销毁队列Q */
    	Status DestroyQueue(LinkQueue *Q)
    	{ 
    		while(Q->front)
    		{ 
    			 Q->rear=Q->front->next;
    			 free(Q->front);
    			 Q->front=Q->rear;
    		}
    		return OK;
    	}
    	
    	/* 将Q清为空队列 */
    	Status ClearQueue(LinkQueue *Q)
    	{ 
    		QueuePtr p,q;
    		Q->rear=Q->front;
    		p=Q->front->next;
    		Q->front->next=NULL;
    		while(p)
    		{ 
    			 q=p;
    			 p=p->next;
    			 free(q);
    		}
    		return OK;
    	}
    	
    	/* 若Q为空队列,则返回TRUE,否则返回FALSE */
    	Status QueueEmpty(LinkQueue Q)
    	{  
    		if(Q.front==Q.rear)
    			return TRUE;
    		else
    			return FALSE;
    	}
    	
    	/* 求队列的长度 */
    	int QueueLength(LinkQueue Q)
    	{  
    		int i=0;
    		QueuePtr p;
    		p=Q.front;
    		while(Q.rear!=p)
    		{ 
    			 i++;
    			 p=p->next;
    		}
    		return i;
    	}
    	
    	/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
    	Status GetHead(LinkQueue Q,QElemType *e)
    	{  
    		QueuePtr p;
    		if(Q.front==Q.rear)
    			return ERROR;
    		p=Q.front->next;
    		*e=p->data;
    		return OK;
    	}
    	
    	/* 插入元素e为Q的新的队尾元素 */
    	Status EnQueue(LinkQueue *Q,QElemType e)
    	{  
    		QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    		if(!s) /* 存储分配失败 */
    			exit(OVERFLOW);
    		s->data=e;
    		s->next=NULL;
    		Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
    		Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */
    		return OK;
    	}
    	
    	/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
    	Status DeQueue(LinkQueue *Q,QElemType *e)
    	{ 
    		QueuePtr p;
    		if(Q->front==Q->rear)
    			return ERROR;
    		p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */
    		*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
    		Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
    		if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
    			Q->rear=Q->front;
    		free(p);
    		return OK;
    	}	
    	/* 从队头到队尾依次对队列Q中每个元素输出 */
    	Status QueueTraverse(LinkQueue Q)
    	{ 
    		QueuePtr p;
    		p=Q.front->next;
    		while(p)
    		{ 
    			 visit(p->data);
    			 p=p->next;
    		}
    		printf("\n");
    		return OK;
    	}
    	
    	int main()
    	{ 
    		int i;
    		QElemType d;
    		LinkQueue q;
    		i=InitQueue(&q);
    		if(i)
    			printf("成功地构造了一个空队列!\n");
    		printf("是否空队列？%d(1:空 0:否) ",QueueEmpty(q));
    		printf("队列的长度为%d\n",QueueLength(q));
    		EnQueue(&q,-5);
    		EnQueue(&q,5);
    		EnQueue(&q,10);
    		printf("插入3个元素(-5,5,10)后,队列的长度为%d\n",QueueLength(q));
    		printf("是否空队列？%d(1:空 0:否) ",QueueEmpty(q));
    		printf("队列的元素依次为：");
    		QueueTraverse(q);
    		i=GetHead(q,&d);
    		if(i==OK)
    		 printf("队头元素是：%d\n",d);
    		DeQueue(&q,&d);
    		printf("删除了队头元素%d\n",d);
    		i=GetHead(q,&d);
    		if(i==OK)
    			printf("新的队头元素是：%d\n",d);
    		ClearQueue(&q);
    		printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);
    		DestroyQueue(&q);
    		printf("销毁队列后,q.front=%u q.rear=%u\n",q.front, q.rear);
    		return 0;
    	}

运行结果:  
        ![在这里插入图片描述][20190225153505791.png]

## 顺序线性表、链表、静态链 表、顺序栈、两栈共享空间、循环队列、链式队列比较 ##

<table> 
 <thead> 
 <tr> 
 <th></th> 
 <th>数据结构</th> 
 <th>某个位置数据插入</th> 
 <th>某个位置数据删除</th> 
 <th>特点</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>顺序线性表</td> 
 <td> typedef struct {   ElemType data[MAXSIZE];    int length; }SqList; </td> 
 <td>所有插入位置后的数据元素都向后移动1位</td> 
 <td>从删除位置遍历到最后一个元素位置，分别将它们都向前移动一个位置</td> 
 <td>删除插入需要移动大量数据，可以快速存取表中的任一位置</td> 
 </tr> 
 <tr> 
 <td>链表</td> 
 <td> typedef struct Node {   ElemType data;    struct Node *next; }Node; typedef struct Node * LinkList; </td> 
 <td>malloc函数生成新节点s，先遍历寻找需要插入的位置的节点p，s-&gt;next = p-&gt;next;p-&gt;next = s;</td> 
 <td>遍历找到要删除位置的节点p，将p赋值给结点q，p-&gt;next = q-&gt;next;free(q);</td> 
 <td>插入和删除时间复杂度为O(1),不需要提前分配存储空间</td> 
 </tr> 
 <tr> 
 <td>静态链表</td> 
 <td> typedef struct {   ElemType data;    int cur; }StaticLinkList[MAXSIZE]; </td> 
 <td>先遍历找到要插入的位置的节点L[j] ，通过模拟的malloc函数新建节点的游标k，L[j].cur = L[k].cur; L[k].cur = j;</td> 
 <td>遍历找到要删除的位置前一个节点的下标k，j = L[k].cur;L[k].cur = L[j].cur;再将j处节点free;</td> 
 <td>需要手动模拟malloc和free函数，关键在于space[0]中存放备用链表的第一个下标</td> 
 </tr> 
 <tr> 
 <td>顺序栈</td> 
 <td> typedef struct {   SElemType data[MAXSIZE];    int top; }SqStack; </td> 
 <td>例如栈s，s-&gt;top ++;s-&gt;data[s-&gt;top] = 插入元素；</td> 
 <td>top范围等于-1表示栈已空，s-&gt;top – ;</td> 
 <td></td> 
 </tr> 
 <tr> 
 <td>两栈共享空间</td> 
 <td> typedef struct {   SElemType data[MAXSIZE];    int top1;    int top2; }SqDoubleStack; </td> 
 <td>当s-&gt;top1+1 == s-&gt;top表明栈已满。插入时，需要传入参数e是栈1还是栈2，栈1s-&gt;data[++s-&gt;data] = e; 否则s-&gt;data[-- s-&gt;top2] = e;</td> 
 <td>若栈1s-&gt;top1 = -1表明空栈，若栈2 s-&gt;top2 = MAXSIZE,表明栈2是空栈，不删除。若不空，s-&gt;top1 --; 或者s-&gt;top2 ++;</td> 
 <td></td> 
 </tr> 
 <tr> 
 <td>链式栈</td> 
 <td> typedef struct {   SElemType data[MAXSIZE];    struct StackNode*next; }StackNode,*LinkStackPtr;//结点结构 typedef struct {   LinkStackPtr top; int count; }LinkStack;//链表结构中有栈顶结点与栈的大小count</td> 
 <td>往栈S中入栈操作，先动态malloc函数新建节点s，s-&gt;next = s-&gt;top;S-&gt;top = s;S-&gt;count ++;</td> 
 <td>往栈S中出栈操作，p = S-&gt;top;S-&gt;top= S-&gt;top-&gt;next;free§;S-&gt;count --;</td> 
 <td></td> 
 </tr> 
 <tr> 
 <td>循环队列</td> 
 <td> typedef struct {   QElemType data[MAXSIZE];    int front;    int rear; }SqQueue; </td> 
 <td>若队列Q头front和尾rear满足，(Q-&gt;rear+1)%MAXSIZE == Q-&gt;front则队列已满，否则Q-&gt;data[Q-&gt;rear] = e;Q-&gt;rear = (Q-&gt;rear +1)%MAXSIZE;</td> 
 <td>若队列Q头front和尾rear满足，Q-&gt;rear== Q-&gt;front则队列已空，否则Q-&gt;front= (Q-&gt;front+1)%MAXSIZE;</td> 
 <td>循环队列入列或者出列其队列头尾指针移动不是单纯的自增或自减，是需要循环,固定长度相比链式优势之一是使用时不用进行free，同时也是缺点,若可以确定队列最大值情况下，建议使用循环队列，否则使用链队列</td> 
 </tr> 
 <tr> 
 <td>链式队列</td> 
 <td> typedef struct {   QElemType data[MAXSIZE];    struct QNode *next; }QNode ,*QueuePtr;//结点结构 typedef struct {   QueuePtr front,rear; }LinkQueue;//链表结构中有对头 队尾两个结点</td> 
 <td>往队列Q中新增元素，先动态malloc生成新节点s,Q-&gt;rear-&gt;next = s;Q-&gt;rear = s;</td> 
 <td>若队列Q，Q-&gt;front == Q-&gt;rear;则表明队列Q为空。否则，将要删除的结点Q-&gt;front-&gt;next暂存给p，Q-&gt;front-&gt;next = p-&gt;next; free§;注意若Q-&gt;rear = p,表明要删除的是头指针，则Q-&gt;rear = Q-&gt;front;</td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

[20190225102458662.png]: /images/20220317/f647897efc20488c99e9ab48f464ca6a.png
[20190225125053267.png]: /images/20220317/6794c2a07d284a279e67e279b640aaa3.png
[20190225124802601.png]: /images/20220317/1868204818ae44deb01a8a7d96d5cd72.png
[20190225130117381.png]: /images/20220317/060f51fbbfd542f3899b0c509cc90ea3.png
[2019022513072716.png]: /images/20220317/58b3732ea09e4e13996358022610143a.png
[20190225145250140.png]: /images/20220317/f21e5194d6b64f06b7e60c1b437bb172.png
[20190225145629684.png]: /images/20220317/62010d3de842472c850c09dac76f6ba7.png
[20190225150956455.png]: /images/20220317/85b6b62378744b528f6d3b490c002e9e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]: /images/20220317/10dd1024ca964e03a960e5b5fffa7d27.png
[20190225153505791.png]: /images/20220317/04132591a5b14dd0a7fba791a2bbcf35.png