本文主要是介绍数据结构和算法设计4 栈，队列和递归，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

一.栈 

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 once
typedef enum{ NOT_PRESENT, ENTRY_FOUND, RANGE_ERROR, SUCCESS, OVER_FLOW， DEFAULT_SIZE }Status;

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

#pragma once
#include"status.h"
template<class ElemType>
class 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;//遍历函数
};
//构造函数
template<class ElemType>
SeqStack<ElemType>::SeqStack(int size)
// 操作结果：构造一个最大容量为size的空栈
{
	maxSize = size;
	elems = new ElemType[maxSize];
	top1 = -1; top2 = size;
}
//析构函数
template<class ElemType>
SeqStack<ElemType>:: ~SeqStack() {
	delete [] elems；
}
//取得栈的长度
template<class ElemType>
int SeqStack<ElemType>::GetLength(int n) {
//判断n的值
if (n == 1)	
//共享栈前面的栈
return top1+1;
if (n == 2)
//共享栈后面的栈
return  maxSize-top2;
}
//判断栈是否为空	
template<class ElemType>
bool SeqStack<ElemType>:: IsEmpty(int n) const {
//前面那个栈top1=-1的时候为空，后面那个栈top2=maxSize的时候为空;
    if (n == 1)
	return (top1 == -1) ;	
    if (n == 2)
	return (top2 == maxSize) ;
}
//入栈函数
template<class ElemType>
Status SeqStack<ElemType>::Push(int n, const ElemType e) {
	if (top1 + 1 == top2)//判断是否栈满
		return OVER_FLOW;
	else{
		if (n == 1) 
		elems[++top1] = e;//先将top1+1，再将top1位置的元素赋为e
		if (n == 2)
		elems[--top2] = e;//先将top2-1，再将top2位置的元素赋为e
		return SUCCESS;
	}
}
//出栈函数
template<class ElemType>
Status SeqStack<ElemType>::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;
	}
}
//遍历函数
template<class ElemType>
void SeqStack<ElemType>::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 once
typedef enum{ NOT_PRESENT, ENTRY_FOUND, RANGE_ERROR, SUCCESS, OVER_FLOW， DEFAULT_SIZE }Status;

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

template<class ElemType>
class 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;
   
};
template<class ElemType>
SeqQueue<ElemType>::SeqQueue(int size){
	maxSize = size; 
	elems = new ElemType[maxSize];
	rear = front = 0; 
}
template<class ElemType>
int SeqQueue<ElemType>::GetLength() const
{
	return (rear - front + maxSize) % maxSize;
}
template<class ElemType>
Status SeqQueue<ElemType>::EnQueue(const ElemType e)
{
	if ((rear + 1) % maxSize == front)
		return OVER_FLOW;
	else{	
		elems[rear] = e;		
		rear = (rear + 1) % maxSize;	
		return SUCCESS;
	}
}
template<class ElemType>
Status SeqQueue<ElemType>::GetHead(ElemType &e) const
{
	if (!IsEmpty()) { 
		e = elems[front];	
		return SUCCESS;
	}
	else
		return UNDER_FLOW;
}
template<class ElemType>
Status SeqQueue<ElemType>::DelQueue(ElemType &e)
{
	if (!IsEmpty()) 	{ 
		e = elems[front];	
		front = (front + 1) % maxSize;		
		return SUCCESS;
	}
	else 
		return UNDER_FLOW;
}
//判断循环队列是否为空
template<class ElemType>
bool SeqQueue<ElemType>::IsEmpty() const
{        return     rear == front;        }
//循环队列的析构函数
template <class ElemType>
SeqQueue<ElemType>::~SeqQueue()
{        delete []elems;         }
//清空循环队列
template<class ElemType>
void SeqQueue<ElemType>::Clear() 
{        rear = front = 0;        }
//遍历循环队列
template <class ElemType>
void SeqQueue<ElemType>::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;
   else
       return n * fact(n-1);
}

void main()
{  int n;    long  f;
    cout << input a integer number:”;
    cin >> n;
    f = fact(n);
    cout << n << “!=“ << f;
}

这篇关于数据结构和算法设计4 栈，队列和递归的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！