C#数据结构【栈与队列】

栈和队列

栈(后进先出/先进后出)

定义:

栈是操作限定在表的尾端进行的线性表。表尾由于要进行插入、删除等操作，所以，它具有特殊的含义，把表尾称为栈顶（ Top），另一端是固定的，叫栈底（ Bottom）。当栈中没有数据元素时叫空栈(Empty Stack)

删除栈元素的方式是：例如a1，需要将a1以上的 元素先移除出去，才能移除a1

使用BCL

在BCL(基本类库)中提供了泛型的Stack类【C#2.0开始】

主要方法如下

1.Push()入栈（添加数据）

2.Pop()出栈（删除栈顶数据，返回被删除的数据）

3.Peek()取栈顶数据（取得栈顶的数据，不删除）

4.Clear()清空所有数据

5.count取得栈中数据的个数

栈的基本使用【代码】

//使用BCL中的Stack<T>
Stack<string> stack = new Stack<string>();
stack.Push("abc");
stack.Push("def");
stack.Push("ghi");//栈顶数据
Console.WriteLine("栈的大小:"+stack.Count);
Console.WriteLine("--------------------------------------------");
string temp= stack.Pop();//取得栈顶数据，并把栈顶数据删除
Console.WriteLine("Pop后的栈顶数据是:"+temp);
Console.WriteLine("Pop后的栈中的数据个数:"+stack.Count);
Console.WriteLine("--------------------------------------------");
string tempTwo = stack.Peek();//取得栈顶数据，但不会将栈顶数据删除
Console.WriteLine("Peek后的栈顶数据是:" + tempTwo);
Console.WriteLine("Peek后的栈中的数据个数:" + stack.Count);
Console.WriteLine("--------------------------------------------");
Console.WriteLine("判断栈是否存在相关数据:" + stack.Contains("abc"));
stack.Clear();
Console.WriteLine("Clear后的栈中的数据个数:" + stack.Count);
Console.WriteLine("--------------------------------------------");
Console.WriteLine("判断栈是否存在相关数据:"+stack.Contains("abc"));
//当栈内为空栈时切勿进行Peek()或者Pop()操作，否则会报错
Console.ReadLine();

控制台输出:

栈的大小:3
--------------------------------------------
Pop后的栈顶数据是:ghi
Pop后的栈中的数据个数:2
--------------------------------------------
Peek后的栈顶数据是:def
Peek后的栈中的数据个数:2
--------------------------------------------
判断栈是否存在相关数据:True
Clear后的栈中的数据个数:0
--------------------------------------------
判断栈是否存在相关数据:False

代码实现

创建接口 IStackDS

public interface IStackDS<T>
   {
       int Count { get; }//栈的大小
       int GetLength();//栈的长度
       bool isEmpty();//判断栈是否为空
       void Clear();//清空操作
       void Push(T item); //入栈操作
       T Pop(); //出栈操作
       T Peek(); //取栈顶元素

   }

顺序栈【第一种存储方式】（用一片连续的存储空间来存储栈中的数据元素(使用数组)）

用一维数组来存放顺序栈中的数据元素。栈顶指示器 top 设在数组下标为 0 的端， top 随着插入和删除而变化，当栈为空时，top=-1。下图是顺序栈的栈顶指示器 top 与栈中数据元素的关系图。

创建 SeqStack

public class SeqStack<T> : IStackDS<T>
   {
       private T[] data;
       private int top;
       public SeqStack(int size) {
           data = new T[size];
           top = -1;
       }
       public SeqStack() : this(15){

       }
       public int Count {
           get  {
               //栈顶+1
               return top + 1;
           }
       }
       public void Clear() {
           top = -1;
       }
       public int GetLength() {
           return Count;
       }
       public bool isEmpty() {
           return Count == 0;
       }
       public T Peek() {
           return data[top];
       }
       //出栈
       public T Pop() {
           T temp=data[top];
           top--;
           return temp;
       }
       //入栈
       public void Push(T item) {
           data[top+1] = item;
           top++;
       }
   }

测试相关方法

Console.WriteLine("使用自定义顺序栈");
           IStackDS<string> newstack = new SeqStack<string>();
           newstack.Push("123");
           newstack.Push("456");
           newstack.Push("789");//栈顶数据
           Console.WriteLine("栈的大小:" + newstack.Count);
           Console.WriteLine("--------------------------------------------");
           string newtemp = newstack.Pop();//取得栈顶数据，并把栈顶数据删除
           Console.WriteLine("Pop后的栈顶数据是:" + newtemp);
           Console.WriteLine("Pop后的栈中的数据个数:" + newstack.Count);
           Console.WriteLine("--------------------------------------------");
           string newtempTwo = newstack.Peek();//取得栈顶数据，但不会将栈顶数据删除
           Console.WriteLine("Peek后的栈顶数据是:" + newtempTwo);
           Console.WriteLine("Peek后的栈中的数据个数:" + newstack.Count);
           Console.WriteLine("--------------------------------------------");
           stack.Clear();
           Console.WriteLine("Clear后的栈中的数据个数:" + newstack.Count);
           Console.ReadLine();

