目录

一.栈 

1.栈的定义和特点

2.栈的基本操作与类模板的定义

3.共享栈

1. 设计思路

2.共享栈的类模板定义与实现

二.队列 

1.队列的定义和特点

2.顺序队列 

 1.顺序队列的三种正常状态

​ 2.顺序队列的上溢和下溢

3.循环队列 

1.循环队列基本思想    

2.队满、队空判定条件 

3.循环队列的类模板定义和实现 

三.递归 

1 .递归的概念  

2.递归的应用 ：

3.递归过程与递归工作栈

1.非递归函数的调用  

2.递归函数的调用  

 如果觉得我写得还行的话，希望三连，鼓励一下哦！！！

一.栈 

1.栈的定义和特点

栈（stack）是一种常用的重要的数据结构，其应用十分广泛。栈定义为只允许在表的末端进行插入和删除的线性表。允许插入和删除的一端叫做栈顶（top），另一端叫做栈底(bottom)。无元素的栈称为空栈。

栈的特点:先进后出。

2.栈的基本操作与类模板的定义

由于栈本身就是一个操作受限的线性表，所以顺序栈和链式栈的基本操作与线性表的操作基本一样，甚至还要简单，所以这里就不给出普通栈的定义了，有需要的同学可以看一下

数据结构与算法设计3 顺序表和链表_m0_54024106的博客-CSDN博客

3.共享栈

栈的顺序存储结构是一种静态的存储结构，栈中元素的多少受到maxSize的限制，空间太大会造成存储空间的浪费，为解决这个问题，同时建立多个顺序栈，以实现存储空间的共享，这样就可以相互调节余缺，既能高效地节约存储空间，又能降低上溢的发生概率。 为两个栈申请一个共享的一维数组空间，将两个栈的栈底分别放在一维数组的两端，分别是-1和m。 由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。

栈空的条件：top1 == -1，top2==m

栈满的条件：top1 + 1 == top2

1. 设计思路

（1）定义两个栈顶指针top1,top2分别管理共享栈中的前后两个栈。

（2）定义函数成员时，通过参数指明相关操作实施的栈号,例如Status Push(int n,const ElemType e);//入栈函数，其中n为1或2，表示入栈的序号。

（3）判断栈空函数的实现：当top1等于-1，top2等于maxSize时栈空。

（4）入栈功能实现：先判断是否栈满，再判断n的值

   n=1时，将top1+1，再将top1位置的元素赋为e；

   n=2时，将top2-1，再将top2位置的元素赋为e。

（5）出栈功能实现：先判断是否栈空，再判断n的值

   n=1时，将top1位置的元素赋给e，再将top1-1；

   n=2时，将top2位置的元素赋给e，再将top2+1。

枚举类型Status定义 

#pragma oncetypedef enum{ NOT_PRESENT, ENTRY_FOUND, RANGE_ERROR, SUCCESS, OVER_FLOW， DEFAULT_SIZE }Status;

2.共享栈的类模板定义与实现

#pragma once#include"status.h"templateclass SeqStack {protected:int top1, top2;// 栈顶指针     int maxSize;// 栈最大容量     ElemType* elems; // 元素存储空间public:SeqStack(int size = DEFAULT_SIZE);//构造函数virtual ~SeqStack();//析构函数int GetLength(int n);//取得栈的长度bool IsEmpty(int n) const;//判断栈是否为空Status Push(int n,const ElemType e);//入栈函数Status Pop(int n,ElemType& e);//出栈函数void Traverse(int n,void (*Visit)(const ElemType&)) const;//遍历函数};//构造函数templateSeqStack::SeqStack(int size)// 操作结果：构造一个最大容量为size的空栈{maxSize = size;elems = new ElemType[maxSize];top1 = -1; top2 = size;}//析构函数templateSeqStack:: ~SeqStack() {delete [] elems；}//取得栈的长度templateint SeqStack::GetLength(int n) {//判断n的值if (n == 1)//共享栈前面的栈return top1+1;if (n == 2)//共享栈后面的栈return  maxSize-top2;}//判断栈是否为空templatebool SeqStack:: IsEmpty(int n) const {//前面那个栈top1=-1的时候为空，后面那个栈top2=maxSize的时候为空;    if (n == 1)return (top1 == -1) ;    if (n == 2)return (top2 == maxSize) ;}//入栈函数templateStatus SeqStack::Push(int n, const ElemType e) {if (top1 + 1 == top2)//判断是否栈满return OVER_FLOW;else{if (n == 1) elems[++top1] = e;//先将top1+1，再将top1位置的元素赋为eif (n == 2)elems[--top2] = e;//先将top2-1，再将top2位置的元素赋为ereturn SUCCESS;}}//出栈函数templateStatus SeqStack::Pop(int n, ElemType& e) {if (IsEmpty(1)&& IsEmpty(2) )//判断两个栈是否都为空，如果是返回下溢信息     return UNDER_FLOW;else {if (n == 1)e=elems[top1--] ;//先将top1位置的元素赋给e，再将top1-1；if (n == 2)e=elems[top2++];//先将top2位置的元素赋给e，再将top2+1；return SUCCESS;}}//遍历函数templatevoid SeqStack::Traverse(int n,void (*Visit)(const ElemType&)) const {if (n == 1) {for (int i = top1; i >= 0; i--) {(*Visit)(elems[i]);}}if (n == 2) {for (int i = top2; i <= maxSize - 1; i++) {(*Visit)(elems[i]);}}}

