数据结构（C#版）栈和队列

谁践踏了优雅 2022-03-10 09:11 252阅读 0赞

**栈和队列**

栈和队列是非常重要的两种数据结构，在软件设计中应用很多。栈和队列也是线性结构，线性表、栈和队列这三种数据结构的数据元素以及数据元素间的逻辑关系完全相同，差别是线性表的操作不受限制，而栈和队列的操作受到限制。栈的操作只能在表的一端进行，队列的插入操作在表的一端进行而其它操作在表的另一端进行，所以，把栈和队列称为操作受限的线性表。

**栈**

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

栈通常记为： S= (a1,a2,…,an)，S是英文单词stack的第 1 个字母。a1为栈底元素，an为栈顶元素。这n个数据元素按照a1,a2,…,an的顺序依次入栈，而出栈的次序相反，an第一个出栈，a1最后一个出栈。所以，栈的操作是按照后进先出(Last In First Out，简称LIFO)或先进后出(First In Last Out，简称FILO)的原则进行的，因此，栈又称为LIFO表或FILO表。栈的操作示意图如图所示。

![20190310152049781.png][]

**BCL中的栈**

C\#2.0 一下版本只提供了非泛型的Stack类(存储object类型)

C\#2.0 提供了泛型的Stack<T>类

重要的方法如下

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

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

3,Peek()取得栈顶的数据，不删除

4,Clear()清空所有数据

5,Count取得栈中数据的个数

**栈的接口定义**

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _002_栈和队列
    {
        interface IStackDS<T>
        {
            int Count { get; }//get data number
            int GetLength();
            bool IsEmpty();
            void Clear();
            void Push(T item);
            T Pop();
            T Peek();
        }
    }

**顺序栈的定义**

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _002_栈和队列
    {
        class SeqStack<T> : IStackDS<T>
        {
            private T[] data;
            private int top;
    
            public SeqStack(int size)
            {
                data = new T[size];
                top = -1;
            }
    
            public SeqStack():this(10)
            {
            }
    
            public int Count
            {
                get
                {
                    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++;
            }
        }
    }

结果验证

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _002_栈和队列
    {
        class Program
        {
            static void Main(string[] args)
            {
                //使用自己的栈
                IStackDS<char> stack = new SeqStack<char>(30);
                stack.Push('a');
                stack.Push('b');
                stack.Push('c');
                Console.WriteLine("push a b c之后的数据个数为:" + stack.Count);
                char temp = stack.Pop();
                Console.WriteLine("Pop之后得到的数据是:" + temp);
                Console.WriteLine("Pop之后数据的个数是:" + stack.Count);
                char temp2 = stack.Peek();
                Console.WriteLine("Peek之后得到的数据是:" + temp2);
                Console.WriteLine("Peek之后数据的个数:" + stack.Count);
            }
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70][]

**栈的存储和代码实现**

栈的另外一种存储方式是链式存储，这样的栈称为链栈(Linked Stack)。链栈通常用单链表来表示，它的实现是单链表的简化。所以，链栈结点的结构与单链表结点的结构一样，如图 3.3 所示。由于链栈的操作只是在一端进行，为了操作方便，把栈顶设在链表的头部，并且不需要头结点。

**链栈-代码实现**

![20190311192508739.png][]

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

**链栈的定义（节点和链栈）**

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _002_栈和队列
    {
        /// <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(T data,Node<T> next)
            {
                this.data = data;
                this.next = next;
            }
    
            public Node(Node<T> next)
            {
                this.next = next;
                data = default(T);
            }
    
            public T Data
            {
                get
                {
                    return data;
                }
                set
                {
                    data = value;
                }
            }
    
            public Node<T> Next
            {
                get
                {
                    return next;
                }
                set
                {
                    next = value;
                }
            }
        }
    }

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _002_栈和队列
    {
        class LinkStack<T> : IStackDS<T>
        {
            private Node<T> top;//栈顶元素结点
            private int count = 0;//栈中元素的个数
    
            public int Count
            {
                get
                {
                    return count;
                }
            }
    
            public void Clear()
            {
                count = 0;
                top = null;
            }
    
            public int GetLength()
            {
                return count;
            }
    
            public bool IsEmpty()
            {
                return count == 0;
            }
    
            public T Peek()
            {
                return top.Data;
            }
    
            public T Pop()
            {
                T temp = top.Data;
                top = top.Next;
                count--;
                return temp;
            }
    
            public void Push(T item)
            {
                //把新添加的元素作为栈顶元素结点
                Node<T> newNode = new Node<T>(item);
                newNode.Next = top;
                top = newNode;
                count++;
            }
        }
    }

验证我们的链栈

LinkStack<char> stack = new LinkStack<char>();
                stack.Push('a');
                stack.Push('b');
                stack.Push('c');
                Console.WriteLine("push a b c之后的数据个数为:" + stack.Count);
                char temp = stack.Pop();
                Console.WriteLine("Pop之后得到的数据是:" + temp);
                Console.WriteLine("Pop之后数据的个数是:" + stack.Count);
                char temp2 = stack.Peek();
                Console.WriteLine("Peek之后得到的数据是:" + temp2);
                Console.WriteLine("Peek之后数据的个数:" + stack.Count);

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 1][]

