第2章栈与队列2.1知识点概述栈（stack）和队列（queue）是在软件设计中最重要，也是应用最广泛的两种数据结构。从逻辑结构来说，栈和队列都是典型的线性结构，但与线性表不同的是，栈和队列在运算规则上加了一些限制，即仅充许在线性表的一端或两端进行操作。栈所有插入和删除在表的同一端进行，这一端称为栈顶，另一端则称为栈底。如果表中没有元素时称为空栈，通常将插入元素的过程叫做进栈，删除元素的过程叫出栈，栈是按“后进先出”的规则进行操作。栈的主要操作有入栈Push、出栈Pop、读栈GetTop、判栈空IsEmpty等基本操作。队列所有插入在表的一端进行，所有的删除在表的另一端进行。插入的一端为队尾，删除的一端为队头。队列中没有元素时称为空队。通常将元素的插入称入队，元素的删除称出队。队列是按“先进先出”的规则进行操作，队列的主要操作有入队EnQueue、出队DeQueue、读队头元素GetHead、判队空IsEmpty等操作。栈有两种存储表示：顺序表示与链式表示。栈的顺序表示又称为顺序栈，它是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，同时设计一个指针top来指示栈顶元素在顺序栈中的位置。由于栈中元素是动态变化的，入栈时，首先判栈是否满了，如果栈满，不能入栈，否则会导致溢出现象的发生，这种现象称为上溢（overflow）；出栈和读栈顶元素操作时，首先判栈是否为空，为空时不能操作，否则产生错误，这种现象称为下溢（underflow）。在顺序栈中，栈满的条件为：S->top==MAXSIZE-1：栈空条件为S->top==-1。栈的链式存储结构称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结构相同。在实际应用中，更多的是使用顺序栈，例如过程调用和返回、表达式求值等。队列也有顺序表示和链式表示队列的顺序表示是用顺序存储结构来实现的，顺序队列需要分配一组地址连续的存储单元依次存放从队头到队尾的元素，需要事先知道或估算队列的大小。顺序队列也存在溢出问题，队列满时入队会产生上溢，而当队列空时出队则会产生下溢的现象。队列中没有元素时，称为空队列。又因为队头与队尾都是活动的，还需附设两个指针分别指17
17 第 2 章 栈与队列 2.1 知识点概述 栈（stack）和队列（queue）是在软件设计中最重要，也是应用最广泛的两种数据 结构。从逻辑结构来说，栈和队列都是典型的线性结构，但与线性表不同的是，栈和队 列在运算规则上加了一些限制，即仅允许在线性表的一端或两端进行操作。 栈所有插入和删除在表的同一端进行，这一端称为栈顶，另一端则称为栈底。如果 表中没有元素时称为空栈，通常将插入元素的过程叫做进栈，删除元素的过程叫出栈。 栈是按“后进先出”的规则进行操作。栈的主要操作有入栈 Push、出栈 Pop、读栈顶 GetTop、判栈空 IsEmpty 等基本操作。 队列所有插入在表的一端进行，所有的删除在表的另一端进行。插入的一端为队尾， 删除的一端为队头。队列中没有元素时称为空队。通常将元素的插入称入队，元素的删 除称出队。队列是按“先进先出”的规则进行操作，队列的主要操作有入队 EnQueue、 出队 DeQueue、读队头元素 GetHead、判队空 IsEmpty 等操作。 栈有两种存储表示：顺序表示与链式表示。 栈的顺序表示又称为顺序栈，它是利用一组地址连续的存储单元依次存放从栈底到 栈顶的数据元素，同时设计一个指针 top 来指示栈顶元素在顺序栈中的位置。由于栈中 元素是动态变化的，入栈时，首先判栈是否满了，如果栈满，不能入栈，否则会导致溢 出现象的发生，这种现象称为上溢（overflow）；出栈和读栈顶元素操作时，首先判栈 是否为空，为空时不能操作，否则产生错误，这种现象称为下溢（underflow）。在顺 序栈中，栈满的条件为：S -> top = = MAXSIZE-1；栈空条件为 S -> top = = -1。栈 的链式存储结构称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结构相 同。在实际应用中，更多的是使用顺序栈，例如过程调用和返回、表达式求值等。 队列也有顺序表示和链式表示 队列的顺序表示是用顺序存储结构来实现的，顺序队列需要分配一组地址连续的存 储单元依次存放从队头到队尾的元素，需要事先知道或估算队列的大小。顺序队列也存 在溢出问题，队列满时入队会产生上溢，而当队列空时出队则会产生下溢的现象。队列 中没有元素时，称为空队列。又因为队头与队尾都是活动的，还需附设两个指针分别指
向队头元素和队尾元素，即队头指针front与队尾指针rear。用链表表示的队列简称为链队列。用单链表来实现链队列，通常需要一个头指针和尾指针，为了操作方便，给链队列添加一个头结点，并令头指针指向头结点。当头指针和尾指针均指向头结点时链队列为空。入队和出队操作需要修改尾指针和头指针。2.2栈及其应用一、实验目的：1、掌握栈的基本概念2、熟悉栈的表示方法及各种运算3、利用栈编写程序解决实际问题二、实验内容：（一）验证实验1、编写栈的基本操作函数（1）进栈函数push (int *stack,int maxn,int *toppt,int x)（2）出栈函数pop (int *stack,int *toppt,int *cp)（3）输出栈元素outputstack(int*stack，inttoppt）2、调用上述函数实现下列操作，操作步骤如下：（1）调用进栈函数建立一个栈（2）读取栈顶元素（3）从栈中删除元素（4）输出栈中的所有元素注：每完成一个步骤就必须及时输出栈中元素，以便观察操作结果实验程序：#include<stdio.h>//栈顶指针指向栈顶元素#defineMAXN10int push(int *stack,int maxn,int *toppt,int x)[if (*toppt==maxn-1)return l;18
18 向队头元素和队尾元素，即队头指针 front 与队尾指针 rear。用链表表示的队列简称为 链队列。用单链表来实现链队列，通常需要一个头指针和尾指针，为了操作方便，给链 队列添加一个头结点，并令头指针指向头结点。当头指针和尾指针均指向头结点时链队 列为空。入队和出队操作需要修改尾指针和头指针。 2.2 栈及其应用 一、实验目的： 1、掌握栈的基本概念 2、熟悉栈的表示方法及各种运算 3、利用栈编写程序解决实际问题 二、实验内容： （一）验证实验 1、编写栈的基本操作函数 （1）进栈函数 push（int *stack,int maxn,int *toppt,int x） （2）出栈函数 pop (int *stack,int *toppt,int *cp) （3）输出栈元素 outputstack(int *stack,int toppt) 2、调用上述函数实现下列操作，操作步骤如下： （1）调用进栈函数建立一个栈 （2）读取栈顶元素 （3）从栈中删除元素 （4）输出栈中的所有元素 注：每完成一个步骤就必须及时输出栈中元素，以便观察操作结果 实验程序： #include<stdio.h>//栈顶指针指向栈顶元素 #define MAXN 10 int push(int *stack,int maxn,int *toppt,int x) {if(*toppt==maxn-1) return 1;
++(*toppt) ;stack[*toppt]=x;return 0;1intpop(int*stack,int*toppt,int*cp)1if (*toppt==-1)return l;*cp=stack[*toppt];--(*toppt) ;return 0;)void outputstack(int *stack,int toppt)(int i;for(i=toppt;i>=o;i--)printf("%d",stack[i]);printf("(n");)void main()[int s[MAXN],i;int top=-1;int op;while(1)(printf（"请选择操作，1：进栈2：出栈O：退出")；scanf("%d",&op) :switch(op) (case 0:return;case l:printf（"请输入进栈元素："）；scanf("%d",&i);19
19 ++(*toppt); stack[*toppt]=x; return 0; } int pop(int *stack,int *toppt,int *cp) { if(*toppt==-1) return 1; *cp=stack[*toppt]; -(*toppt); return 0;} void outputstack(int *stack,int toppt) {int i; for(i=toppt;i>=0;i-) printf("%d",stack[i]); printf("\n");} void main() {int s[MAXN],i; int top=-1; int op; while(1) {printf("请选择操作，1：进栈 2：出栈 0：退出"); scanf("%d",&op); switch(op){ case 0: return; case 1: printf("请输入进栈元素:"); scanf("%d",&i);
if(push(s,MAXN,&top,i)==0) (printf（"进栈成功，栈内元素为：ln"）；outputstack(s,top);)elseprintf("栈满\n")；break;case 2:if(pop(s,&top,&i)==0)(printf("出栈元素为：[%d]，栈内元素为：|n"，i)；outputstack(s,top):)elseprintf("栈空\n")；break;-111、#include<stdio.h>//栈顶指针指向栈顶元素上一个空位置#define MAXN 10int push(int *stack,int maxn,int *toppt,int x)(if(*toppt>=maxn)return 1;stack[*toppt]=x;++(*toppt);return O;1int pop(int *stack,int *toppt,int *cp)1if(*toppt=-0)return 1;20
20 if(push(s,MAXN,&top,i)==0){ printf("进栈成功，栈内元素为:\n"); outputstack(s,top);} else printf("栈满\n"); break; case 2: if(pop(s,&top,&i)==0){ printf("出栈元素为:[%d],栈内元素为:\n",i); outputstack(s,top);} else printf("栈空\n"); break; } } } 1、#include<stdio.h>//栈顶指针指向栈顶元素上一个空位置 #define MAXN 10 int push(int *stack,int maxn,int *toppt,int x) {if(*toppt>=maxn) return 1; stack[*toppt]=x; ++(*toppt); return 0; } int pop(int *stack,int *toppt,int *cp) { if(*toppt==0) return 1;
--(*toppt);*cp=stack[*toppt];return 0;)void outputstack(int *stack,int toppt)(int i;for(i=toppt-1;i>=0;i--)printf("%d",stack[i];printf("/n");)2、void main()(int s[MAXN],i;int top=0;int op,while(1)(printf("请选择操作，1：进栈2：出栈0：退出");scanf("%d",&op);switch(op)case O:return,case 1:printf("请输入进栈元素：");scanf("%d",&i);if(push(s,MAXN,&top,i)--0)printf("进栈成功，栈内元素为:ln");outputstack(s,top);)elseprintf("栈满\n");break;case 2:if(pop(s,&top,&i)==0)21
21 -(*toppt); *cp=stack[*toppt]; return 0;} void outputstack(int *stack,int toppt) {int i; for(i=toppt-1;i>=0;i-) printf("%d",stack[i]); printf("\n");} 2、void main() {int s[MAXN],i; int top=0; int op; while(1) {printf("请选择操作，1：进栈 2：出栈 0：退出"); scanf("%d",&op); switch(op){ case 0: return; case 1: printf("请输入进栈元素:"); scanf("%d",&i); if(push(s,MAXN,&top,i)==0){ printf("进栈成功，栈内元素为:\n"); outputstack(s,top);} else printf("栈满\n"); break; case 2: if(pop(s,&top,&i)==0){