数据结构06-链队列（用C++、C#、lua实现）

目录

• 1、C#实现
• 2、C++实现
• 3、lua实现

本文为数据结构-链队列的代码实现。
作者水平比较差，有错误的地方请见谅。

1、C#实现

队列接口
IQueue.cs

    interface IQueue<T>
    {
        int GetLength(); //求队列的长度
        bool IsEmpty(); //判断队列是否为空
        void Clear(); //清空
        void Enqueue(T data); //入队列
        T Dequeue(); //出队列
        T Peek(); //取队列顶元素
        void ShowAllElem(); //显示队列中所有元素
    }

链队列
LinkQueue.cs

class LinkQueue<T> : IQueue<T>
    {
        /// <summary>
        /// 指向最后一个结点
        /// </summary>
        private QueueNode<T> mRearNode;
        /// <summary>
        /// 指向第一个结点
        /// </summary>
        private QueueNode<T> mFrontNode;
        private int mCount;

        public LinkQueue()
        {
            mRearNode = new QueueNode<T>();
            mFrontNode = new QueueNode<T>();
            mCount = 0;
        }

        public int GetLength()
        {
            return mCount;
        }

        public bool IsEmpty()
        {
            return mCount == 0;
        }

        public void Enqueue(T data)
        {
            QueueNode<T> newNode = new QueueNode<T>(data);
            if (mCount == 0)
            {
                mRearNode = newNode;
                mFrontNode = newNode;
            }
            else
            {
                mRearNode.Next = newNode;
                mRearNode = newNode;
            }
            mCount++;
        }

        public T Dequeue()
        {
            T data = default(T);
            if (mCount == 0)
            {
                Console.WriteLine("队列为空，无法再出队列。");
                return default(T);
            }
            else if(mCount == 1)
            {
                data = mFrontNode.Data;
                mRearNode = null;
                mFrontNode = null;
            }
            else
            {
                data = mFrontNode.Data;
                mFrontNode = mFrontNode.Next;
            }

            mCount--;
            return data;
        }

        public T Peek()
        {
            if (mCount == 0)
            {
                Console.WriteLine("队列为空，无法再出队列。");
                return default(T);
            }
            return mFrontNode.Data;
        }

        public void Clear()
        {
            mCount = 0;
            mRearNode = null;
            mFrontNode = null;
        }

        public void ShowAllElem()
        {
            QueueNode<T> temp = mFrontNode;
            while (temp != null)
            {
                Console.WriteLine(temp.Data);
                temp = temp.Next;
            }
        }
    }

Program.cs

    class Program
    {
        static void Main(string[] args)
        {
            IQueue<string> linkQueue = new LinkQueue<string>();
            linkQueue.Enqueue("111");
            linkQueue.Enqueue("222");
            linkQueue.Enqueue("333");
            linkQueue.Enqueue("444");

            linkQueue.Clear();
            linkQueue.Enqueue("111");
            linkQueue.Enqueue("222");
            linkQueue.Enqueue("333");
            linkQueue.Enqueue("444");

            //Console.WriteLine(linkQueue.GetLength());
            //Console.WriteLine(linkQueue.IsEmpty());
            //Console.WriteLine(linkQueue.Dequeue());
            //Console.WriteLine(linkQueue.Peek());
            linkQueue.ShowAllElem();

            Console.ReadKey();
        }
    }

2、C++实现

队列接口
IQueue.cpp

#include <iostream>
using namespace std;

typedef int ElemType;

class IQueue
{
public:

    ///求队列的长度
    virtual int GetLength() = 0;

    ///判断队列是否为空
    virtual bool IsEmpty() = 0;

    ///清空
    virtual void Clear() = 0;

    ///入队列
    virtual void Enqueue(ElemType data) = 0;

    ///出队列
    virtual ElemType Dequeue() = 0;

    ///取队列顶元素
    virtual ElemType Peek() = 0;

    ///显示队列中所有元素
    virtual void ShowAllElem() = 0;

};

链队列
LinkQueue.cpp

#include <iostream>
#include "IQueue.cpp"
using namespace std;

typedef int ElemType;

typedef struct QNode{
    ElemType data;
    QNode* next;
}QNode,*QueueNode;

class LinkQueue:public IQueue
{
private:
    QueueNode mRearNode;
    QueueNode mFrontNode;
    int mCount;

public:
    LinkQueue();
    ~LinkQueue();

    int GetLength();

    bool IsEmpty();

    void Clear();

    void Enqueue(ElemType data);

    ElemType Dequeue();

    ElemType Peek();

    void ShowAllElem();

};

LinkQueue::LinkQueue()
{
   mRearNode = new QNode();
   mFrontNode = new QNode();
   mCount = 0;
}

