教学内容栈和队列的定义及特点栈的顺序存储.ppt

《教学内容栈和队列的定义及特点栈的顺序存储.ppt》由会员分享，可在线阅读，更多相关《教学内容栈和队列的定义及特点栈的顺序存储.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、教学内容：一、教学内容：1、栈和队列的定义及特点；2、栈的顺序存储表示和链接存储表示；3、队列的顺序存储表示；队列的链接存储表示；4、栈和队列的应用举例。第3章 栈和队列 二、教学要求：二、教学要求：了解递归的概念和递归过程的实现；掌握栈和队列的定义、表示、实现和应用；掌握栈的顺序存储结构和链式存储结构以及相应操作的实现；掌握队列的顺序存储结构（循环队列）和链式存储结构的实现；熟练掌握链式栈和顺序队列的操作算法。目录 3.1 栈 3.1.1 栈的定义 3.1.2 顺序栈的表示与实现 3.1.3 链式栈的表示与实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.4 迷宫求解 3.2.5

2、 表达式求值*3.3 栈和递归的实现 3.4 队列 抽象数据类型队列的定义 3.4.2 链队列-队列的链式表示与实现 3.4.3 循环队列-队列的顺序表示与实现本章小结3.1 栈（栈（stack）3.1.1 栈的定义：限定仅在表尾进行插入或删除操作的线性表.栈顶（栈顶（top）:线性表的表尾端，即可操作端。栈底（栈底（base）:线性表的表头。特点：特点：先进后出（FILO）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)3.1.2 栈的顺序存储结构顺序栈实现：一维数组sMbase=0123450栈空栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top12

3、3450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空top=0base=0base=0栈的抽象数据类型定义ADT Stack 数据对象数据对象：D=ai|ai属于ElemSet,(i=1,2,n,n0)数数据据关关系系：R1=ai-1,ai|ai-1,ai属于D,(i=2,3,n)约定an为栈顶,a1为栈底。基本操作基本操作：InitStack(&S);/置空栈置空栈 Dest

4、royStack(&S);/销毁栈销毁栈 ClearStack(&S);/清清空空栈栈 StackEmpty(S);/判判栈栈空空否否 StackLength(S);/求栈长度求栈长度 GetTop(S,&e);/取栈顶取栈顶 Push(&S,e);/进栈进栈 Pop(&S,&e);/出栈出栈 StackTraverse(S,visit()ADT Stack栈的顺序存储结构(顺序栈)表示:#define STACK_INIT_SIZE 100；#define STACKINCREMENT 10；typedef char SElemType;typedef struct /顺序栈定义顺序栈定义

5、SElemType*base;/栈底指针栈底指针 SElemType*top;/栈顶指针栈顶指针int stacksize；/当前已分配的全部存储空间当前已分配的全部存储空间 SqStack；顺序栈的基本运算:顺序栈的基本操作初始化初始化压栈压栈出栈出栈清空栈清空栈判判栈是否为空栈是否为空判判栈是否为满栈是否为满取栈顶元素取栈顶元素多个栈的共享空间多个栈的共享空间分分析析：初始化就是建立一个空栈，栈中不含任何元素，此时栈顶指针top为0，表示栈空。示示意意图图*base*topstacksize*top=*base;stacksize=STACK_INIT_SIZEvoid InitStack

6、(SqStack&S)/置空栈置空栈 S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/存储分配失败存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;实实现现算算法法v算法：InitStack（S）初始化：）初始化：分分析析：进栈需要判判断断是是否否会会出出现现“溢溢出出”，若栈不满，则元素进栈时，栈顶指针做加一操作，元素进栈栈顶指针做加一操作，元素进栈。实现算法：实现算法：void Push(SqStack&S,SElemT

7、ype e)/插入元素插入元素e为为新的新的栈顶栈顶元素元素 if(S.top-S.base=S.stacksize)/栈满栈满，追加存，追加存储储空空间间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/存存储储分配失分配失败败 S.top=S.base+S.stacksize;/重新置栈顶指针重新置栈顶指针 S.stacksize+=STACK_INCREMENT;*(S.top)+=e;v算法：Push(&S，e）压栈压

8、栈e*base*topstacksize.a1.aians*base*topstacksize.a1.aians栈满时，追加存储空间*(s.top+)=e;*(s.top+)=e;元素入栈示意图元素入栈示意图分分析析：如果顺序栈不为空，此时执行出栈操作，栈顶指针做减一操作，指向原栈顶的后继元素。如果对空栈执行出栈操作，应提示错误信息并终止程序运行。实现算法：实现算法：Status Pop(SqStack&S,SElemType&e)/若若栈栈不不空空，则则删删除除S的的栈栈顶顶元元素素，用用e返返回回其其值值，并并返回返回OK；否；否则则返回返回ERROR if(S.top=S.base)re

9、turn ERROR;e=*-S.top;return OK;v算法：Pop（&S，&e）出栈出栈栈空,下溢分分析析：清空栈，就是把一个栈置成空栈。即不论数组中是否存有数据，只要将栈顶指针top指向栈底处，就表示栈空。实现算法实现算法：void ClearStack(SqStack&S)/把S置为空栈 S.top=S.base;v算法：ClearStack(&S)清空栈清空栈分析：通过判断栈顶指针来判断栈是否为空。栈栈顶指针顶指针top与栈底指针与栈底指针base指向相同，表示栈为空，指向相同，表示栈为空，返回返回TRUE；否则返回否则返回FALSE。实现算法：Status StackEmpt

10、y(SqStack S)/若栈若栈S为空栈，则返回为空栈，则返回TRUE，否则返回否则返回FALSE if(S.top=S.base)return TRUE;else return FALSE;v算法：StackEmpty（&s)判判栈是否为空栈是否为空分析：分析：通过判断栈顶指针与栈底指针之间的元素个数是否达到了最大容量判断栈是否为满。栈为满，返回栈为满，返回TRUE；否则返回否则返回FALSE。实现算法：实现算法：Status StackFull(SqStack S)if(S.top-S.base=S.StackSize)return TRUE;/判栈满判栈满else return FAL

11、SE;v算法：StackFull（s)判判栈是否为满栈是否为满分析：分析：栈顶指针直接指向栈顶元素。需要注意空空栈栈的情况。实现算法：实现算法：Status GetTop(SqStack S,SElemType&e)/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(StackEmpty(S)return ERROR;/or if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;v算法：GetTopGetTop（s,&e)s,&e)取栈顶元素取栈顶元素结论：结论：顺序栈的入栈和出栈操作，实际上对应的是顺序表的表尾插入和表尾