**队列**

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

队列通常记为： Q= (a1,a2,…,an)，Q是英文单词queue的第 1 个字母。a1为队头元素，an为队尾元素。这n个元素是按照a1,a2,…,an的次序依次入队的，出对的次序与入队相同，a1第一个出队，an最后一个出队。所以，对列的操作是按照先进先出(First In First Out)或后进后出( Last In Last Out)的原则进行的，因此，队列又称为FIFO表或LILO表。队列Q的操作示意图如图所示。在实际生活中有许多类似于队列的例子。比如，排队取钱，先来的先取，后来的排在队尾。

队列的操作是线性表操作的一个子集。队列的操作主要包括在队尾插入元素、在队头删除元素、取队头元素和判断队列是否为空等。与栈一样，队列的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在物理存储结构层次上的。因此，把队列的操作作为逻辑结构的一部分，每个操作的具体实现只有在确定了队列的存储结构之后才能完成。队列的基本运算不是它的全部运算，而是一些常用的基本运算。

![20190311192616675.png][]

**BCL 中的队列**

C\#2.0 以下版本提供了非泛型的Ｑueue类

C\#2.0 提供了泛型Queue<T>类

方法

1，Enqueue()入队(放在队尾)

2，Dequeue()出队(移除队首元素，并返回被移除的元素)

3，Peek()取得队首的元素，不移除

4，Clear()清空元素

属性

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

**使用BCL 中的队列**

//1.使用BCL中的队列
                Queue<int> queue = new Queue<int>();
                //入队(添加数据)
                queue.Enqueue(23);//队首
                queue.Enqueue(45);
                queue.Enqueue(67);
                queue.Enqueue(89);
                Console.WriteLine("添加了23 45 67 89之后队列的大小为:" + queue.Count);
                int i = queue.Dequeue();//出队
                Console.WriteLine("Dequeue取得队首的数据为:" + i);
                Console.WriteLine("Dequeue出队之后，队列的大小为:" + queue.Count);
                int j = queue.Peek();
                Console.WriteLine("Peek()取得队首的数据为: " + j);
                Console.WriteLine("Peek()出队之后，队列的大小为:" + queue.Count);
                queue.Clear();
                Console.WriteLine("Clear()之后的队列大小为:" + queue.Count);
                Console.ReadKey();

![20190311193940107.png][]

**队列接口定义**

interface IQueue<T>
        {
            int Count { get; }
            int GetLength();
            bool IsEmpty();
            void Clear();
            void Enqueue(T item);
            T Dequeue();
            T Peek();
        }

**顺序队列**

用一片连续的存储空间来存储队列中的数据元素，这样的队列称为顺序队列(Sequence Queue)。类似于顺序栈，用一维数组来存放顺序队列中的数据元素。队头位置设在数组下标为 0 的端，用 front 表示；队尾位置设在数组的另一端，用 rear 表示。 front 和 rear 随着插入和删除而变化。当队列为空时， front=rear=-1。下图是顺序队列的两个指示器与队列中数据元素的关系图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 2][]

**顺序队列-(循环顺序队列)**

如果再有一个数据元素入队就会出现溢出。但事实上队列中并未满，还有空闲空间，把这种现象称为“假溢出”。这是由于队列“队尾入队头出”的操作原则造成的。解决假溢出的方法是将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列(Circular sequence Queue)。循环队列如图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 3][]

**顺序队列-代码实现**