LinkQueue::~LinkQueue()
{
    QueueNode first = mFrontNode;

    while (first != NULL)
    {
        QueueNode temp = first;
        first = first->next;
        delete temp;
    }
    mCount = 0;
}

int LinkQueue::GetLength()
{
    return mCount;
}

bool LinkQueue::IsEmpty()
{
    return mCount == 0;
}

void LinkQueue::Clear()
{
    QueueNode first = mFrontNode;

    while (first != NULL)
    {
        QueueNode temp = first;
        first = first->next;
        delete temp;
    }
    mCount = 0;
    mRearNode = NULL;
    mFrontNode = NULL;
}

void LinkQueue::Enqueue(ElemType data)
{
    QueueNode node = new QNode();
    node->data = data;

    if(mCount == 0){
        mRearNode = node;
        mFrontNode = node;
    }
    else{
        mRearNode->next = node;
        mRearNode = node;
    }
    mCount++;
}

ElemType LinkQueue::Dequeue()
{
    ElemType data;
    if(mCount == 0){
        cout<<"队列为空，无法出队列。"<<endl;
        return 0;
    }
    else if(mCount == 1)
    {
        data = mFrontNode->data;

        delete mFrontNode;
        mRearNode = NULL;
        mFrontNode = NULL;
    }
    else
    {
        data = mFrontNode->data;

        QueueNode temp = mFrontNode;
        mFrontNode = mFrontNode->next;
        delete temp;
    }

    mCount--;
    return data;
}

ElemType LinkQueue::Peek()
{
    if (mCount == 0)
    {
        cout<<"队列为空，无法再出队列。"<<endl;
        return 0;
    }
    return mFrontNode->data;
}

void LinkQueue::ShowAllElem()
{
    QueueNode temp = mFrontNode;
    while (temp != NULL)
    {
        cout<<temp->data<<endl;
        temp = temp->next;
    }
}

main.cpp

#include <iostream>
#include "LinkQueue.cpp"

using namespace std;

typedef int ElemType;

int main()
{
    LinkQueue linkQueue;

    linkQueue.Enqueue(111);
    linkQueue.Enqueue(222);
    linkQueue.Enqueue(333);
    linkQueue.Enqueue(444);

    linkQueue.Clear();
    linkQueue.Enqueue(111);
    linkQueue.Enqueue(222);
    linkQueue.Enqueue(333);
    linkQueue.Enqueue(444);

    cout<<linkQueue.GetLength()<<endl;
    cout<<linkQueue.IsEmpty()<<endl;
    cout<<linkQueue.Dequeue()<<endl;
    cout<<linkQueue.Peek()<<endl;

    linkQueue.ShowAllElem();

    return 0;
}

3、lua实现

--表示链式队列
linkQueue = {}
--表示头结点
frontNode = {}
--表示尾结点
rearNode = {}
--队列中结点个数
count = 0


--初始化
function linkQueue:Init()
    count = 0
end

--销毁
function linkQueue:Destory()
    self = nil
    frontNode = nil
    rearNode = nil
    count = nil
end

--清空
function linkQueue:Clear()
    self = {}
    frontNode = {}
    rearNode = {}
    count = 0
end

--是否为空
function linkQueue:IsEmpty()
    return count == 0
end

--长度
function linkQueue:GetLength()
    return count
end

--入队列
function linkQueue:EnQueue(value)
    local newNode = {data = value,next = nil}
    if(count == 0) then
        self = newNode
        frontNode = self
        rearNode = self
    else
        rearNode.next = newNode
        rearNode = newNode
    end
    count = count + 1
end

--出队列
function linkQueue:DeQueue()
    local data
    if(count == 0) then
        print("队列中无元素，无法再出队列。");
        return
    elseif(count == 1) then
        data = frontNode.data
        frontNode = {}
        rearNode = {}
    else
        data = frontNode.data
        frontNode = frontNode.next
    end

    count = count - 1
    return data
end

--获取队列第一个元素
function linkQueue:Peek()
    if(count == 0) then
        print("队列中无元素，无法再出队列。");
        return
    end

    return frontNode.data
end

--显示所有元素
function linkQueue:ShowAllElem()
    local temp = frontNode
    while(temp ~= nil) do
        print(temp.data)
        temp = temp.next
    end
end


--主运行函数
function main()
    linkQueue:Init()
    linkQueue:EnQueue(111)
    linkQueue:EnQueue(222)
    linkQueue:EnQueue(333)
    linkQueue:EnQueue(444)

    linkQueue:Clear()
    linkQueue:EnQueue(111)
    linkQueue:EnQueue(222)
    linkQueue:EnQueue(333)
    linkQueue:EnQueue(444)

    --print(linkQueue:GetLength())
    --print(linkQueue:IsEmpty())
    --print(linkQueue:DeQueue())
    --print(linkQueue:Peek())

    linkQueue:ShowAllElem()

end

main()