您当前的位置:首页 > 电脑百科 > 程序开发 > 编程百科

栈的简介及C++模板实现

时间:2019-08-26 16:28:32  来源:  作者:

0. 数据结构图文解析系列

数据结构系列文章数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现数据结构图文解析之:栈的简介及C++模板实现数据结构图文解析之:队列详解与C++模板实现数据结构图文解析之:树的简介及二叉排序树C++模板实现.数据结构图文解析之:AVL树详解及C++模板实现数据结构图文解析之:二叉堆详解及C++模板实现数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现

回到顶部

1. 栈的简介

1.1栈的特点

栈(Stack)是一种线性存储结构,它具有如下特点:

  1. 栈中的数据元素遵守”先进后出"(First In Last Out)的原则,简称FILO结构。
  2. 限定只能在栈顶进行插入和删除操作。

1.2栈的相关概念

栈的相关概念:

  1. 栈顶与栈底:允许元素插入与删除的一端称为栈顶,另一端称为栈底。
  2. 压栈:栈的插入操作,叫做进栈,也称压栈、入栈。
  3. 弹栈:栈的删除操作,也叫做出栈。

例如我们有一个存储整型元素的栈,我们依次压栈:{1,2,3}

数据结构图文解析之:栈的简介及C++模板实现

 

在压栈的过程中,栈顶的位置一直在”向上“移动,而栈底是固定不变的。

如果我们要把栈中的元素弹出来:

数据结构图文解析之:栈的简介及C++模板实现

 

出栈的顺序为3、2、1 ,顺序与入栈时相反,这就是所谓的”先入后出“。

在弹栈的过程中,栈顶位置一直在”向下“移动,而栈底一直保持不变。

如果你玩过一种称为汉诺塔的益智玩具,你就会知道游戏中小圆盘的存取就是一种先进后出的顺序,一个圆柱就是一个栈:

数据结构图文解析之:栈的简介及C++模板实现

 

1.3 栈的操作

栈的常用操作为:

  1. 弹栈,通常命名为pop
  2. 压栈,通常命名为push
  3. 求栈的大小
  4. 判断栈是否为空
  5. 获取栈顶元素的值

1.4 栈的存储结构

栈既然是一种线性结构,就能够以数组或链表(单向链表、双向链表或循环链表)作为底层数据结构。

本文我们以数组、单向链表为底层数据结构构建栈。

回到顶部

2. 基于数组的栈实现

当以数组为底层数据结构时,通常以数组头为栈底,数组头到数组尾为栈顶的生长方向:

数据结构图文解析之:栈的简介及C++模板实现

 

2.1 栈的抽象数据类型

栈提供了如上所述操作的相应接口。

template<typename T>
class ArrayStack
{
public:
 ArrayStack(int s = 10); //默认的栈容量为10
 ~ArrayStack();
 
public:
 T top(); //获取栈顶元素
 void push(T t); //压栈操作
 T pop(); //弹栈操作
 bool isEmpty(); //判空操作
 int size(); //求栈的大小
 
private:
 int count; //栈的元素数量
 int capacity; //栈的容量
 T * array; //底层为数组
};
  1. count 为栈的元素数量,capacity为栈的容量,count<=capacity,当栈满的时候,count = capacity。
  2. 本实现中不支持栈的动态扩容,栈满的时候无法再插入元素。栈的容量在定义栈的时候就需要指定,默认的栈容量为10。

2.2 栈的具体实现

栈的实现还是相对简单的,很容易理解。这里就不再画蛇添足了。

 /*栈的判空操作*/
template <typename T>
bool ArrayStack<T>::isEmpty()
{
 return count == 0; //栈元素为0时为栈空
};
 
/*返回栈的大小*/
 template <typename T>
int ArrayStack<T>::size()
{
 return count;
};
 
/*插入元素*/
template <typename T>
void ArrayStack<T>::push(T t)
{
 if (count != capacity) //先判断是否栈满
 {
 array[count++] = t; 
 }
};
 