把循环顺序队列看作是一个泛型类，类名叫 CSeqStack<T>，“ C”是英文单词 circular 的第 1 个字母。 CSeqStack<T>类实现了接口 IQueue<T>。用数组来存储循环顺序队列中的元素，在 CSeqStack<T>类中用字段 data 来表示。用字段maxsize 表示循环顺序队列的容量， maxsize 的值可以根据实际需要修改，这通过CSeqStack<T>类的构造器中的参数 size 来实现，循环顺序队列中的元素由 data\[0\]开始依次顺序存放。字段 front 表示队头， front 的范围是 0 到 maxsize-1。字段 rear表示队尾，rear 的范围也是 0 到 maxsize-1。如果循环顺序队列为空，front=rear=-1。当执行入队列操作时需要判断循环顺序队列是否已满，如果循环顺序队列已满，(rear + 1) % maxsize==front ， 循 环 顺 序 队 列 已 满 不 能 插 入 元 素 。 所 以 ，CSeqStack<T>类除了要实现接口 IQueue<T>中的方法外，还需要实现判断循环顺序队列是否已满的成员方法。

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _003_队列
    {
        class SeqQueue<T> : IQueue<T>
        {
            private T[] data;
            private int front;//队首(=队首元素索引-1）
            private int rear;//队尾（=队尾元素索引）
            private int count;//当前有多少个元素
    
            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 Dequeue()
            {
                if(count > 0)//队列里有数据
                {
                    T temp = data[++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;
                    }
                    else
                    {
                        data[++rear] = item;
                    }
                    count++;
                }
            }
    
            public int GetLength()
            {
                return count;
            }
    
            public bool IsEmpty()
            {
                return count == 0;
            }
    
            public T Peek()
            {
                if (count > 0)//队列里有数据
                {
                    return data[front+1];
                }
                else
                {
                    Console.WriteLine("队列为空，无法取得数据!");
                    return default(T);
                }
            }
        }
    }

验证我们的顺序队列

//2.使用我们自己的顺序队列
                SeqQueue<int> queue = new SeqQueue<int>();
                //入队(添加数据)
                queue.Enqueue(23);//队首
                queue.Enqueue(45);
                queue.Enqueue(67);
                queue.Enqueue(89);
                Console.WriteLine("添加了23 45 67 89之后队列的大小为:" + queue.Count);
                int i = queue.Dequeue();//出队
                Console.WriteLine("Dequeue取得队首的数据为:" + i);
                Console.WriteLine("Dequeue出队之后，队列的大小为:" + queue.Count);
                int j = queue.Peek();
                Console.WriteLine("Peek()取得队首的数据为: " + j);
                Console.WriteLine("Peek()出队之后，队列的大小为:" + queue.Count);
                queue.Clear();
                Console.WriteLine("Clear()之后的队列大小为:" + queue.Count);
                Console.ReadKey();

![20190311201449709.png][]

**链队列**

队列的另外一种存储方式是链式存储，这样的队列称为链队列(Linked Queue)。同链栈一样，链队列通常用单链表来表示，它的实现是单链表的简化。所以，链队列的结点的结构与单链表一样，如图所示。由于链队列的操作只是在一端进行，为了操作方便，把队头设在链表的头部，并且不需要头结点。

![20190311201548820.png][]

**链队列-代码实现**

把链队列看作一个泛型类，类名为 LinkQueue<T>。 LinkQueue<T>类中有两个字段 front 和 rear，表示队头指示器和队尾指示器。由于队列只能访问队头的数据元素，而链队列的队头指示器和队尾指示器又不能指示队列的元素个数，所以，与链栈一样，在 LinkQueue<T>类增设一个字段 num 表示链队列中结点的个数。

**首先定义结点**

class Node<T>
        {
            private T data;
            private Node<T> next;
    
            public Node(T data)
            {
                this.data = data;
                next = null;
            }
    
            public T Data
            {
                get
                {
                    return data;
                }
                set
                {
                    data = value;
                }
            }
    
            public Node<T> Next
            {
                get { return next; }
                set { next = value; }
            }
        }

**定义链队列**