二.队列 

1.队列的定义和特点

队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素。 在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。 在队列中插入一个新元素的操作简称为进队或入队，新元素进队后就成为新的队尾元素； 从队列中删除一个元素的操作简称为出队或离队，当元素出队后，其后继元素就成为新的队头元素。

假设队列为q = (a1, a2 , … , an )，那么a1是队头元素，an是队尾元素。队列中的元素是按照a1, a2 , … , an的顺序进入的，退出队列也只能按照这个顺序退出。

队列的特点：先进先出。

2.顺序队列 

 1.顺序队列的三种正常状态

（1）若顺序队列为空，则front==rear，队列的初始状态可设置为front=rear=0；

（2）若顺序队列为满，则front==0且rear==MAXSIZE；

（3）若顺序队列非空非满，则MAXSIZE>rear>front;

 2.顺序队列的上溢和下溢

（1）当队空时，再进行出队就会产生“下溢”；

（2）当队满时，再进行入队就会产生“上溢”；

（3）此外，顺序队列还存在“假上溢”现象，即rear==MAXSIZE且front>0。

 如何解决，最容易想到的就是将front置为0，将元素一个一个往前移，但效率太低。

所以由于存在假溢出现象，实际软件系统中不使用上述顺序队列，而是使用接下来的循环队列。

3.循环队列 

1.循环队列基本思想    

把队列设想成环形，即若rear+1==maxsize,则令rear=0；若front+1==maxsize，亦令front=0 。

实现：利用“模”运算（以前例说明）

入队： elems[rear]=e;  rear=(rear+1)%maxsize;

出队： e=elems[front];  front=(front+1)%maxsize;

2.队满、队空判定条件 

假如将循环队列的所有空间都用上的话，队空与队满的判断条件相同，都为front=rear；

这样就区分不了队空还是队满，所以我们要

1.另外设一个标志以区别队空、队满

2.少用一个元素空间：

队空：front==rear  

队满：(rear+1)%maxsize==front

当maxsize比较大时，一个存储空间的浪费是微乎其微的。

 枚举类型Status定义 

#pragma oncetypedef enum{ NOT_PRESENT, ENTRY_FOUND, RANGE_ERROR, SUCCESS, OVER_FLOW， DEFAULT_SIZE }Status;

3.循环队列的类模板定义和实现 

templateclass SeqQueue {protected:int front, rear; // 队头队尾指针 int maxSize; // 队列容量 ElemType *elems; // 元素存储空间public:SeqQueue(int size = DEFAULT_SIZE);virtual ~SeqQueue();    int GetLength() const;    bool IsEmpty() const;    void Clear();    Status DelQueue(ElemType &e);    Status GetHead(ElemType &e) const;    Status EnQueue(const ElemType e);   void  Traverse(void (*Visit)(const ElemType &)) const;   };templateSeqQueue::SeqQueue(int size){maxSize = size; elems = new ElemType[maxSize];rear = front = 0; }templateint SeqQueue::GetLength() const{return (rear - front + maxSize) % maxSize;}templateStatus SeqQueue::EnQueue(const ElemType e){if ((rear + 1) % maxSize == front)return OVER_FLOW;else{elems[rear] = e;rear = (rear + 1) % maxSize;return SUCCESS;}}templateStatus SeqQueue::GetHead(ElemType &e) const{if (!IsEmpty()) { e = elems[front];return SUCCESS;}elsereturn UNDER_FLOW;}templateStatus SeqQueue::DelQueue(ElemType &e){if (!IsEmpty()) { e = elems[front];front = (front + 1) % maxSize;return SUCCESS;}else return UNDER_FLOW;}//判断循环队列是否为空templatebool SeqQueue::IsEmpty() const{ return     rear == front; }//循环队列的析构函数template SeqQueue::~SeqQueue(){ delete []elems;  }//清空循环队列templatevoid SeqQueue::Clear() { rear = front = 0; }//遍历循环队列template void SeqQueue::Traverse(void (*Visit)(const ElemType &)) const{for (int i = front; i != rear; i = (i + 1) % maxSize)(*Visit)(elems[i]);}

三.递归 

1 .递归的概念  

递归的定义：一个对象部分地包含自己，或用自己给自己定义，则该对象是递归的。

一个过程直接或间接地调用自己，则该过程是递归的。

2.递归的应用 ：

定义是递归的

问题解法是递归的     汉诺塔问题 

3.递归过程与递归工作栈

1.非递归函数的调用  

在函数调用前保存如下信息：（1）返回地址；（2）本函数调用时，与形参结合的实参值，包括函数名和函数参数；（3）本函数的局部变量值。

2.递归函数的调用  

使用递归工作栈保存如下信息：（1）返回地址：上一层中本次调用语句的后继语句地址；（2）本次函数调用时，与形参结合的实参值；（3）本层的局部变量值。 

long  fact(int n){    if(n == 0) return 1;   elsereturn n * fact(n-1);}

void main(){  int n;    long  f;    cout <> n;    f = fact(n);    cout << n << “!=“ << f;}