控制台输出:

使用自定义顺序栈
栈的大小:3
--------------------------------------------
Pop后的栈顶数据是:789
Pop后的栈中的数据个数:2
--------------------------------------------
Peek后的栈顶数据是:456
Peek后的栈中的数据个数:2
--------------------------------------------
Clear后的栈中的数据个数:2

链栈 【第二种实现方式】(用单链表来表示，它的实现是单链表的简化,链栈结点的结构与单链表结点的结构一样)

注意：链栈的操作只是在一端进行，为了操作方便，把栈顶设在链表的头部，并且不需要头结点

把链栈看作一个泛型类，类中有一个字段 top 表示栈顶指示器。由于栈只能访问栈顶的数据元素，而链栈的栈顶指示器又不能指示栈的数据元素的个数。所以，求链栈的长度时，必须把栈中的数据元素一个个出栈，每出栈一个数据元素，计数器就增加 1，但这样会破坏栈的结构。为保留栈中的数据元素，需把出栈的数据元素先压入另外一个栈，计算完长度后，再把数据元素压入原来的栈。但这种算法的空间复杂度和时间复杂度都很高，所以，以上两种算法都不是理想的解决方法。理想的解决方法是 LinkStack类增设一个字段 num 表示链栈中结点的个数。

创建链栈结点

/// <summary>
    /// 链栈的节点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class Node<T>
    {
        private T data;//数据
        private Node<T> next;
        public Node() {
            Data=default(T);
            Next=null;
        }
        public Node(T data) {
            this.Data = data;
            Next = null;
        }
        public Node(Node<T> next) {
            this.Next=next;
            this.Data=default(T);
        }
        public Node(T data, Node<T> next) {
            this.Data=data;
            this.Next = next;
        }
        public T Data { get => data; set => data = value; }
        internal Node<T> Next { get => next; set => next = value; }
    }

创建链栈

public class LinkStack<T> : IStackDS<T>
    {
        private Node<T> top;//栈顶元素的结点
        private int count;//栈中的元素个数
        public int Count {
            get { return count; }
        }
        public int GetLength() {
            return count;
        }
        /// <summary>
        /// 清空栈中所有的数据
        /// </summary>
        public void Clear() {
            count = 0;
            top= null;
        }
        /// <summary>
        /// 判断栈中是否有数据，即是否为空栈
        /// </summary>
        /// <returns></returns>
        public bool isEmpty() {
            return count == 0;
        }
        /// <summary>
        /// 取得栈顶中的数据，但不进行删除栈顶
        /// </summary>
        /// <returns></returns>
        public T Peek() {
            return top.Data;
        }
        /// <summary>
        /// 出栈，取得栈顶元素，并且删除
        /// </summary>
        /// <returns></returns>
        public T Pop() {
            T data = top.Data;
            top = top.Next;
            return data;
        }
        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="item"></param>
        public void Push(T item) {
            //把新添加的元素作为头结点（栈顶）
            Node<T> newNode = new Node<T>(item);
            newNode.Next = top;
            top = newNode;
            count++;
        }
    }

测试相关方法

Console.WriteLine("使用代码实现链栈");
          IStackDS<string> newLinkStack=new LinkStack<string>();
           newLinkStack.Push("西游记");
           newLinkStack.Push("三国演义");
           newLinkStack.Push("红楼梦");
           newLinkStack.Push("水浒传");//栈顶数据
           Console.WriteLine("栈的大小:" + newLinkStack.Count);
           Console.WriteLine("--------------------------------------------");
           string newLinktemp = newLinkStack.Pop();//取得栈顶数据，并把栈顶数据删除
           Console.WriteLine("Pop后的栈顶数据是:" + newLinktemp);
           Console.WriteLine("Pop后的栈中的数据个数:" + newLinkStack.Count);
           Console.WriteLine("--------------------------------------------");
           string newLinktempTwo = newLinkStack.Peek();//取得栈顶数据，但不会将栈顶数据删除
           Console.WriteLine("Peek后的栈顶数据是:" + newLinktempTwo);
           Console.WriteLine("Peek后的栈中的数据个数:" + newLinkStack.Count);
           Console.WriteLine("--------------------------------------------");
           newLinkStack.Clear();
           Console.WriteLine("Clear后的栈中的数据个数:" + newLinkStack.Count);
           Console.WriteLine("--------------------------------------------");
           //当栈内为空栈时切勿进行Peek()或者Pop()操作，否则会报错

控制台输出:

使用代码实现链栈
栈的大小:4
--------------------------------------------
Pop后的栈顶数据是:水浒传
Pop后的栈中的数据个数:4
--------------------------------------------
Peek后的栈顶数据是:红楼梦
Peek后的栈中的数据个数:4
--------------------------------------------
Clear后的栈中的数据个数:0
--------------------------------------------

队列(先进先出，后进后出)

定义

队列(Queue)是插入操作限定在表的尾部而其它操作限定在表的头部进行的线性表。把进行插入操作的表尾称为队尾(Rear)，把进行其它操作的头部称为队头(Front)。当队列中没有数据元素时称为空队列(Empty Queue)。