class LinkQueue<T> : IQueue<T>
        {
            private Node<T> front;//头结点
            private Node<T> rear;//尾结点
            private int count;//表示元素的个数
    
            public LinkQueue()
            {
                front = null;
                rear = null;
                count = 0;
            }
    
            public int Count
            {
                get
                {
                    return count;
                }
            }
    
            public void Clear()
            {
                front = null;
                rear = null;
                count = 0;
            }
    
            public T Dequeue()
            {
                if(count == 0)
                {
                    Console.WriteLine("队列为空，无法取得数据!");
                    return default(T);
                }
                else if (count == 1)
                {
                    T temp = front.Data;
                    front = null;
                    rear = null;
                    count--;
                    return temp;
                }
                else
                {
                    T temp = front.Data;
                    front = front.Next;
                    count--;
                    return temp;
                }
            }
    
            public void Enqueue(T item)
            {
                Node<T> newNode = new Node<T>(item);
                if (count == 0)
                {
                    front = newNode;
                    rear = newNode;
                    count = 1;
                }
                else
                {
                    rear.Next = newNode;
                    rear = newNode;
                    count++;
                }
                
            }
    
            public int GetLength()
            {
                return count;
            }
    
            public bool IsEmpty()
            {
                return count == 0;
            }
    
            public T Peek()
            {
                if (count == 0)
                {
                    Console.WriteLine("队列为空，无法取得数据!");
                    return default(T);
                }
                else
                {
                    return front.Data;
                }
            }
        }

![20190311205020802.png][]

循环队列的相关条件和公式：

队尾指针是rear,队头是front，其中QueueSize为循环队列的最大长度

1.队空条件：rear==front

2.队满条件：(rear+1) %QueueSIze==front

3.计算队列长度：（rear-front+QueueSize）%QueueSize

4.入队：（rear+1）%QueueSize

5.出队：（front+1）%QueueSize

**栈和队列的应用举例**

编程判断一个字符串是否是回文。回文是指一个字符序列以中间字符为基准两边字符完全相同，如字符序列“ ACBDEDBCA”是回文。

算法思想：判断一个字符序列是否是回文，就是把第一个字符与最后一个字符相比较，第二个字符与倒数第二个字符比较，依次类推，第 i 个字符与第 n-i个字符比较。如果每次比较都相等，则为回文，如果某次比较不相等，就不是回文。因此，可以把字符序列分别入队列和栈，然后逐个出队列和出栈并比较出队列的字符和出栈的字符是否相等，若全部相等则该字符序列就是回文，否则就不是回文。

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 栈和队列应用举例
    {
        class Program
        {
            static void Main(string[] args)
            {
                string str = Console.ReadLine();
                Stack<char> stack = new Stack<char>();
                Queue<char> queue = new Queue<char>();
                for(int i = 0; i < str.Length; i++)
                {
                    stack.Push(str[i]);
                    queue.Enqueue(str[i]);
                }
                bool isHui = true;
                while (stack.Count > 0)
                {
                    if (stack.Pop() != queue.Dequeue())
                    {
                        isHui = false;
                        break;
                    }
                }
                Console.WriteLine("是否是回文字符串：" + isHui);
                Console.ReadKey();
            }
        }
    }

![20190311210509654.png][]![20190311210532137.png][]

[20190310152049781.png]: /images/20220310/ee8655d02f624393a0455f94b221201b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70]: /images/20220310/d622261b3e2e40c5b9e4cb2dddb330f4.png
[20190311192508739.png]: /images/20220310/3a27ee562e204313987c0c584a6f697b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 1]: /images/20220310/29d62ce149014070aec263c715eacfc8.png
[20190311192616675.png]: /images/20220310/35337d6631f44a3a8fdd42caa81bc5d7.png
[20190311193940107.png]: /images/20220310/6eb39d85da4e4cde80ef9a00d8d61d0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 2]: /images/20220310/024a0aed8daf4eb89c8c950049dafbf2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70 3]: /images/20220310/a05e7d622adc4d879edb7cd1239c555e.png
[20190311201449709.png]: /images/20220310/18dc4399bf63409d86f61dce160baa9e.png
[20190311201548820.png]: /images/20220310/84b723476d294d0e91857d523739be27.png
[20190311205020802.png]: /images/20220310/75567557f50a4d9093050e22714e21af.png
[20190311210509654.png]: https://img-blog.csdnimg.cn/20190311210509654.png
[20190311210532137.png]: /images/20220310/942df3020e014fa6ab11400dde5d8d9d.png