文章目录

前言

一、栈

1、栈的基本概念

2、栈的抽象数据类型描述

3、顺序栈的表示与实现

（1）顺序栈——顺序存储结构的栈。

（2）顺序栈的存储结构

（3）顺序栈的操作实现（以动态分配为例）

4、链栈的表示与实现

5、练习

二、栈的应用举例

1、数制转换——除留余数法

2、括号匹配的检验

3、行编辑程序问题

4、迷宫求解（内容较多且不好理解，有兴趣的看教材P50-52）

5、表达式求值

三、栈与递归

1、递归的定义

2、递归定义的数学函数

 3、具有递归特性的数据结构

4、可递归求解的问题——迷宫问题、Hanoi塔问题

5、用分治法求解递归问题

6、用C语言实现汉诺塔

7.递归与迭代

四、队列

1、队列的类型定义

2、链队列

（1）存储结构定义

 （2）队列运算指针变化状况

 （3）链队列初始化

（4）销毁链队列

（5）判断链队列是否为空

（6）求链队列的队头元素

（7）链队列入队

（8）链队列出列

3、循环队列——队列的顺序表示与实现

（1）顺序存储结构定义

 （2）循环队列的存储结构

（3）初始化

（4）求循环队列的长度

（5）循环队列入队

（6）循环队列出队

 （7）练习

总结

---

前言

本文主要介绍数据结构（C语言版）第三章栈和队列内容，主要包括栈的相关定义域操作、栈的应用举例、栈与递归以及队列。

其中重点在于栈与队列的基本操作实现算法，难点在于栈的应用举例以及栈的递归。

---

一、栈

1、栈的基本概念

（1）定义——限定只能在表的一端（栈顶）（表尾）进行插入和删除运算的线性表。

表尾即an端称为栈顶/top；表头即a1端称为栈底/base；a1称为栈底元素，an称为栈顶元素。
（2）逻辑结构——与线性表相同，仍为一对一关系
（3）存储结构——用顺序栈或链栈存储均可，但以顺序栈更常见
（4）运算规则——只能在栈顶运算，且访问结点时依照后进先出( LIFO ）或先进后出( FILO ）的原则
（5）实现方式——关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等。（插入元素到栈顶的操作叫做入栈；从栈顶删除最后一个元素的操作叫做出栈）
（6）栈上溢——在栈满时还进行入栈运算，必定会产生空间的溢出。
（7）栈下溢——当栈空时仍进行出栈运算，必定会产生空间的溢出。
（8）栈与一般线性表的不同——仅在于运算规则不同。
一般线性表的运算规则——随机存取；栈的运算规则：后进先出。

2、栈的抽象数据类型描述

ADT Stack {
数据对象：
D ={ai|ai∈ElemSet,i=1,2…,n,n≥0}
数据关系：
R1=}|ai-1,ai∈D,i=2,…,n}
约定an端为栈顶,a1端为栈底。
基本操作：
 InitStack(&S)//建立一个空栈
 StackLength(S)//求栈长
 DestroyStack(&S)//销毁栈
 StackEmpty(S)//判断栈空
 Getop(S,&e)//取栈顶元素
 ClearStack(&S)//清空栈
 Push(&S,e)//入栈
 Pop(&S,&e)//出栈
 StackTravers(S,visit())//遍历
} ADT Stack 

3、顺序栈的表示与实现

（1）顺序栈——顺序存储结构的栈。

（2）顺序栈的存储结构

它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针 top 指示栈顶元素的当前位置。

●top 指示真正的栈顶元素之上的下标地址

●栈满时的处理方法：
①报错，返回操作系统。
②分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。

●入栈口诀——堆栈指针 top “先压后加”：S [ top ++]= an 

●出栈口诀——堆栈指针 top “先减后弹”: e = S [-- top ]

●栈不存在的条件—— base == NULL ;

●栈为空的条件——base == top ;

●栈满的条件—— top - base == MaxSize ;

（3）顺序栈的操作实现（以动态分配为例）

①顺序存储结构表示

动态分配存储空间（当栈满时可以申请新的存储空间，将原栈的内容移入新栈）

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10;
typedef struct {
   SElemType *base;//构造之前和销毁之后,base的值为NULL
   SElemType *top;//栈顶指针
   int stacksize ;//当前已分配的存储空间以元素为单位
}SqStack;//类型名

 静态分配存储空间

#define Stack_Size 50
typedef struct{
    SElemType data[Stack_Size];//定义最大空间的一维数组存储数据
    SElemType *top;//栈顶指针
}SqStack;

静态分配与动态分配间最大的差别一个是空间能否在操作中增加，一个是是否需要base指针。

②顺序栈初始化

