随笔，数据结构与算法（八）

冬夜夜寒觉夜长，沉吟久坐坐北堂。

数据结构,那么怎么去理解这个数据结构这4个字呢,从某种角度来说,就是这一长串数据集合的特性,约束条件.之前的文章中我们对于数据结构的讨论,都会说它的时间复杂度,也就是使用某个数据结构的性能,这里我们还是一样,掌握了多种数据结构,有助于简化代码,提高代码可读性.

栈与队列

从本质上来说,栈与队列就是有了特殊限制的数组,栈与队列一般处理临时的数据,比如在游戏中,一些消息的推送就是存放在对列中.

栈

就像前面说的,栈存取数据的方式和数组一样,也是在内存中开辟一段连续的空间来存放数据,但是相对于数组来言,它有以下3条约束.

栈只能在末尾假如数据
栈只能在末尾删除数据
栈只能读取末尾的数据

我们可以想象一个薯片筒,商家在包装的时候,是这样:

包装即将完成

当厂家包装完之后消费者买到后消费这筒薯片开始打开食用,是这样:

所以,厂家最后一个放进薯片筒中的薯片会第一个被消费者拿出来吃掉.

在栈中,加入数据称之为”压栈”,

在栈中,取出数据称之为”出栈”.

让我们来简单的举个例子加强记忆一下.

在VS编译器语法检查中括号都是成对出现的,如果不成对,就会报错,那么这样的用栈来实现该怎么做呢?

如果编译器识别到了一个”{“,那么后面必然有一个”}”与之对应.如果括号有嵌套,那么如果不是同类型的括号,要等同类型的括号与之对应,具体如下说明:

括号的判断无非只会有3种情况

( … 有左无右
… ) 有右无左
{ … ) 左右括号不匹配

算法设计思想如下:

挨个读取一行代码,如果读到的字符不是括号类型的,就忽略,再读下一个,如果读到了左括号,那么就将它压到栈里.

如果读到了右括号,那么它就要判断3个东西

如果此时的栈中只有一个右括号,那么显然是”有右无左”的错误
如果此时的栈中有左括号,但是与这个右括号并不匹配,那么显然就是”左右括号不匹配”的错误
如果栈中有与它匹配的左括号,那么就代表已经匹配完毕,那么就可以将这对括号弹出,也就是出栈.

其实还有一个例子也能说明栈的作用,比如你写代码的时候写错了会撤销,那么你写的每一个步骤,每一个代码都是存在栈中的,当你按下Ctrl+z的时候也就是一个出栈的过程.

下面是详细的栈的使用方法:

using System;
using System.Collections;

namespace CollectionsApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack st = new Stack();

            st.Push('A');//压栈
            st.Push('M');
            st.Push('G');
            st.Push('W');

            Debug.Log("Current stack: ");

            foreach (char c in st)
            {
                Console.Write(c + " ");
            }
//输出的结果是W G M A,为什呢?想想薯片筒 
            st.Push('V');
            st.Push('H');
            Debug.Log("The next poppable value in stack: {0}",
            st.Peek());
            Debug.Log("Current stack: ");          
            foreach (char c in st)
            {
               Debug.Log(c + " ");
            }
            Debug.Log("");

           Debug.Log("Removing values ");
            st.Pop();
            st.Pop();
            st.Pop();

            Debug.Log("Current stack: ");
            foreach (char c in st)
            {
               Debug.Log(c + " ");
            }
        }
    }
}

Stack 类的方法和属性

属性	描述
Count	获取 Stack 中包含的元素个数。

下表列出了 Stack 类的一些常用的方法：

序号	方法名 & 描述
1public virtual void Clear()	从 Stack 中移除所有的元素。
2public virtual bool Contains( object obj )	判断某个元素是否在 Stack 中。
3public virtual object Peek()	返回在 Stack 的顶部的对象，但不移除它。
4public virtual object Pop()	移除并返回在 Stack 的顶部的对象。
5public virtual void Push( object obj )	向 Stack 的顶部添加一个对象。
6public virtual object[] ToArray()	复制 Stack 到一个新的数组中。

队列

如果将栈比喻成薯片筒的话,那么对列就可以比喻成排队,排在前面的人最先得到服务并也可以提前推出排队,队列和栈相比,有差别的就是它的取数据的方式.

但是为了好区分,我们还是写下它的特性

只能在末尾插入数据

只能读取排在第一位的数据

只能删除排在第一位的数据

也就是遵循先进先出的原则.这样的数据结构,在游戏消息推送消息中很有必要这样设计.

using System;
using System.Collections;

namespace CollectionsApplication
{
   class Program
   {
      static void Main(string[] args)
      {
         Queue q = new Queue();

         q.Enqueue('A');
         q.Enqueue('M');
         q.Enqueue('G');
         q.Enqueue('W');

         Debug.Log("Current queue: ");
         foreach (char c in q)
             {
             Debug.Log(c + " ");
             }
//这里就是按照顺序输出的了,想想排队       
         Console.WriteLine();
         q.Enqueue('V');
         q.Enqueue('H');
         Console.WriteLine("Current queue: ");        
         foreach (char c in q)
            Debug.Log(c + " ");
         Console.WriteLine();
         Console.WriteLine("Removing some values ");
         char ch = (char)q.Dequeue();
         Console.WriteLine("The removed value: {0}", ch);
         ch = (char)q.Dequeue();
         Debug.Log("The removed value: {0}", ch);

      }
   }
}

Queue 类的方法和属性

下表列出了 Queue 类的一些常用的属性：

属性	描述
Count	获取 Queue 中包含的元素个数。

下表列出了 Queue 类的一些常用的方法：

序号	方法名 & 描述
1public virtual void Clear();	从 Queue 中移除所有的元素。
2public virtual bool Contains( object obj );	判断某个元素是否在 Queue 中。
3public virtual object Dequeue();	移除并返回在 Queue 的开头的对象。
4public virtual void Enqueue( object obj );	向 Queue 的末尾添加一个对象。
5public virtual object[] ToArray()	复制 Queue 到一个新的数组中。
6public virtual void TrimToSize();	设置容量为 Queue 中元素的实际个数。

总结

栈与队列用在合适的地方就能少写很多代码,其实这么说是不适合的,应该说的精巧简练的代码,学会了栈和队列,就解锁了下一章内容,基于栈的递归算法,这也是一个基本的算法.下篇文章见.

…END…