12、删除操作。所以入栈和出栈操作的时间复杂度都为O（1）。顺序栈的操作演示顺序栈的操作演示实例：栈使用的完整C程序实例Q1:对于一个栈，给出输入项对于一个栈，给出输入项A、B、C，如果输入，如果输入项序列由项序列由ABC组成，试给出所有可能的输出序列组成，试给出所有可能的输出序列,能否产生能否产生CAB输出序列输出序列。Q2:如果一个栈的输入序列为如果一个栈的输入序列为123456，能否得到，能否得到435612和和135426的出栈序列？的出栈序列？栈的共享存储单元栈的共享存储单元(可选可选)问问题题:有时，在一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢

13、出，而另一个栈空间过大，造成大量存储单元浪费的现象。解解决决方方法法:为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。两个共享存储单元顺序栈的操作演示两个共享存储单元顺序栈的操作演示base1top1top2base2实例实例:在在程序中定义两个栈程序中定义两个栈（1）定义共享栈数据结构#define MAX 100int stackMAX;int top1=base1=0,top2=base2=MAX-1;base1top1top2base2栈1的操作:入栈top1执行加1的操作;出栈top1执行减1的操作;栈2

14、的操作:入栈top2执行减1的操作;出栈top2执行加1的操作;栈满条件:top1top2(2)共享进栈算法 void push1(int x)if(top1top2)printf(“overflow”);else stacktop1=x;top1+;void push2(int x)if(top1top2)printf(“overflow”);else stacktop2=x;top2-;(3)共享出栈算法 int pop1()if top1=0)printf(“underflow”);return(NULL);top1-;return(stacktop1);int pop2()if(top

15、2=MAX-1)printf(“underflow”);return(NULL):top2+;return(stacktop2);3.1.3 链栈链栈(可选）可选）定义：栈的链式存储通常用单链表实现单链表实现，此时链表的头指头指针为栈顶指针针为栈顶指针，定义为top，链表第一个结点为栈顶结点第一个结点为栈顶结点。当头指针为NULL时，表示当前栈为空栈。链栈示意图：链栈示意图：特点：特点：链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作栈的链接存储结构定义：typedef struct node ElemType data;struct node*nex

16、t;LNode,*LinkStack;分分析析：链式存储时，空空栈栈即即为为空空单单链链表表，其栈顶指针值为NULL。实现算法：实现算法：void InitStack(LinkStack&s)s=(LNode*)malloc(sizeof(LNode);s-next=NULL;注意：空单链表是带表头结点的空单链表。注意：空单链表是带表头结点的空单链表。v算法：InitStack(S)初始化初始化分析：分析：链栈的入栈操作就是单链表的表头插入单链表的表头插入。实现算法：实现算法：LinkStack*PushLStack(LinkStack*top,ElemType x)LinkStack*p;p

17、(LinkStack*)malloc(sizeof(LinkStack);p-datax;p-nexttop;return p;v算法：PushLStack(S)链栈的进栈算法链栈的进栈算法分析：分析：如果是空栈空栈，提示出错信息并退出；否则，栈顶元素出栈，即删除单链表的第一个结点删除单链表的第一个结点。实现算法：实现算法：linkstack*PopLStack(LinkStack*top,ElemType*datap)LinkStack*p;if(top=NULL)printf(“under flown”);return NULL;else *dataptop-data;ptop;topto

18、p-next;free(p);return top;v算法：PopLStack（S）链栈的出栈算法链栈的出栈算法分分析析：如果是空空栈栈，提示出错信息并退出；否则，返回单链表的第一个结点的值返回单链表的第一个结点的值。实现算法：实现算法：（略）v算法：GetTop(S)取栈顶的元素取栈顶的元素v算法：StackEmpty(S)判栈是否为空判栈是否为空分析：分析：通过判断判断toptop的值的值来判断链栈的状态实现算法：实现算法：（略）分析：分析：清空链栈，要释放链表中的所有结点要释放链表中的所有结点。实现算法：实现算法：（略）v算法：ClearStack(S)清空栈清空栈 3.2 栈的应用举例

19、栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。数制转换数制转换(*)行编辑程序行编辑程序迷宫求解迷宫求解表达式求值表达式求值 Hanoi塔问题塔问题例1：栈的应用举例-数制转换(讲述讲述)十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(n div d)*d+n mod d (其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计计算算顺

20、顺序序输输出出顺顺序序 void conversion()/算法3.1/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 ElemType e;SqStack s;int n;InitStack(s);scanf(“%d”,&n);while(n)Push(s,n%8);n=n/8;while(!StackEmpty(s)Pop(s,e);printf(“%d”,e);v算法：1010进制进制-8-8进制转换进制转换.while(n)Push(s,n%16);n=n/16;v算法：1010进制进制-16-16进制转换进制转换十进制转化为任意进制的实例例例2 2：行编辑程序：行编辑程

21、序在用户输入一行的过程中，允许在用户输入一行的过程中，允许 用户输入出差错，用户输入出差错，并在发现有误时可以及时更正。并在发现有误时可以及时更正。设立一个输入缓冲区，用以接受用户输入的一行字设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区符，然后逐行存入用户数据区;并假设并假设“#”#”为退格符为退格符，“”为退行符为退行符。假设从终端接受两行字符：假设从终端接受两行字符：whli#ilr#ewhli#ilr#e（s#*s)s#*s)outchaputchar(*s=#+);outchaputchar(*s=#+);实际有效行为：实际有效行为：while(*s)whil

22、e(*s)putchar(*s+);putchar(*s+);void LineEdit()InitStack(s);ch=getchar();while(ch!=EOF)/EOF为全文结束符为全文结束符while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,ch);break;case:ClearStack(S);break;/重置重置S为空栈为空栈 default:Push(S,ch);break;ch=getchar();/从终端接收下一个字符从终端接收下一个字符/while将从栈底到栈顶的字符传送至调用过程的数据区；将从栈底到栈顶的字符传送至调用过程的数据区

23、；ClearStack(S);/重置重置S为空栈为空栈if(ch!=EOF)ch=getchar();/whileDestroyStack(s);v算法：例例3：迷宫求解：迷宫求解例例4 4：表达式求值：表达式求值例例5：hanoi塔问题塔问题(讲述讲述)a b ca b c 问题描述：问题描述：传说在创世纪时，在一个叫传说在创世纪时，在一个叫BrahmaBrahma的寺庙里，有三的寺庙里，有三个柱子，其中一柱上有个柱子，其中一柱上有6464个盘子从小到大依次叠放，僧侣的工作个盘子从小到大依次叠放，僧侣的工作是将这是将这6464个盘子从一根柱子移到另一个柱子上。个盘子从一根柱子移到另一个柱子上

24、。移动时的规则：移动时的规则：每次只能移动一个盘子；每次只能移动一个盘子；只能小盘子在大盘子上面；只能小盘子在大盘子上面；可以使用任一柱子。可以使用任一柱子。当工作做完之后，就标志着世界末日到来。当工作做完之后，就标志着世界末日到来。l解决方法：ln=1时，直接把圆盘从A移到Cln1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题 hanoi塔的递归算法void hanoi (int n,char a,char b,char c )/将将

25、 n 个个 编号从上到下为编号从上到下为 1n 的盘子从的盘子从 a 柱，借助柱，借助 b 柱移到柱移到 c 柱柱 if(n =1 )move(a,1,c );/将编号为将编号为 1 的的盘子盘子从从 a 柱移到柱移到 c 柱柱 else /将将 n-1个个 编号从上到下为编号从上到下为1n-1的盘子从的盘子从 a 柱，借助柱，借助 b 柱移到柱移到 c 柱柱 hanoi(n-1,a,c ,b );move(a,n,c);/将编号为将编号为 n 的的盘子盘子从从 a 柱移到柱移到 c 柱柱 /将将 n-1个个 编号从上到下为编号从上到下为 1n-1的盘子从的盘子从 b 柱，借助柱，借助 a 柱

26、移到柱移到 c 柱柱 hanoi(n-1,b,a,c);/hanoiv算法：hanoi塔塔3.4 队列队列定义队列定义队列的特点队列的特点队列的队列的ADTADT表示表示链式队列链式队列链式队列的基本操作链式队列的基本操作循环队列（顺序队列）循环队列（顺序队列）队列的定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列的特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)双端队列a1 a2 a3.an 端1端2入队出队入队出队队列的抽象数据类型定义：ADT Qu

27、eue ADT Queue 数数 据据 对对 象象：D=ai|ai属 于 Elemset,(i=1,2,n,n0)数数 据据 关关 系系：R1=ai-1,ai|ai-1,ai属 于D,(i=2,3,n)约定an为队尾,a1为队头。基本操作基本操作：InitQueue(&Q);DestroyQueue(&Q);ClearQueue(&Q);QueueEmpty(Q);QueueLength(Q);GetHead(Q,&e);EnQueue(&Q,e);DeQueue(&Q,&e);QueueTraverse(Q,visit()ADT Queue链队列链队列 队列的链式存储结构队列的链式存储结构简

28、称为链队列链队列，它是限限制仅在表头删除和表尾插入的单链表制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。typedef struct QueuePtr front;QueuePtr rear;LinkQueue;链队列的存储结构定义：链队列的存储结构定义：typedef struct QNode ElemType data;struct QNode*next;QNode,*QueuePtr;null*qq.frontq.rear非空队列非空队列空队列空队列q.frontq.

29、rearnull*q链队列示意图：链队列示意图：链队列中，有两个分别指示队头和队尾的指针。链队列中，有两个分别指示队头和队尾的指针。链式队列在进队时无队满问题，但有队空问题。链式队列在进队时无队满问题，但有队空问题。链式队列的基本操作构造一个空队列判队列是否为空取队头元素入队出队算法实现：算法实现：Status InitQueue(LinkQueue&Q)/构造一个空队列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)exit(OVERFLOW);Q.front-next=NULL;return OK;v算法：构造一个空队列置队空示意图q

30、.frontq.rearnull*q算法实现：算法实现：Status QueueEmpty(LinkQueue Q)/若若Q为空队列，则返回为空队列，则返回TRUE，否则返回否则返回FALSE if(Q.front-next=NULL)return TRUE;else return FALSE;v算法：判队列是否为空判队列是否为空算法实现：算法实现：Status GetHead(LinkQueue Q,QElemType&e)/若队列不空，则用若队列不空，则用e返回返回Q的队头元素，并返回的队头元素，并返回OK，否则返回否则返回ERROR QueuePtr p;if(Q.front=Q.rea

31、r)return ERROR;p=Q.front-next;e=p-data;return OK;v算法：取队头元素取队头元素算法实现：算法实现：void EnQueue(LinkQueue&Q,QElemType e)/插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 QueuePtr p;if(!(p=(QueuePtr)malloc(sizeof(QNode)/存储分配存储分配失败失败 exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;v算法：入队入队算法实现：算法实现：Status DeQueue(LinkQueu

32、e&Q,QElemType&e)/若队列不空，删除若队列不空，删除Q的队头元素，用的队头元素，用e返回其值，并返回返回其值，并返回OK，否则返回否则返回ERROR QueuePtr p;if(Q.front=Q.rear)return ERROR;/队空队空 p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;v算法：出队出队非循环队列和循环队列非循环队列和循环队列顺序队列顺序队列队列的顺序存储表示。队列的顺序存储表示。用一组地址连续的存用一组地址连续的存储单元依次存放

33、从队列头到队列尾的元素，指针储单元依次存放从队列头到队列尾的元素，指针front和和rear分别指示队头元素和队尾元素的位置。分别指示队头元素和队尾元素的位置。插入新的队尾元素，尾指针增插入新的队尾元素，尾指针增1，rear=rear+1，删除队头元素，头指针增删除队头元素，头指针增1，front=front+1，因此，在非空队列中，头指针始终指向队列头元素，而因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的尾指针始终指向队列尾元素的下一个位置下一个位置。队满时再进队将溢出队满时再进队将溢出 解决办法：将顺序队列臆造为一个环状的空间，形成解决办法：将顺序队列臆造为一个

34、环状的空间，形成循环循环(环形环形)队列队列队列的顺序存储结构定义：队列的顺序存储结构定义：#define MAXQSIZE 100typedef struct /ElemType dataMAXQSIZE;/静态分配 ElemType *base;/动态分配 int front;int rear;SqQueue;顺序队列的操作演示顺序队列的操作演示队列的进队和出队示例：队列的进队和出队示例：frontrear空队列空队列frontrearA,B,C,D进队进队A B C DfrontrearA,B出队出队C DfrontrearE,F,G进队进队C D E F GC D E F Gfront

35、rearH进队进队,溢出溢出n队空：Q.front=Q.rearn队满：Q.rear=maxsize（假溢出）求队的长度：n 入队：新元素按 rear 指示位置加入，再将队尾指针加一，即 rear=rear+1n 出队：将front指示的元素取出，再将队头指针加一，即front=front+1非循环队列非循环队列设数组维数为M，则：当front=0,rear=M时，再有元素入队发生溢出真溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢假溢出出存在问题存在问题:解决方法解决方法:循环队列循环队列(Circular Queue)基本思想：基本思想：把队列设想成环形队头、队尾指针队

36、头、队尾指针加加1 1，可用取模，可用取模(余数余数)运算实现。运算实现。队头指针进队头指针进1:front=(front+1)%maxsize;1:front=(front+1)%maxsize;队尾指针进队尾指针进1:rear=(rear+1)%maxsize;1:rear=(rear+1)%maxsize;队列初始化队列初始化：front=rear=0;front=rear=0;队空条件队空条件：front=rear;front=rear;队满条件：队满条件：(rear+1)%maxsize=front;(rear+1)%maxsize=front;01234567循环队列循环队列fro

37、ntrearMaxsize-101234567frontBCDrear一般情况一般情况AC01234567队满队满frontrearDEFGABCH01234567rear空队列空队列frontC01234567队满队满(正确正确-与队空区别与队空区别)frontrearDEFGABC#define MAXSIZE 100Typedef structQElemType*base;int front;int rear;SqQueue;循环队列的类型定义循环队列的类型定义算法实现：算法实现：Status EnQueue(SqQueue&Q,ElemType e)if(Q.rear+1)%MAXQS

38、IZE=Q.front)return(ERROR);Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return(OK);v算法：入队入队分析分析:（1）检查队列是否已满，若队满，则进行溢出错误处理；（2）将新元素赋给队尾指针所指单元；（3）将队尾指针后移一个位置（即加1），指向下一单元。算法实现：算法实现：Status DeQueue(SqQueue&Q,ElemType&e)if(Q.rear=Q.front)return(ERROR);e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return(OK);v算法

39、：出队出队分析分析:（1）检查队列是否为空，若队空，则进行下溢错误处理；（2）取队首元素的值。（3）将队首指针后移一个位置（即加1）；本章小结本章小结线性表、栈与队的异同点线性表、栈与队的异同点相相同同点点：逻逻辑辑结结构构相相同同，都都是是线线性性的的；都都可可以以用用顺顺序序存存储储或或链链表表存存储储；栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表，即即受受限限的的线性表线性表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。不同点：不同点：运运算算规规则则不不同同，线线性性表表为为随随机机存存取取，而而栈栈是是只只允允许许在在一一端端进进行行插插入入和和删删除除运运算算，因因而而是是后后进进先先出出表表LIFOLIFO；队队列列是是只只允允许许在在一一端端进进行行插插入入、另另一一端端进进行行删删除除运运算算，因因而而是先进先出表是先进先出表FIFOFIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。和简化设计等。实验3：栈和队列的定义及基本操作(必做2学时）实验4：栈和队列的综合应用(选做2学时）