●步骤：
(1）分配空间并检查空间是否分配失败，若失败则返回错误。
(2）设置栈底和栈顶指针S.top=S.base ;
(3）设置栈大小。

具体算法描述如下：

 void InitStack(SqStack &S)
｛//构造一个空栈S
    S.base =(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(S.base) 
      exit (-1); //存储分配失败 
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE; 
}

③判断栈是否为空

//bool是布尔型变量，布尔型变量的值只有真（true）和假（false）
bool StackEmpty(SqStack S)
{
   if(S.top==S.base) 
       return true; 
   else
       return false ;
}

④求顺序栈的长度

int StackLength(SqStack S)
{
  return S.top-S.base;
}

⑤清空顺序栈

int ClearStack(SqStack S) 
{
   if(S.base) //栈不空
      S.top=S.base;
   return 1;
} 

⑥销毁顺序栈

 int DestroyStack(SqStack &S)
{
   if(S.base)
   {
      free(S.base);
      S.stacksize=0;
      S.base=S.top=NULL;
   }
   return 1;
}

⑦顺序栈进栈（入栈）

(1）判断是否栈满，若满则出错   (2）元素 e 压入栈顶   (3）栈顶指针加1
 

 int Push(SqStack &S,SElemType e) 
{
  if(S.top-S.base==S.stacksize)//栈满 
      return 0;
  *S.top++=e;//等价于*S.top=e; S.top++;
  return 1;
}

⑧顺序栈出栈
(1）判断是否栈空，若空则出错  (2）获取栈顶元素 e  (3）栈顶指针减1

 int Pop(SqStack &S,SElemType &e)
{
  if(S.top==S.base)//栈空 
      return 0;
  e=*--S.top;//等价于--S.top; e=*S.top;
  return 1;
}

⑨取顺序栈栈顶元素

Status GetTop(SqStack S,SElemType &e)
{
  if(S.top=S.base)//栈空
     return 0;
  e=*(S.top-1);
  return 1;
}

4、链栈的表示与实现

运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针。

①链式存储结构表示

typedef struct StackNode{
 SElemType data;//数据域
 struct StackNode *next;//指针域
}StackNode,*LinkStack;
LinkStack S;

 ②链栈的初始化

void InitStack(LinkStack &S)
{ S=NULL;}

③判断链栈是否为空

int StackEmpty(LinkStack S)
{
  if(S==NULL)
     return 1; 
  else 
     return 0;
}

④链栈进栈

int Push(LinkStack &S,SElemType e)
{
   p=(StackNode*)malloc(sizeof(StackNode)));//生成新结点p 
   if(p) //存储空间申请失败
     exit(-1); 
   p->data=e;//入栈
   p->next=S; 
   S=p; 
   return 1;
}

⑤链栈出栈

int Push(LinkStack &S,SElemType e)
{
  p=(StackNode*)malloc(sizeof(StackNode)));//生成新结点 p 
  if(p) 
    exit(-1); 
  p->data=e; 
  p->next=S; 
  S=p;  
  return 1;
}

⑥几点说明

●在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，可不设头结点链栈。
●一般不会出现栈满情况；除非没有空间导致 maloc 分配失败。
●链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。
●采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。

5、练习

二、栈的应用举例

1、数制转换——除留余数法

除留余数法基于下列原理，将十进制整数 N 转换为 d 进制数： N =( N div d ) *d + N mod d 
其中： div 为整除运算，mod 为求余运算

 算法步骤：

①初始化一个空栈 S 。                                                                                                                  ②当十进制数 N 非零时，循环执行以下操作：●把 N 与8求余得到的八进制数压入栈 S ;● N 更新为 N 与8的商。
③当栈 S 非空时，循环执行以下操作：●弹出栈顶元素 e ; ●输出 e 。

具体算法：

2、括号匹配的检验

●假设在表达式中允许包含两种括号：圆括号的方括号，嵌套顺序任意。
例：[（[][]）]或（[]（））正确
[（]）或（[（））或（（）]）不正确
检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述，恰好与栈的特点吻合。

●例如：考虑下列括号序列：[()([])()]
可用栈来存放并表示待匹配的左括号“期待的急迫程度”
思路：设置一个栈用于存放待匹配的左括号，每次读入一个括号：
●若是左括号，则作为一个新的更急迫的期待压入栈中。
●若是右括号，则或者使位于栈顶的最急迫的期待得以消解，或者是不合法的情况；
●若最后栈不空，则为不合法的情况

 算法步骤：

①初始化一个空栈s。
②设置一标记性变量flag，用来标记匹配结果以控制循环及返回结果，1表示正确匹配，0表示错误匹配，flag初值为1。
③扫描表达式，依次读入字符ch，如果表达式没有扫描完毕或flag非零，则循环执行以下操作：
●若ch是左括号“）”或“（”，则将其压入栈；
●若ch是右括号“）”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“（”，则正确匹配，否则错误匹配，flag置为0；
●若ch是右括号“]”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“I”，则正确匹配，否则错误匹配，flag置为0。
④退出循环后，如果栈空且flag值为1，则匹配成功，返回true，否则返回false。

具体算法：

3、行编辑程序问题

如何实现简单的行编辑程序？
●设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。
输入缓冲区
●例如，C语言中执行scanf、getchar等使用输入缓冲区的函数时，用户输入的数据先被存入缓冲区中，等待用户按下回车键，scanf或getchar等函数才从缓冲区里依次取走数据。
●优点：允许用户对输入错误进行及时修改假设从终端接受了这样两行字符：
whli##ilr#e(s#*s)
outcha@putchar(*s=#++);
则实际有效的是下列两行：
while(*s)
putchar(*s++);

设计思路：

设这个输入缓冲区为栈结构。
每当从终端接受了一个字符后，先作如下判断：
●如果该字符既不是退格符也不是退行符，则将其压入栈顶；
●如果该字符是一个退格符，则从栈顶删去一个字符；
●如果该字符是一个退行符，则将字符栈清为空栈。

具体算法：

4、迷宫求解（内容较多且不好理解，有兴趣的看教材P50-52）

重点在于解决以下问题以及掌握其中的思想。

5、表达式求值

 算符间的优先关系

示例：3*（7-2）#

 算法思想：

三、栈与递归

1、递归的定义

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。

2、递归定义的数学函数

（1）阶乘函数

（2）2阶Fibonaci数列

 3、具有递归特性的数据结构

树与广义表

4、可递归求解的问题——迷宫问题、Hanoi塔问题

5、用分治法求解递归问题

分治法——对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解。
必备的三个条件
①能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的。
②可以通过上述转化而使问题简化。
③必须有一个明确的递归出口，或称递归的边界。

6、用C语言实现汉诺塔

#include 
int main()
{
  int hanoi(int,char,char,char);
  int n;
  printf("Input the number of diskes: ");
  scanf("%d",&n);
  printf("n");
  hanoi(n,'A','B','C');
  return 0;
}

int hanoi(int n,char x,char y,char z)
{
  int move(char,int,char);
  if(n==1)
     move(x,1,z);
  else
{
     hanoi(n-1,x,z,y);
     move(x,n,z);
     hanoi(n-1,y,x,z);
}
  return 0;
}

int move(char getone,int n,char putone)
{
   static int counter=1;//全局变量对移动次数计数
   printf("%2d:%3d # %c---%cln",counter,n,getone,putone);
   if(counter++%3==0)
     printf("/n");
   return 0;
}

7.递归与迭代

迭代——通过某段代码的重复执行来实现循环

递归——通过重复调用函数自身来实现循环

递归算法结构清晰，程序易读，时空开销大。  迭代时空效率较高。
一般情况下，当迭代方法比较容易找到时，应该避免使用递归；反之，当很难建立一个迭代方法，或者当问题底层的数据结构本身就是递归的时，递归就是比较好的方法。

四、队列

1、队列的类型定义

（1）定义——只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表。

      队尾（rear）——允许插入的一段   队头（front）——允许删除的一端
（2）逻辑结构——与线性表相同，仍为一对一关系。
（3）存储结构——用顺序队列或链队存储均可。
（4）运算规则——先进先出（FIFO）
（5）实现方式——关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同。

（6）队列的抽象数据类型

ADT Queue {
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R1={|ai-1,ai∈D,i=1,2,…,n}
约定a1端为队列头,an端为队列尾
基本操作：
(1) InitQueue(&Q)//构造空队列
(2)DestroyQueue(&Q）∥销毁队列
(3) ClearQueue(&S)//清空队列
(4) QueueEmpty(S)//判空。空--TRUE
(5) QueueLength(Q)//取队列长度
(6) GetHead (Q,&e)//取队头元素
(7) EnQueue (&Q,e)∥入队列
(8) DeQueue (&Q,&e)//出队列
(9) Queue Traverse(Q,visit())//遍历
}ADT Queue

2、链队列

（1）存储结构定义

typedef struct QNode{∥结点类型
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct{∥链队列类型
  QueuePtr front;∥队头指针
  QueuePtr rear;∥队尾指针
} LinkQueue;

 （2）队列运算指针变化状况

 （3）链队列初始化

int InitQueue(LinkQueue &Q)
{ ∥构造一个空队列Q
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    if (!Q.front) 
       exit (-1);//存储分配失败
    Q.front->next=NULL；∥头结点指针域置空
    return 1;
}

（4）销毁链队列

int DestroyQueue(LinkQueue &Q)
{ ∥销毁队列Q
  while(Q.front)//队列非空
  {
     Q.rear=Q.front->next;//Q.rear做辅助指针，从头结点开始删
     free(Q.front);
     Q.front=Q.rear; 
  }
  return 1;
}

（5）判断链队列是否为空

int QueueEmpty(LinkQueue Q)
{//判断队列是否为空
    if(Q.front==Q.rear)
         return 1;
    else
         return 0;
}

（6）求链队列的队头元素

int GetHead(LinkQueue Q,QElemType &e)
{
    if(Q.front==Q.rear) 
        return 0;
    e=Q.front->next->data;
    return 1;
}

（7）链队列入队

int EnQueue(LinkQueue &Q,QElemType e)
{ //插入元素e为Q的新的队尾元素
   p=(QueuePtr)malloc(sizeof(QNode));
   if(!p)
      exit(-1)；//存储分配失败
   p->data=e; 
   p->next=NULL;
   Q.rear->next=p;
   Q.reаr=р;
   return 1;
}

（8）链队列出列

int DeQueue (LinkQueue &Q,QElemType &e)
{ //若队列不空，则删除Q的队头元素，
  //用e返回其值，并返回1；否则返回0
  if(Q.front==Q.rear)
       return 0;//队空 
  p=Q.front->next;
  e=p->data;
  Q.front->next=p->next;
  if(Q.rear==p)
     Q.rear=Q.front;//考虑最后一个元素被删
  free (p);
  return 1;
}

3、循环队列——队列的顺序表示与实现

（1）顺序存储结构定义

#define MAXQSIZE 100 //最大队列长度
typedef struct{
   QElemType *base;//动态分配存储空间
   int front;//头指针，若队列不空，指向队列头元素
   int rear;∥尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

约定：
空队标志：front==rear=0
入队：base[rear++]=x;
出队：x=base[front++];
存在问题：假溢出——front≠0，rear=M时再入队就会出现假溢出。

解决方法——循环队列

基本思想：把队列设想成环形，让base[0]接在base[M-1]之后，若rear+1==M则令rear=0;
实现：利用“模”运算
入队：base[rear]=x;rear=(rear+1)%M;
出队： x=base[front]; front=(front+1)%M;

此时出现了一个问题，如何判断队满，因为队空和队满条件都是front=rear。

解决方案：
1.另外设一个标志以区别队空、队满
2.少用一个元素空间。

主要介绍第二种方法：

选用少用一个元素空间：约定以“队头指针在队尾指针的下一位置（指环状的下一位置）上”作为队满的标志。
队空条件：front＝rear（初始化时：front=rear）
队满条件：front=(rear+1)%M (M=maxsize)
队列长度：L=（M+rear-front）%M

 

 （2）循环队列的存储结构

在C语言中不能用动态分配的一维数组来实现循环队列，若用户的应用程序中设有循环队列，必须为循环队列设定一个最大队列长度；若用户无法预估队列的最大长度，则宜采用链队列。

#define MAXQSIZE 100 //最大长度
typedef struct{
  QElemType *base; //初始化的动态分配存储空间
  int front;//头指针
  int rear;//尾指针
}SqQueue;

（3）初始化

int InitQueue(SqQueue &Q)
{ //构造一个空队列Q
    Q.base =(QElemType*)malloc(MAXQSIZE *sizeof (QElemType));
    if(!Q.base)
       exit(-1)；//存储分配失败,退出程序
    Q.front=Q.rear=0;
    return 1;
}

（4）求循环队列的长度

int QueueLength(SqQueue Q)
{
   return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

循环队列中的“长度”到底是指总长度还是数据元素个数？
答：一般情况下的长度（L）是指元素个数（不含头结点
或空闲单元），而MAXQSIZE M才是指所有单元总数，即"容量”。 

（5）循环队列入队

int EnQueue(SqQueue &Q,QElemType e)
{ //插入元素e为Q的新的队尾元素
   if ((Q.rear+1) % MAXQSIZE==Q.front)
      return 0;//队列满
   Q.base[Q.rear]=e;//存储
   Q.rear=(Q.rear+1)% MAXQSIZE;//指针后移
   return 1;
}

（6）循环队列出队

int DeQueue(SqQueue &Q,QElemType &e)
{∥若队列不空，则删除Q的队头元素，
∥用e返回其值，并返回1，否则返回0
   if(Q.front==Q.rear) //栈空
        return 0;
   e=Q.base[Q.front];
   Q.front=(Q.front+1) % MAXQSIZE;
   return 1;
}

 （7）练习

---

总结

上面主要介绍了数据结构（C语言版）第三章栈和队列内容，主要包括栈的相关定义域操作、栈的应用举例、栈与递归以及队列。

其中重点在于栈与队列的基本操作实现算法，难点在于栈的应用举例以及栈的递归。

希望大家能够通过学习掌握栈与队列这一数据结构并且掌握其相关操作的实现以及一些实际运用的思想。