网站开发岗位职责,深圳南山企业网站建设,网站建设互联网推广,wordpress多个字体大小文章目录 前言1. 栈的顺序存储#xff08;顺序栈#xff09;2. 栈的基本操作#x1f351; 入栈操作#x1f351; 出栈操作#x1f351; 获取栈顶元素#x1f351; 获取栈的长度#x1f351; 判断是否为空栈#x1f351; 判断栈是否满了#x1f351; 打印栈内的元素顺序栈2. 栈的基本操作 入栈操作 出栈操作 获取栈顶元素 获取栈的长度 判断是否为空栈 判断栈是否满了 打印栈内的元素 测试函数 3. 共享栈 代码实现 4. 链式栈 代码实现 5. 总结 前言
栈是一种线性表。不过它只能在一端进行插入和删除操作先入栈的数据只能后出来而后入栈的数据只能先出来。所以栈具有先进后出或者后进先出的特性。通常来说我们可以把栈理解为一种 受限的线性表。
如果我们把栈比成一个类似木桶这样的容器栈有两端把允许进行插入和删除操作的一端称为 栈顶top也就是桶口或者称为线性表的表尾而另一端称为 栈底bottom也就是桶底或者称为线性表的表头。不包含任何数据的栈叫做空栈空线性表。 整体结构理清之后我们再说相关的操作。向栈中插入元素可以叫做 入栈 或进栈从栈中删除元素就叫 出栈。除了能够在表尾插入和删除数据外对于栈这种数据结构在任何其他位置插入和删除数据都不应该被允许。你只能提供符合这个规定的操作接口否则实现的就不是栈了。
栈也被称为 后进先出Last In First OutLIFO的线性表这意味着最后放入到栈里的数据插入数据只能最先被从栈中拿出来删除数据。
其实我们生活中满足栈这种后进先出的情形非常多比如往抽屉里放东西先放进去的肯定会被堆到最里面所以只能最后取出而最后放入的物品往往在最前面或者最上面所以会被最先取出。
如果用示意图表示用栈存取数据的过程就会像下图一样 在上图中如果分别将数据 a1、a2、a3、a4、a5 存入栈中那么在将数据出栈的时候顺序就应该是 a5、a4、a3、a2、a1与入栈顺序正好相反。
栈是 受限的线性表比如因为只能在栈顶进行元素的插入和删除操作所以也无法指定插入和删除操作的位置所以栈所支持的操作可以理解为线性表操作的子集一般包括栈的创建、入栈增加数据、出栈删除数据、获取栈顶元素查找数据、判断栈是否为空或者是否已满等操作。
1. 栈的顺序存储顺序栈
所谓顺序栈就是顺序存储用一段连续的内存空间依次存储栈中的数据。
这里有 2 种保存数据的方案
通过为一维数组 静态 分配内存的方式来保存数据。通过为一维数组 动态 分配内存的方式来保存数据。
为了顺序栈中数据存满时可以对栈进行扩容在这里我会采用第 2 种保存数据的方案来编写顺序栈的实现代码。
此外为了考虑到元素存取的便利性将数组下标为 0 的一端作为栈底最合适。
2. 栈的基本操作
先进行类定义、初始化以及释放操作。
#define InitSize 10 //动态数组的初始尺寸
#define IncSize 5 //当动态数组存满数据后每次扩容所能多保存的数据元素数量template typename T
class SeqStack
{
public:SeqStack(int length InitSize); //构造函数参数可以有默认值~SeqStack(); //析构函数public:bool Push(const T e); //入栈增加数据bool Pop(T e); //出栈删除数据也就是删除栈顶数据bool GetTop(T e); //读取栈顶元素但该元素并没有出栈而是依旧在栈中void DispList(); //输出顺序栈中的所有元素int ListLength(); //获取顺序栈的长度实际拥有的元素数量bool IsEmpty(); //判断顺序栈是否为空bool IsFull(); //判断顺序栈是否已满private:void IncreaseSize(); //当顺序栈存满数据后可以调用此函数为顺序栈扩容private:T* m_data; //存放顺序栈中的元素int m_maxsize; //动态数组最大容量int m_top; //栈顶指针(用作数组下标)指向栈顶元素该值为-1表示空栈
};//通过构造函数对顺序栈进行初始化
template typename T
SeqStackT::SeqStack(int length)
{m_data new T[length]; //为一维数组动态分配内存m_maxsize length; //顺序栈最多可以存储m_maxsize个数据元素m_top -1; //空栈
}//通过析构函数对顺序栈进行资源释放
template typename T
SeqStackT::~SeqStack()
{delete[] m_data;
}在主函数中加入代码创建一个初始大小为 10 的顺序栈对象。
int main()
{SeqStackint st(10);return 0;
} 创建好以后那么顺序栈看起来就会是下图的样子此时是一个空栈 入栈操作
入栈增加数据通常时间复杂度为 O ( 1 ) O(1) O(1)但一旦需要扩容时间复杂度就会变成 O ( n ) O(n) O(n)了
代码实现
template typename T
bool SeqStackT::Push(const T e)
{if (IsFull() true){IncreaseSize(); //扩容}m_data[m_top] e; //存放元素e栈顶指针向后走return true;
}当顺序栈存满数据后可以调用此函数为顺序栈扩容时间复杂度为 O ( n ) O(n) O(n)
templateclass T
void SeqStackT::IncreaseSize()
{T* p m_data;m_data new T[m_maxsize IncSize]; //重新为顺序栈分配更大的内存空间 for (int i 0; i m_top; i){m_data[i] p[i]; //将数据复制到新区域}m_maxsize m_maxsize IncSize; //顺序栈最大长度增加IncSizedelete[] p; //释放原来的内存空间
}出栈操作
出栈删除数据也就是删除栈顶数据时间复杂度为 O ( 1 ) O(1) O(1)
template typename T
bool SeqStackT::Pop(T e)
{if (IsEmpty() true){cout 当前顺序栈为空不能进行出栈操作! endl;return false;}e m_data[m_top--]; //栈顶元素值返回到e中。return true;
}获取栈顶元素
读取栈顶元素但该元素并没有出栈而是依旧在栈顶中因此 m_top 值不会发生改变时间复杂度为 O ( 1 ) O(1) O(1)
代码实现
template typename T
bool SeqStackT::GetTop(T e)
{if (IsEmpty() true){cout 当前顺序栈为空不能读取栈顶元素! endl;return false;}e m_data[m_top]; //栈顶元素返回到e中。return true;
}获取栈的长度
获取顺序栈的长度实际拥有的元素数量时间复杂度为 O ( 1 ) O(1) O(1)
代码实现
templateclass T
int SeqStackT::ListLength()
{return m_top 1;
}判断是否为空栈
判断顺序栈是否为空时间复杂度为 O ( 1 ) O(1) O(1)
代码实现
templateclass T
bool SeqStackT::IsEmpty()
{if (m_top -1){return true;}return false;
}判断栈是否满了
判断顺序栈是否已满时间复杂度为 O ( 1 ) O(1) O(1)
代码实现
templateclass T
bool SeqStackT::IsFull()
{if (m_top m_maxsize - 1){return true;}return false;
}打印栈内的元素
输出顺序栈中的所有元素时间复杂度为 O ( n ) O(n) O(n)
代码实现
templateclass T
void SeqStackT::DispList()
{//按照从栈顶到栈底的顺序来显示数据for (int i m_top; i 0; --i){cout m_data[i] ; //每个数据之间以空格分隔}cout endl; //换行
}测试函数
在主函数中增加测试代码。
代码实现
int main()
{SeqStackint st(10);//入栈 st.Push(10); st.Push(20); st.Push(30); st.Push(40); st.Push(50); //打印st.DispList(); //获取栈顶元素int elem 0;st.GetTop(elem);cout elem endl; //出栈 st.Pop(elem);st.Pop(elem);//打印st.DispList(); return 0;
} 运行结果如下 在有的实现栈的代码中会让 m_top 的初始值等于 0指向 0 的位置那么判断栈是否为空的代码IsEmpty 函数也就是判断 m_top 是否等于 0而判断栈满IsFull 函数的条件也应该变成 if (m_top m_maxsize)。
这种实现方式实际就是让 m_top 代表下一个可以放入栈中的元素的下标当数据入栈Push 函数时代码行 m_top 和代码行 m_data[m_top] e 的执行就需要互换顺序而当数据出栈Pop 函数时代码行 e m_data[m_top] 和代码行 m_top-- 的执行也需要互换顺序。
3. 共享栈
所谓共享栈就是两个顺序栈共享存储空间。为什么会提出这个概念呢
之前我们提到的顺序栈一个比较大的缺点是保存数据的空间初始尺寸不好确定如果太大就会浪费空间如果太小那么存满数据后再入栈新数据就需要扩容而扩容就又需要开辟一整块更大的新区域并将原有数据复制到新区域操作起来比较耗费性能。
不过我们可以设想一下。假设有两个相同数据类型的顺序栈如果分别为他们开辟了保存数据的空间那是不是就可能出现第一个栈的数据已经存满了而另一个栈中还有很多存储空间的情形呢那么如果开辟出来一块保存数据的空间后让这两个栈同时使用也就是共享这块空间是不是也许就能达到最大限度利用这块空间、减少浪费的目的呢这就是共享栈的含义。
下面直接给出共享栈的实现代码。 代码实现
代码实现
//共享栈
template typename T //T代表数组中元素的类型
class ShareStack
{
public:ShareStack(int length InitSize) //构造函数参数可以有默认值{m_data new T[length]; //为一维数组动态分配内存m_maxsize length; //共享栈最多可以存储m_maxsize个数据元素m_top1 -1; //顺序栈1的栈顶指针为-1表示空栈m_top2 length; //顺序栈2的栈顶指针为length表示空栈}~ShareStack() //析构函数{delete[] m_data;}public:bool IsFull() //判断共享栈是否已满{if (m_top1 1 m_top2){return true;}return false;}bool Push(int stackNum, const T e) //入栈增加数据,参数stackNum用于标识栈1还是栈2{if (IsFull() true){//共享栈满了你也可以自行增加代码来支持动态增加共享栈的容量这里简单处理直接返回falsecout 共享栈已满不能再进行入栈操作了! endl;return false;}if (stackNum 1){//要入的是顺序栈1m_top1; //栈顶指针向后走m_data[m_top1] e;}else{//要入的是顺序栈2m_top2--;m_data[m_top2] e;}return true;}bool Pop(int stackNum, T e) //出栈删除数据也就是删除栈顶数据{if (stackNum 1){//要从顺序栈1出栈if (m_top1 -1){cout 当前顺序栈1为空不能进行出栈操作! endl;return false;}e m_data[m_top1]; //栈顶元素值返回到e中m_top1--;}else{//要从顺序栈2出栈if (m_top2 m_maxsize){cout 当前顺序栈2为空不能进行出栈操作! endl;return false;}e m_data[m_top2];m_top2;}return true;}private:T* m_data; //存放共享栈中的元素int m_maxsize; //动态数组最大容量int m_top1; //顺序栈1的栈顶指针int m_top2; //顺序栈2的栈顶指针
};从代码中可以看到既然是两个顺序栈共享同一块内存空间那么就需要引入两个栈顶指针m_top1、m_top2来分别标识这两个顺序栈的栈顶位置。顺序栈 1 的栈底位置在最下面而顺序栈 2 的栈底位置在最上面。
同时注意阅读判断共享栈是否已满的代码IsFull以及入栈和出栈Push、Pop的代码。如果对顺序栈 1 进行入栈操作则 m_top1 要递增数据要从下向上存储。如果对顺序栈 2 进行入栈操作则 m_top2 要递减数据从上向下存储。
这样的话从逻辑上看实现的是两个栈但这两个栈又是共享着同一块物理内存的从而提高内存利用率。如下图所示 4. 链式栈
链式栈就是链式存储方式来实现的栈。我们知道单链表的插入操作 ListInsert 方法其第一个参数用于指定元素要插入的位置如果把该参数值设置为 1就是链式栈的入栈操作。对于单链表的删除操作 ListDelete 方法其参数用于指定要删除的元素位置如果把该参数值也设置为 1就是链式栈的出栈操作。
可以发现链式栈其实就是一个单链表只不过人为的规定只能在单链表的第一个位置进行插入入栈和删除出栈操作即链表头这一端是栈顶。
链式栈的实现代码和单链表的实现代码非常类似可以把链式栈理解成受限的单链表。但对于链式栈来讲考虑到只在链表头位置插入数据所以链式栈一般不需要带头节点。 代码实现
代码实现
//链式栈中每个节点的定义
template typename T //T代表数据元素的类型
struct StackNode
{T data; //数据域存放数据元素StackNodeT* next; //指针域指向下一个同类型和本节点类型相同节点
};//链式栈的定义
template typename T
class LinkStack
{
public:LinkStack(); //构造函数~LinkStack(); //析构函数public:bool Push(const T e); //入栈元素ebool Pop(T e); //出栈删除数据也就是删除栈顶数据bool GetTop(T e); //读取栈顶元素但该元素并没有出栈而是依旧在栈中void DispList(); //输出链式栈中的所有元素int ListLength(); //获取链式栈的长度bool Empty(); //判断链式栈是否为空private:StackNodeT* m_top; //栈顶指针int m_length; //链式栈当前长度
};//通过构造函数对链式栈进行初始化
template typename T
LinkStackT::LinkStack()
{m_top nullptr;m_length 0;
}//通过析构函数对链式栈进行资源释放
template typename T
LinkStackT::~LinkStack()
{T tmpnousevalue { 0 };while (Pop(tmpnousevalue) true) {} //把栈顶元素删光while循环也就退出了此时也就是空栈了
}//入栈元素e时间复杂度为O(1)
template typename T
bool LinkStackT::Push(const T e)
{StackNodeT* node new StackNodeT;node-data e;node-next m_top;m_top node;m_length;return true;
}//出栈删除数据也就是删除栈顶数据时间复杂度为O(1)
template typename T
bool LinkStackT::Pop(T e)
{if (Empty() true) //链式栈为空return false;StackNodeT* p_willdel m_top;m_top m_top-next;m_length--;e p_willdel-data;delete p_willdel;return true;
}//读取栈顶元素但该元素并没有出栈而是依旧在栈中
template typename T
bool LinkStackT::GetTop(T e)
{if (Empty() true) //链式栈为空return false;e m_top-data;return true;
}//输出链式栈中的所有元素时间复杂度为O(n)
templateclass T
void LinkStackT::DispList()
{if (Empty() true) //链式栈为空return;StackNodeT* p m_top;while (p ! nullptr){cout p-data ; //每个数据之间以空格分隔p p-next;}cout endl; //换行
}//获取链式栈的长度时间复杂度为O(1)
templateclass T
int LinkStackT::ListLength()
{return m_length;
}//判断链式栈是否为空时间复杂度为O(1)
templateclass T
bool LinkStackT::Empty()
{if (m_top nullptr) //链式栈为空{return true;}return false;
}与顺序栈相比链式栈没有长度限制不存在内存空间的浪费问题。但对于数据的入栈和出栈这些需要对数据进行定位的操作顺序栈更加方便而链式栈中的每个数据节点都需要额外的指针域以指向下一个数据节点这会略微降低数据的存储效率当然也会多占用一些内存。
所以如果要存储的数据数量无法提前预估一般考虑使用链式栈而如果数据的数量比较固定可以考虑使用顺序栈。
5. 总结
顺序栈可以看成是功能受限的数组或把链式栈看成是功能受限的单链表都是没有问题的。为什么创造出功能受限的栈来呢你可以理解为因为功能受限所以使用起来也更加简单错用误用的概率比数组、单链表等更低。
栈有很多应用比如在函数调用期间需要用栈来保存临时的参数信息、函数内局部变量信息、函数调用返回地址信息等。网上也有很多小例子演示栈的简单应用比如利用栈来进行括号匹配的检验利用栈来计算表达式结果等。以及用栈来实现诸如树的非递归遍历、记录节点路径信息等操作。
