数据结构(C#)：队列

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

队列的特点是先进先出，如同日常生活中的排队。队列有加入队尾，从队头删除元素，取得队尾元素，取得队头元素，取得队列长度，判断队列是否为空等操作。
队列也可以可以用顺序表、链表实现，但队列最好不要用顺序表实现，因为元素加入队列和删除元素中的一种操作总会引起全部元素的移动，效率极低(循环队列除外)。
队列的实现非常简单，下面用前面介绍的单链表实现。
代码：

/*
* File     :   Queue.cs
* Author   :   Zhenxing Zhou
* Date     :   2008-12-07
* Blog     :   http://www.xianfen.net/
*/
namespace Xianfen.Net.DataStructure
{
    public class Queue<T>
    {
        protected SingleLinkedList<T> m_List;

        public bool IsEmpty
        {
            get { return m_List.IsEmpty; }
        }

        public int Count
        {
            get { return m_List.Count; }
        }

        public Queue()
        {
            m_List = new SingleLinkedList<T>();
        }

        public Queue(T t)
        {
            m_List = new SingleLinkedList<T>(t);
        }

        public T DeQueue()
        {
            T t = m_List.GetTail();
            m_List.RemoveTail();

            return t;
        }

        public void EnQueue(T t)
        {
            m_List.AddHead(t);
        }

        public T GetFront()
        {
            return m_List.GetTail();
        }

        public T GetRear()
        {
            return m_List.GetHead();
        }
    }
}

2.应用示例
也是一个非常无聊的演示程序：显示随机生成整数的奇偶数对。

Queue<int> q1 = new Queue<int>();
Queue<int> q2 = new Queue<int>();
Random rnd = new Random();

for (int i = 0; i < 20; i++)
{
    int value = rnd.Next();

    if (value % 2 != 0)
    {
        q1.EnQueue(value);
    }
    else
    {
        q2.EnQueue(value);
    }
}

while (!q1.IsEmpty && !q2.IsEmpty)
{
    Console.WriteLine("奇偶数对：{0},{1}", q1.DeQueue(), q2.DeQueue());
}

某次运行结果：

奇偶数对：1001667163,570500228
奇偶数对：703882551,1134267770
奇偶数对：1938115369,486438246
奇偶数对：1471693833,717831946
奇偶数对：429728181,678751398
奇偶数对：1894142101,2052360200
奇偶数对：1289719185,1630602020