- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
栈一种常见的特殊线性数据结构,其特殊之处在于其操作顺序,下面会详细介绍,也正因为其特性,因此栈可以轻松解决表达式求值、括号匹配、递归算法、回溯算法等等问题.
栈的特殊性表现为操作受限,其一只允许在栈的一端进行元素插入和删除运算,其二栈的运算操作遵循后进先出(Last In First Out,简称LIFO)的原则.
入栈:当把元素插入到栈,这一行为叫做入栈,也称进栈或压栈; 。
出栈:当把元素从栈中移除,这一行为叫做出栈,也称退栈; 。
栈顶:允许元素进行插入和删除操作的一端称为栈顶; 。
栈底:与栈顶对应的另一个端称为栈底,并且不允许进行元素操作; 。
空栈:当栈中没有元素时叫做空栈.
满栈:当栈是有限容量,并且容量已用完,则称为满栈.
栈容量:当栈是有限容量,栈容量表示栈可以容纳的最大元素数量.
栈大小:表示当前栈中的元素数量.
栈是逻辑结构,因此以存储方式的不同可以分为顺序栈和链栈.
顺序栈就是使用连续的地址空间存储所有栈元素,通常采用数组实现,因此导致栈的大小是固定的,不易扩扩容,容易浪费空间同时还要注意元素溢出等问题.
链栈顾名思义就是采用链式方式存储,通常采用单向链表实现,因此链栈可以无限扩容,按需使用,内存利用高效,同时也不存在满栈的情况.
我们借助数组来实现顺序栈,其核心思想是把数组的起始位置作为栈底,把数组尾方向当作栈顶.
我们知道数组对插入、删除元素是不友好的,因为涉及到已存在元素移动的问题,但是如果直接在数组尾端插入、删除元素还是很方便的,因为不涉及元素移动问题,我们正是利用这一特点,把数组起始位置做为栈底,而插入、删除方便的数组尾端作为栈顶.
下面我们将一步一步实现一个泛型顺序栈.
我们首先来定义顺序栈的ADT.
ADT Stack{ 。
数据对象:D 是一个非空的元素集合,D = {a1, a2, ..., an},其中 ai 表示栈中的第i个元素,n是栈的长度。
数据关系:D中的元素通过它们的索引(位置)进行组织,索引是从0到n-1的整数,并且遵循元素只能在栈顶操作,元素后进先出的原则。
基本操作:[
Init(n) :初始化一个指定容量的空栈。
Capacity:返回栈容量。
Length:返回栈长度。
Top:返回栈顶元素,当为空栈则报异常。
IsEmpty():返回是否为空栈。
IsFull():返回是否为满栈。
Push():入栈即添加元素,当为满栈则报异常。
Pop():出栈即返回栈顶元素并把其从栈中移除,当为空栈则报异常。
] 。
} 。
定义好栈ADT,下面我们就可以开始自己实现的栈.
初始化结构主要做几件事.
初始化栈的容量; 。
初始化存放栈元素数组; 。
初始化栈顶索引; 。
具体实现代码如下:
//存放栈元素
private T[] _array;
//栈容量
private int _capacity;
//栈顶索引,为-1表示空栈
private int _top;
//初始化栈为指定容量
public MyselfArrayStack<T> Init(int capacity)
{
//初始化栈容量为capacity
_capacity = capacity;
//初始化指定长度数组用于存放栈元素
_array = new T[_capacity];
//初始化为空栈
_top = -1;
//返回栈
return this;
}
这个比较简单直接把栈容量私有字段返回即可.
//栈容量
public int Capacity
{
get
{
return _capacity;
}
}
因为栈顶索引表示数组下标,因此可以通过栈顶索引加1转为栈长度,同时因为我们定义了空栈是栈顶索引为-1,因此此时栈长等于[-1+1]为0,所以栈长度即为[栈顶索引+1].
//栈长度
public int Length
{
get
{
//栈长度等于栈顶元素加1
return _top + 1;
}
}
获取栈顶元素可以通过栈顶索引私有字段从数组中直接获取,同时要注意判断栈是否为空栈,如果为空栈则报异常。具体代码如下:
//获取栈顶元素
public T Top
{
get
{
if (IsEmpty())
{
//空栈,不可以进行获取栈顶元素操作
throw new InvalidOperationException("空栈");
}
return _array[_top];
}
}
是否空栈只需判断栈顶索引是否为小于0即可.
//是否空栈
public bool IsEmpty()
{
//栈顶索引小于0表示空栈
return _top < 0;
}
是否满栈只需判断栈顶索引是否与栈容量减1相等,代码如下:
//是否满栈
public bool IsFull()
{
//栈顶索引等于容量大小表示满栈
return _top == _capacity - 1;
}
入栈则是在把栈顶索引向数组后移动一位后,再把新元素赋值到栈顶索引所对应的元素上,同时还需要检查是否为满栈,如果是满栈则报错,具体实现代码如下:
//入栈
public void Push(T value)
{
if (IsFull())
{
//栈顶索引大于等于容量大小减1,表明已经满栈,不可以进行入栈操作
throw new InvalidOperationException("满栈");
}
//栈顶索引先向后移动1位,然后再存放栈顶元素
_array[++_top] = value;
}
出栈则是首先取出栈顶元素后,然后把栈顶索引向数组前移动一位,最后返回取出的栈顶元素,同时还需要检查是否为空栈,如果是空栈则报错,具体实现代码如下:
//出栈
public T Pop()
{
if (IsEmpty())
{
//栈顶索引小于1表示空栈,不可以进行出栈操作
throw new InvalidOperationException("空栈");
}
//返回栈顶元素后,栈顶索引向前移动1位
return _array[_top--];
}
我们借助链表来实现链栈,其核心思想是把链表尾节点作为栈底,把链表首元节点当作栈顶.
这是因为如果我们想拿到链表的尾节点需要变量整个链表才可以拿到,但是要想获取首元节点则可以通过头指针直接获取到(无头节点链表),因此对于链表尾节点来说操作时不友好的适合来做栈底,链表首元节点对操作友好适合做为栈顶.
下面我们将一步一步实现一个泛型链栈.
相对于顺序栈的ADT来说,链栈的ADT少了两个方法即获取栈容量和是否满栈,这也是链表特性带来的好处.
初始化结构主要初始化栈顶节点为空和栈长度为0,具体实现如下:
public class MyselfStackNode<T>
{
//数据域
public T Data;
//指针域,即下一个节点
public MyselfStackNode<T> Next;
public MyselfStackNode(T data)
{
Data = data;
Next = null;
}
}
public class MyselfStackLinkedList<T>
{
//栈顶节点即首元节点
private MyselfStackNode<T> _top;
//栈长度
private int _length;
//初始化栈
public MyselfStackLinkedList<T> Init()
{
//初始化栈顶节点为空
_top = null;
//初始化栈长度为0
_length = 0;
//返回栈
return this;
}
}
这个比较简单直接把栈长度私有字段返回即可.
//栈长度
public int Length
{
get
{
return _length;
}
}
获取栈顶元素可以通过栈顶节点直接获取,但是要注意判断栈是否为空栈,如果为空栈则报异常。具体代码如下:
//获取栈顶元素
public T Top
{
get
{
if (IsEmpty())
{
//空栈,不可以进行获取栈顶元素操作
throw new InvalidOperationException("空栈");
}
//返回首元节点数据域
return _top.Data;
}
}
是否空栈只需判断栈顶节点是否为空即可.
//是否空栈
public bool IsEmpty()
{
//栈顶节点为null表示空栈
return _top == null;
}
入栈则是首先创建一个新节点,然后把原栈顶节点赋值给新节点的指针域,最后把新节点变更为栈顶节点,同时栈长加1,具体实现代码如下:
//入栈
public void Push(T value)
{
//创建新的栈顶节点
var node = new MyselfStackNode<T>(value);
//将老的栈顶节点赋值给新节点的指针域
node.Next = _top;
//把栈顶节点变更为新创建的节点
_top = node;
//栈长度加1
_length++;
}
出栈则是首先取出栈顶节点对应的数据后,然后把栈顶节点指向原栈顶节点对应的下一个节点,同时栈长度减1,当然如果空栈则报错,具体实现代码如下:
//出栈
public T Pop()
{
if (IsEmpty())
{
//空栈,不可以进行出栈操作
throw new InvalidOperationException("空栈");
}
//获取栈顶节点数据
var data = _top.Data;
//把栈顶节点变更为原栈顶节点对应的下一个节点
_top = _top.Next;
//栈长度减1
_length--;
//返回栈顶数据
return data;
}
注:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner 。
最后此篇关于数据结构-栈的文章就讲到这里了,如果你想了解更多关于数据结构-栈的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
栈一种常见的特殊线性数据结构,其特殊之处在于其操作顺序,下面会详细介绍,也正因为其特性,因此栈可以轻松解决表达式求值、括号匹配、递归算法、回溯算法等等问题。 01、定义 栈的特殊性表现为操作受
目录 实践1 —— 从字符串中移除星号 栈和数组存储数据的方式一样,它们都只是元素的列表。不同之处在于栈的以下3个限制: 数据只能从栈末插入; 数据只
准备工作 工具:idea+jdk8 技术要求:java基础语法 编码环节 首先,我们得先确定下来,用什么数据来模拟栈的操作。由于是一个一个的元素放入栈里面,我们可以考虑用数组来实现。
0. 学习目标 栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有着巨大的不
在可以使用递归(在堆栈中存储状态)和对象创建(在堆中创建新对象)的场景中。 问题 在对象创建和递归之间进行选择时应考虑哪些参数? 我的研究得出以下结论(需要验证这一点) 当可用内存较少时:使用递归 可
下面是我编写的用于检查内存对齐的示例程序。 Pavan@Pavan-pc:~/working_dir/pavan/C$ cat mem3.c #include #include
Instapaper 和 Twitterrific 等应用启动的 View 不是其导航堆栈的 Root View 。我们知道这一点,因为初始 View 已经有一个后退按钮。 Instapaper 推出
有没有办法在调试或正常运行期间的某个时刻可视化 Activity 堆栈? 最佳答案 您可以通过 Activity 管理器获取一些有用的信息。 ActivityManager manag
我想编写一个应用层协议(protocol),在发送 GET 请求时使用 TCP 返回特定的 ASCII 文本。我读了第一HTTP specification和 the SMTP specificati
1、堆和栈的速度性能分析 堆和栈是jvm内存模型中的2个重要组成部分,自己很早以前也总结过堆和栈的区别,基本都是从存储内
一: 概念 栈,同样是一种特殊的线性表,是一种last in first out(lifo)的形式,现实中有很多这样的例子,
java中stack类继承于vector,其特性为后进先出(lastinfirstout). 入栈和出栈实例图: 实例图的java代码实例: ?
1、单链表 1、在我们数据结构中,单链表非常重要。它里面的数据元素是以结点为单位,每个结点是由数据元素的数据和下一个结点的地址组成,在java集合框架里面 LinkedList、Ha
本文实例讲述了Python编程实现双链表,栈,队列及二叉树的方法。分享给大家供大家参考,具体如下: 1.双链表 ?
我一遍又一遍地阅读定义,但我仍然不明白ARM中的SP和LR是什么?我了解PC(它显示下一条指令的地址),SP和LR可能类似,但我只是不明白它是什么。你能帮我一下吗? 编辑:如果你能用例子来解释它,那就
我必须使用索引 0 作为堆栈的顶部,并且在实现此操作时遇到问题。我得到了所有 null,但输出 100、200 和 300 是我得到的唯一数字。我忽略的实现有什么问题吗? push 方法应该实现 Ar
我正在用 Java 解决汉诺塔问题。我选择使用 Stacks 作为钉子,除了 move 方法之外,一切都正常。我有规范和 JUnit 测试类,目前通过了 7 项测试中的 6 项,但在移动测试中失败了。
这个问题在这里已经有了答案: 关闭 11 年前。 Possible Duplicate: Does this type of memory get allocated on the heap or
首先,抱歉我的英语不好。我将尝试解释我的问题: 我有一个 RootViewController(基于导航的项目)。因此,它显示了表格 View ,当用户选择表格的一行 (didSelectRowAtI
我有一个看起来像这样的类 class A { int b; void B() { int c; } } int main() { A asdf;
我是一名优秀的程序员,十分优秀!