使用BCL

主要方法

1，Enqueue()入队(放在队尾)
2，Dequeue()出队(移除队首元素，并返回被移除的元素)
3，Peek()取得队首的元素，不移除
4，Clear()清空元素

主要属性

1，Count获取队列中元素的个数

使用BCL的队列

Console.WriteLine("************使用BCL的队列************");
//创建队列
Queue<string> queue = new Queue<string>();
//将数据存储到队尾部分，即入队
queue.Enqueue("王者荣耀");//队首
queue.Enqueue("和平精英");
queue.Enqueue("使命召唤M");
Console.WriteLine("加入完三个游戏名称后的队列大小为:"+queue.Count);
//Dequeue含义是出队，取得队首的数据后，并删除该数据
var tempOne=queue.Dequeue();
Console.WriteLine("取得队首的数据为:"+tempOne);
Console.WriteLine("出队之后的队列大小为:"+queue.Count);
var tempTwo = queue.Peek();
Console.WriteLine("取得队首的数据为:" + tempTwo);
Console.WriteLine("Peek之后的队列大小为:" + queue.Count);
queue.Clear();
Console.WriteLine("Clear之后的队列大小为:"+queue.Count);
Console.WriteLine("---------------------------------------");

控制台输出

************使用BCL的队列************
加入完三个游戏名称后的队列大小为:3
取得队首的数据为:王者荣耀
出队之后的队列大小为:2
取得队首的数据为:和平精英
Peek之后的队列大小为:2
Clear之后的队列大小为:0
---------------------------------------

代码实现

定义IQueue接口

public interface IQueue<T> {
        int Count{get;}//取得队列长度的属性
        int GetLength(); //求队列的长度
        bool IsEmpty(); //判断对列是否为空
        void Clear(); //清空队列
        void Enqueue(T item); //入队
        T Dequque(); //出队
        T Peek(); //取队头元素
}

顺序队列（用一片连续的存储空间来存储队列中的数据元素）

用一维数组来存放顺序队列中的数据元素。队头位置设在数组下标为 0 的端，用 front 表示；队尾位置设在数组的另一端，用 rear 表示。 front 和 rear 随着插入和删除而变化。当队列为空时， front=rear=-1。如下图

创建SeqQueue

class SeqQueue<T> : IQueue<T>
   {
       private T[] data;
       private int count;//当前元素数量
       private int front;//队首==>队首元素索引-1
       private int rear;//队尾==>队尾元素索引
       public SeqQueue(int size) {
           data = new T[size];
           count = 0;
           front = -1;
           rear = -1;
       }
       public SeqQueue() : this(10) {

       }
       public int Count {
           get { return count; }
       }
       public void Clear() {
           count =0;
           front = rear = -1;
       }
       public T Dequque()
       {
           if (count> 0) {
               T temp=data[front+1];
               front++;
               count--;
               return temp;
           }
           else {
               Console.WriteLine("队列为空，无法取得队首的数据");
               return default(T);
           }
       }

       public void Enqueue(T item)
       {
           if (count == data.Length){
               Console.WriteLine("队列已满，不可以再添加新的数据");
           }
           else{
               if (rear == data.Length - 1) {
                   data[0] = item;
                   rear = 0;
                   count++;
               }
               else{
                   data[rear + 1] = item;
                   rear++;
                   count++;
               }
           }
       }
       public int GetLength(){
           return count;
       }
       public bool IsEmpty(){
           return count == 0;
       }
       public T Peek(){
           T temp = data[front+ 1];
           return temp;
       }
   }

测试代码

Console.WriteLine("************使用代码实现顺序队列************");
            //创建队列
            SeqQueue<string> seqQueue = new SeqQueue<string>();
            //将数据存储到队尾部分，即入队
            seqQueue.Enqueue("牛魔");//队首
            seqQueue.Enqueue("典韦");
            seqQueue.Enqueue("女娲");
            Console.WriteLine("加入完三个游戏名称后的队列大小为:" + seqQueue.Count);
            //Dequeue含义是出队，取得队首的数据后，并删除该数据
            var tempseqQueueOne = seqQueue.Dequque();
            Console.WriteLine("取得队首的数据为:" + tempseqQueueOne);
            Console.WriteLine("出队之后的队列大小为:" + seqQueue.Count);
            var tempseqQueueTwo = seqQueue.Peek();
            Console.WriteLine("取得队首的数据为:" + tempseqQueueTwo);
            Console.WriteLine("Peek之后的队列大小为:" + seqQueue.Count);
            seqQueue.Clear();
            Console.WriteLine("Clear之后的队列大小为:" + seqQueue.Count);
            Console.WriteLine("---------------------------------------");

控制台输出

************使用代码实现顺序队列************
加入完三个游戏名称后的队列大小为:3
取得队首的数据为:牛魔
出队之后的队列大小为:2
取得队首的数据为:典韦
Peek之后的队列大小为:2
Clear之后的队列大小为:0
---------------------------------------