/*弹栈*/
template <typename T>
T ArrayStack<T>::pop()
{
 if (count != 0) //先判断是否是空栈
 {
 return array[--count];
 }
};
 
/*获取栈顶元素*/
template <typename T>
T ArrayStack<T>::top()
{
 if (count != 0)
 {
 return array[count - 1];
 }
};
 

2.3 栈的代码测试

int _tmain(int argc, _TCHAR* argv[])
{
 ArrayStack <int> p(5);
 for (int i = 0; i < 5; i++)
 {
 p.push(i);
 }
 cout << "栈的大小:"<<p.size() << endl;
 cout << "栈是否为空:"<<p.isEmpty() << endl;
 cout << "栈顶元素:"<<p.top() << endl;
 cout << "依次出栈:" << endl;
 while (!p.isEmpty())
 {
 cout << p.pop() << endl;
 }
 getchar();
 return 0;
}

测试结果:

栈的大小:5
栈是否为空:0
栈顶元素:4
依次出栈:
4
3
2
1
0

回到顶部

3. 基于单链表的栈

以链表为底层的数据结构时,以链表头为作为栈顶较为合适,这样方便节点的插入与删除。压栈产生的新节点将一直出现在链表的头部;

数据结构图文解析之:栈的简介及C++模板实现

 

3.1 链表节点

/*链表节点结构*/
template <typename T>
struct Node
{
 Node(T t) :value(t), next(nullptr){};
 Node() :next(nullptr){};
 
public:
 T value;
 Node<T>* next;
};
  1. value:栈中元素的值
  2. next:链表节点指针,指向直接后继

3.2 栈的抽象数据类型

基于链表的栈提供的接口与基于数组的栈一致。

 
/*栈的抽象数据结构*/
template <typename T>
class LinkStack
{
public:
 LinkStack();
 ~LinkStack();
public:
 
 bool isEmpty();
 int size();
 void push(T t);
 T pop();
 T top();
 
private:
 
 Node<T>* phead;
 int count;
};

3.3 栈的具体实现

/*返回栈的大小*/
template <typename T>
int LinkStack<T>::size()
{
 return count;
};
/*栈的判空操作*/
template <typename T>
bool LinkStack<T>::isEmpty()
{
 return count == 0;
};
/*插入元素*/
template<typename T>
void LinkStack<T>::push(T t)
{
 Node <T> *pnode = new Node<T>(t);
 pnode->next = phead->next;
 phead->next = pnode;
 count++;
};
/*弹栈*/
template <typename T>
T LinkStack<T>::pop()
{
 if (phead->next != nullptr) //栈空判断
 {
 Node<T>* pdel = phead->next;
 phead->next = phead->next->next;
 T value = pdel->value;
 delete pdel;
 count--;
 return value;
 }
};
/*获取栈顶元素*/
template <typename T>
T LinkStack<T>::top()
{
 if (phead->next!=nullptr)
 return phead->next->value;
};

3.4 栈的代码测试

int _tmain(int argc, _TCHAR* argv[])
{
 LinkStack <string> lstack;
 lstack.push("hello");
 lstack.push("to");
 lstack.push("you!");
 
 cout << "栈的大小:" << lstack.size() << endl;
 cout <<"栈顶元素:"<< lstack.top() << endl;
 
 while (!lstack.isEmpty())
 {
 lstack.pop();
 }
 
 cout << "栈的大小:" << lstack.size() << endl;
 
 getchar();
 return 0;
}

测试结果:

栈的大小:3
栈顶元素:you!
栈的大小:0

回到顶部

4. 栈的完整代码

基于数组的栈: https://github.com/huanzheWu/Data-Structure/blob/master/Stack/Main/Main/ArrayStack.h

基于单链表的栈:https://github.com/huanzheWu/Data-Structure/blob/master/singleList/singleList/singleList.h

