首页 > 代码库 > 第四篇 栈与队列（一）
第四篇 栈与队列（一）
一、栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表；栈又称为后进先出的线性表（LIFO）。
栈顶：允许插入和删除操作的一端称为栈顶；而另一端则为栈底。
栈的操作：插入数据称为进栈（压栈、入栈）；栈的删除操作称为出栈（弹栈）。
如下图所示：
二、栈的抽象数据类型
栈是一种特殊的线性表，因此具有线性表的所有特性。如除根节点以外，有且仅有一个前驱节点等。
三、栈的顺序存储结构及实现
C#代码实现
/// <summary> /// 栈的顺序存储结构 /// </summary> /// <typeparam name="T"></typeparam> public class SequenceStoregeStackt<T> { //栈的最大空间 private int _maxSize; //栈顶指针 private int _top; //栈的数据用数据进行存储 private T[] _storage; public SequenceStoregeStackt(int maxSize) { _maxSize = maxSize; _storage = new T[maxSize]; } /// <summary> /// 判断栈是否为空 /// </summary> /// <returns></returns> public bool IsEmpty() { return _top == -1; } /// <summary> /// 添加元素 /// 栈只能从栈顶添加元素 /// </summary> /// <param name="t">添加的元素</param> public void Push(T t) { if (_top == _maxSize - 1) throw new ApplicationException("The stack is full."); //将元素添加到栈顶 _storage[_top + 1] = t; //将栈顶指针+1 _top++; } /// <summary> /// 取出栈顶元素 /// </summary> public T Pop() { T t = default(T); if (!IsEmpty()) { t = _storage[_top]; _top--; } return t; } }四、栈的链式存储结构
C#代码实现
/// <summary> /// 栈的链式结构实现 /// </summary> public class LinkedStack<T> { /// <summary> /// 栈的指针 /// </summary> private Node<T> _top; /// <summary> /// 栈的长度 /// </summary> public int Length { get; set; } public LinkedStack() { } /// <summary> /// 判断栈是否为空 /// </summary> /// <returns></returns> public bool IsEmpty() { return _top == null; } /// <summary> /// 插入元素 /// </summary> /// <param name="t"></param> public void Push(T t) { //栈的连式存储只有在内存满了，才会添加失败 Node<T> node = new Node<T>(); node.t = t; //将当前的栈顶元素赋值给新节点的直接后继 node.NextNode = _top; //将新的节点赋给栈顶指针 _top = node; //将栈的长度+1 Length++; } /// <summary> /// 取出栈顶元素 /// </summary> /// <returns></returns> public T Pop() { T t = default(T); if (!IsEmpty()) { //取得栈顶元素 Node<T> node = _top; //取得值 t = node.t; //修改栈顶指针 _top = _top.NextNode; //修改栈长度 Length--; } return t; } } /// <summary> /// 栈的元素 /// </summary> /// <typeparam name="T"></typeparam> public class Node<T> { /// <summary> /// 栈的数据元素 /// </summary> public T t { get; set; } /// <summary> /// 下一节点指针 /// </summary> public Node<T> NextNode { get; set; } }五、栈的应用之递归
斐波那契数列【具体解释参考百度百科】
斐波那契数列数学表示：
C#代码实现
/// <summary> /// 斐波那契数列实现 /// </summary> public class FibonacciDemo { /// <summary> /// 递归实现 /// </summary> /// <param name="value">输入的数列项</param> /// <returns></returns> public int Execute(int value) { if (value < 2) return 1; return Execute(value - 1) + Execute(value - 2); } /// <summary> /// 斐波那契的循环实现 /// </summary> /// <param name="value"></param> /// <returns></returns> public int LoopExecute(int value) { int[] arr = new int[value]; if (value =http://www.mamicode.com/= 0)>六、栈的应用之四则运算
后缀表达式（逆波兰）
第四篇 栈与队列（一）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。