栈的简介

栈是一种线性的逻辑结构，可依赖数组和链表这两种物理结构实现，是一种FILO的结构。以下是生活中遇到的栈的结构：

 

 

 

栈的形式化定义为

栈(Stack)简记为 S，是一个二元组，顾定义为S = (D, R)
其中：D 是数据元素的有限集合；
R 是数据元素之间关系的有限集合。

 

栈顶指针保存栈索引的下标，因此空栈时候top=-1

栈分为：顺序栈( 用数组来保存) 和链栈

 

栈的 基本操作

由于栈只能在栈顶进行操作， 所以栈不能在栈的任意一个元素处插入或删除元素。因此，栈的操作是线性表操作的一个子集。栈的操作主要包括在栈顶插入元素和删除元素、取栈顶元素和判断栈是否为空等等方面的操作。

count\Empty\Full\Push\Pop\Peek

有几种出栈顺序（考题）

 

 

 

顺序栈

自定义顺序栈  源代码如下：

using System; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Drawing.Drawing2D; using System.IO; using System.Text; using System.Threading; using System.Xml; using System.Xml.XPath; namespace LinearList; public class Sample {     public  struct SequencedStack<T> {         private T[] itme;         private const int Empty = -1;         public int Top { get; set; } = Empty;         public bool IsEmpty { get=> Top==Empty;  }           public bool Full{ get=>Top==itme.Length-1; }         public int Count{ get=>Top +1; }           public SequencedStack() : this(16)         {                       }         public SequencedStack(int n)         {             itme = new T[2];                   }         public void Push(T k)         {             if (Full)             {                 DoubleCapacity();             }             itme[++Top] = k;         }         public T Pop()         {             if (IsEmpty) throw new InvalidOperationException();             return itme[Top--];              }         public T Peek()         {             if (IsEmpty) throw new InvalidOperationException();             return itme[Top];          }         private void DoubleCapacity()         {                             T[] newitme = new T[itme.Length * 2];                 itme.CopyTo(newitme, 0);                 itme = newitme;//数组是引用类型                      }         public void Print()         {             if (IsEmpty) throw new InvalidOperationException();           //  Array.ForEach(itme, it => Console.WriteLine(it) );           for(int i = Top; i >=0; i--)             {                 Console.WriteLine(itme[i]);             }         }         public override string ToString()         {             StringBuilder stringBuilder = new StringBuilder();             for (int i = Top; i >= 0; i--)             {                 stringBuilder.Append(itme[i]);             }             return stringBuilder.ToString();          }     }       static void Main()     {  SequencedStack<int> sequencedStack = new  ();         for (int i = 0; i <5; i++)         {             sequencedStack.Push(1);         }         sequencedStack.Print();         Console.WriteLine(  );     }       }

View Code

 链栈

 

 链栈等于线性链表结构，但是只能在链表头进行增删操作。因此链栈可以有两种实现方式一种是带链头的栈，一种是不带头的栈，

 自定义链栈，基于链表结构，源代码如下

using System; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Drawing.Drawing2D; using System.IO; using System.Text; using System.Threading; using System.Xml; using System.Xml.XPath; namespace LinearList; public class Sample {     public static void Main()     {                }     public class Node<T>     {         private T? item;         private Node<T>? next;          public T? Item { get => item; set => item = value; }         public Node<T>? Next { get => next; set => next = value; }          public Node(T value)         {             item = value;          }         public Node()         {          }          public override string ToString()         {             return item.ToString();         }      }     //读取时线程安全     public class NodeList<T> where T : notnull     {          public Node<T> Head;          private int length;         [ThreadStatic] private static Node<T> currntNode;         public virtual Node<T> CurrntNode         {             get             {                 if (Head.Next == null) currntNode = Head;                   return currntNode;             }             set             {                 currntNode = value;             }         }         /// <summary>         /// 构造头节点，他是开始的标志         /// </summary>         public NodeList()         {             Head = new Node<T>();             currntNode = new();             CurrntNode = Head;         }         public NodeList(Node<T> firstnode) : this()         {             Head.Next = firstnode;         }         public NodeList(T[] array) : this()         {              for (int i = 0; i < array.Length; i++)             {                  Node<T> node = new(array[i]);                  CurrntNode.Next = node;                 if (i == 0) Head.Next = node;                 CurrntNode = CurrntNode.Next;             }           }           /// <summary>         ///  列表长度 ,为了方便循环单向链表 继承后修改改方法，所以改方法设置成virtual          /// </summary>          public virtual int Length         {             get             {                  Node<T>? node = Head;                 length = 0;                 while (node != null)                 {                     node = node.Next;                     length++;                 }                 return length;             }              set => length = value;         }         /// <summary>         /// 添加数据项 ,为了方便循环单向链表 继承后修改改方法，所以改方法设置成virtual          /// </summary>         /// <param name=item></param>         public virtual void Add(T item)         {             Node<T> newNOde = new(item);             if (CurrntNode == null) { CurrntNode = new(); CurrntNode = newNOde; Head = newNOde; }             else             {                 CurrntNode.Next = newNOde;                 CurrntNode = CurrntNode.Next;              }           }         /// <summary>         /// 输出完整的列表         /// </summary>         public void Print()         {             if (Head.Next != null) CurrntNode = Head.Next;              while (CurrntNode != null)             {                  Console.WriteLine(CurrntNode.Item);                 CurrntNode = CurrntNode.Next;             }         }         /// <summary>         /// 是否是空列表         /// </summary>         public virtual bool IsEmpty { get { return Head.Next == null; } }              /// <summary>         /// suo'y         /// </summary>         /// <param name=item></param>         /// <returns></returns>         /// <exception cref=IndexOutOfRangeException></exception>         public virtual T this[int item]         {             get             {                 if (item < 0) throw new IndexOutOfRangeException();                 if (Head.Next == null) throw new IndexOutOfRangeException();                 CurrntNode = Head.Next;                 int n = 0;                 while (n != item)                 {                     CurrntNode = CurrntNode.Next;                     n++;                 }                 return CurrntNode.Item;             }             set             {                 CurrntNode = Head.Next;                 int n = 0;                 while (n != item)                 {                     CurrntNode = CurrntNode.Next;                     n++;                 }                 CurrntNode.Item = value;             }         }          public override string ToString()         {             if (Head == null) return string.Empty;             CurrntNode = Head;              StringBuilder str = new();             while (CurrntNode != null)             {                  str.Append(CurrntNode.Item +  );                 CurrntNode = CurrntNode.Next;             }             return str.ToString();         }         /// <summary>         /// 在指定的索引位置之后插入元素 ,为了方便循环单向链表 继承后修改改方法，所以改方法设置成virtual          /// </summary>         /// <param name=index>索引位置</param>         /// <param name=item></param>         /// <exception cref=IndexOutOfRangeException></exception>         public virtual void Insert(int index, T item)         {             Node<T> node = new(item);             if (index < 0 || index > Length) throw new IndexOutOfRangeException();              CurrntNode = Head;              Node<T> nextnode = CurrntNode.Next;              int i = 0;             while (CurrntNode != null)             {                 if (i == index)                 {                     break;                 }                 CurrntNode = nextnode;                 nextnode = nextnode.Next;                 i++;             }                node.Next = CurrntNode!.Next;             CurrntNode.Next = node;           }         /// <summary>         ///  在队列的末尾添加 数据元素         /// </summary>         /// <param name=item></param>         public virtual void Append(T item)         {             Node<T> node = new(item);             if (Head == null) { Head = node; return; }             CurrntNode = Head;              Node<T> nextnode = CurrntNode.Next;             while (nextnode != null)             {                 CurrntNode = nextnode;             }             CurrntNode.Next = node;          }         /// <summary>         ///  删除出现item的数据元素           /// </summary>         /// <param name=item></param>         public void Remove(T item)         {              if (Head == null) { throw new ArgumentOutOfRangeException(nameof(item)); }             CurrntNode = Head;              Node<T> nextnode = CurrntNode.Next;             if (CurrntNode.Item.Equals(item)) { Head = nextnode; }              while (nextnode != null)             {                 if (nextnode.Item.Equals(item))                 {                     CurrntNode.Next = nextnode.Next;                     return;                 }                 CurrntNode = nextnode;                 nextnode = nextnode.Next;             }              Console.WriteLine(未找到删除的元素);           }         /// <summary>         /// 删除指定索引的元素         /// </summary>         /// <param name=i></param>         /// <exception cref=IndexOutOfRangeException></exception>         public void RemoveAt(int i)         {             if (Head == null || i < 0 || i > Length) { throw new IndexOutOfRangeException(); }             if (i == 0) { Head = null; return; }             CurrntNode = Head;              Node<T> nextnode = CurrntNode.Next;             int n = 0;              while (nextnode != null)             {                 if (i - 1 == n)                 {                     CurrntNode.Next = nextnode.Next;                     return;                 }                 CurrntNode = nextnode;                 nextnode = nextnode.Next;                 n++;             }             if (Length == i) { CurrntNode = null; return; }             Console.WriteLine(未找到删除的元素);         }         public void Reverse()         {             if (Head.Next == null) return;             CurrntNode = Head.Next;              Node<T> nextnode = CurrntNode.Next;              Node<T> prenode;             int n = 0;             while (nextnode != null)             {                  prenode = CurrntNode;                 if (n == 0) prenode.Next = null;                  CurrntNode = nextnode;                  nextnode = nextnode.Next;                 CurrntNode.Next = prenode;                    n++;              }              Head.Next = CurrntNode;         }      }     public class LinkedStack<T>: NodeList<T>     {         private Node<T> top;         public Node<T> Top { get => top; set => top = value; }         public LinkedStack():base()         {             top = base.Head.Next;//          }         public override bool IsEmpty =>top ==null;         public void Push(T n )         {                          Node<T> node= new Node<T>(n);             node.Next = top;             base.Head.Next = node;          }         public T Pop()         {                       if (IsEmpty) throw new InvalidOperationException(Stack Is Empty+this.GetType());           T node =  top.Item ;             top = top.Next;             Head.Next = top;                                    return node;          }         public T Peek()         {             if (!IsEmpty)                 return top.Item;             else throw new InvalidOperationException();         }            } }

View Code

 

 

共享栈

 

栈的应用

1、基于栈结构的函数嵌套调用。（P88 C#数据结构与算法）

例如，执行函数A时，函数A中的某语句又调用函数B，系统要做一些列的如下操作：

（1）将调用函数的下一条语句作为返回地址信息保存在栈中，该过程称为保护现场。

（2）将函数A调用函数B的实参保存在栈中，该过程称为实参压栈。

（3）控制交给函数B，在栈中分配函数B的局部变量，然后开始执行函数B内的其他语句

函数B执行完成时，系统则要做一系列的如下出栈操作才能保证系统控制返回到调用函数B的函数中：

（1）退回栈中为函数B的局部变量分配的空间

（2）退回栈中为函数B的参数 分配的空间

（3）取出保存在栈中的返回地址信息，该过程称作现场恢复，程序继续运行函数的A的其他语句