原创文章,转载请注明出处:http://www.cnblogs.com/QG-whz/p/5170418.html



Tags:栈的简   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
0. 数据结构图文解析系列数据结构系列文章数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现数据结构图文解析之:栈的简介及C++模板实现数据结构图文解析之:队列详解...【详细内容】
2019-08-26  Tags: 栈的简  点击:(214)  评论:(0)  加入收藏
▌简易百科推荐
本文分为三个等级自顶向下地分析了glibc中内存分配与回收的过程。本文不过度关注细节,因此只是分别从arena层次、bin层次、chunk层次进行图解,而不涉及有关指针的具体操作。前...【详细内容】
2021-12-28  linux技术栈    Tags:glibc   点击:(3)  评论:(0)  加入收藏
摘 要 (OF作品展示)OF之前介绍了用python实现数据可视化、数据分析及一些小项目,但基本都是后端的知识。想要做一个好看的可视化大屏,我们还要学一些前端的知识(vue),网上有很多比...【详细内容】
2021-12-27  项目与数据管理    Tags:Vue   点击:(2)  评论:(0)  加入收藏
程序是如何被执行的&emsp;&emsp;程序是如何被执行的?许多开发者可能也没法回答这个问题,大多数人更注重的是如何编写程序,却不会太注意编写好的程序是如何被运行,这并不是一个好...【详细内容】
2021-12-23  IT学习日记    Tags:程序   点击:(9)  评论:(0)  加入收藏
阅读收获✔️1. 了解单点登录实现原理✔️2. 掌握快速使用xxl-sso接入单点登录功能一、早期的多系统登录解决方案 单系统登录解决方案的核心是cookie,cookie携带会话id在浏览器...【详细内容】
2021-12-23  程序yuan    Tags:单点登录(   点击:(8)  评论:(0)  加入收藏
下载Eclipse RCP IDE如果你电脑上还没有安装Eclipse,那么请到这里下载对应版本的软件进行安装。具体的安装步骤就不在这赘述了。创建第一个标准Eclipse RCP应用(总共分为六步)1...【详细内容】
2021-12-22  阿福ChrisYuan    Tags:RCP应用   点击:(7)  评论:(0)  加入收藏
今天想简单聊一聊 Token 的 Value Capture,就是币的价值问题。首先说明啊,这个话题包含的内容非常之光,Token 的经济学设计也可以包含诸多问题,所以几乎不可能把这个问题说的清...【详细内容】
2021-12-21  唐少华TSH    Tags:Token   点击:(10)  评论:(0)  加入收藏
实现效果:假如有10条数据,分组展示,默认在当前页面展示4个,点击换一批,从第5个开始继续展示,到最后一组,再重新返回到第一组 data() { return { qList: [], //处理后...【详细内容】
2021-12-17  Mason程    Tags:VUE   点击:(14)  评论:(0)  加入收藏
什么是性能调优?(what) 为什么需要性能调优?(why) 什么时候需要性能调优?(when) 什么地方需要性能调优?(where) 什么时候来进行性能调优?(who) 怎么样进行性能调优?(How) 硬件配...【详细内容】
2021-12-16  软件测试小p    Tags:性能调优   点击:(20)  评论:(0)  加入收藏
Tasker 是一款适用于 Android 设备的高级自动化应用,它可以通过脚本让重复性的操作自动运行,提高效率。 不知道从哪里听说的抖音 app 会导致 OLED 屏幕烧屏。于是就现学现卖,自...【详细内容】
2021-12-15  ITBang    Tags:抖音防烧屏   点击:(25)  评论:(0)  加入收藏
11 月 23 日,Rust Moderation Team(审核团队)在 GitHub 上发布了辞职公告,即刻生效。根据公告,审核团队集体辞职是为了抗议 Rust 核心团队(Core team)在执行社区行为准则和标准上...【详细内容】
2021-12-15  InfoQ    Tags:Rust   点击:(25)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条