数据结构之队列

一、队列的介绍

队列（Queue），是一种线性存储结构。它有以下几个特点：

1、队列中数据是按照”先进先出（FIFO, First-In-First-Out）”方式进出队列的。
2、队列只允许在”队首”进行删除操作，而在”队尾”进行插入操作。队列通常包括的两种操作：入队列和出队列。

1. 队列的示意图

这里写图片描述

队列中有10，20，30共3个数据。

2. 出队列

这里写图片描述

出队列前：队首是10，队尾是30。
出队列后：出队列(队首)之后。队首是20，队尾是30。

3. 入队列

这里写图片描述

入队列前：队首是20，队尾是30。
入队列后：40入队列(队尾)之后。队首是20，队尾是40。

二、队列的实现

实现1：数组实现
实现2：链表实现

数组实现完整代码：

    //头文件
#ifndef QUEUE_H
#define QUEUE_H

class Queue
{
public:
    Queue();
    ~Queue();

    void EnQueue(int x);
    int DeQueue();
    int GetSize(){  return (tail + MAXSIZE - head) % MAXSIZE; }
    int GetHead();
    int GetTail();
    bool Empty(){ return (head == tail) ? 1 : 0; }
    bool Full(){ return (head == tail + 1) ? 1 : 0; }
    void Display();

private:
    int *Data;
    const int MAXSIZE=50;
    int head;
    int tail;

};

#endif // !QUEUE_H


//实现文件
#include "queue.h"
#include <iostream>

Queue::Queue()
{
    Data = new int[MAXSIZE];
    head = 1;
    tail = 1;
}

Queue::~Queue()
{
    while (!Empty())
        DeQueue();

    delete []Data;
}

void Queue::EnQueue(int x)
{
    if (Full())
        std::cout << "队列已满！" << std::endl;
    else
    {

        if (tail == MAXSIZE)
        {
            tail = 1;
            Data[tail] = x;
        }
        else
            Data[tail++] = x;
    }

}


int Queue::DeQueue()
{
    if (Empty())
        std::cout << "队列已空！" << std::endl;
    else
    {
        int x = Data[head]; 
        if (head == MAXSIZE)
            head = 1;
        else
            head++;
        return x;
    }
}

int Queue::GetHead()
{
    if (Empty())
        std::cout << "队列已空！" << std::endl;
    else
        return Data[head];
}

int Queue::GetTail()
{
    if (Empty())
        std::cout << "队列已空！" << std::endl;
    else
        return Data[tail - 1];
}

void Queue::Display()
{
    if (Empty())
        std::cout << "队列已空！" << std::endl;
    else
    {
        int hd = head;
        while (hd != tail)
        {
            if (hd == MAXSIZE)
                hd = 1;
            std::cout << Data[hd++] << " ";
        }

    }
}


//测试文件

#include <iostream>
#include "queue.h"

using namespace std;

int main()
{
    Queue queue;

    cout << "队列中元素数目：";
    cout << queue.GetSize() << endl;

    for (int i = 0; i < 30; ++i)
        queue.EnQueue(i);

    cout << "队列中元素数目：";
    cout << queue.GetSize() << endl;

    for (int i = 0; i < 5; ++i)
    cout << "删除元素：" << queue.DeQueue() << endl;

    cout << "队列头元素：";
    cout << queue.GetHead() << endl;

    cout << "队列尾元素：";
    cout << queue.GetTail()<< endl;

    cout << "队列中元素数目：";
    cout << queue.GetSize() << endl;

    for (int i = 0; i < 22; ++i)
        queue.EnQueue(i);

    cout << "队列中元素：";
    queue.Display();
    cout << endl;

    cout << "队列头元素：";
    cout << queue.GetHead() << endl;

    cout << "队列尾元素：";
    cout << queue.GetTail() << endl;

    cout << "队列中元素数目：";
    cout << queue.GetSize() << endl;


    system("pause");

    return 0;
}

链表实现完整代码：

//头文件

#ifndef LINKQUEUE_H
#define LINKQUEUE_H
#include <iostream>

struct Node
{
    int data;
    Node *next;
};

class LinkQueue
{
public:
    LinkQueue();
    ~LinkQueue();
    void EnQueue(int x);
    int DeQueue();
    void Display();
    bool Empty(){ return (tail == head) ? 1 : 0; }

private:
    Node *head; //head指向无用的头结点, head->pNext才是指向队首元素， tail指向队尾元素
    Node *tail;
};


#endif // !LINKQUEUE_H


//实现文件

#include "linkqueue.h"

LinkQueue::LinkQueue()
{
    head = tail = new Node;
    tail->next = NULL;
}

LinkQueue::~LinkQueue()
{
    while (Empty())
        DeQueue();

    delete head;
}

void LinkQueue::EnQueue(int x)
{
    Node *n = new Node;

    n->data = x;
    n->next = NULL;

    tail->next = n; //将n挂到队列尾部 
    tail = n; //为指针后移
}

int LinkQueue::DeQueue()
{
    if (Empty())
        std::cout << "队列为空！" << std::endl;
    else
    {
        Node *temp = head->next;
        head->next = temp->next;
        int x = temp->data;

        delete temp;


        if (head->next == NULL)
            tail = head;

        return x;
    }

}

void LinkQueue::Display()
{
    if (Empty())
        std::cout << "队列为空！" << std::endl;
    else
    {
        Node *node = head->next;
        std::cout << "队列中的元素是：";

        while (node != tail->next)
        {
            std::cout << node->data << " ";
            node = node->next;
        }
        delete node;
    }

}


//测试文件

#include "linkqueue.h"

using namespace std;

int main()
{
    LinkQueue lq;

    for (int i = 0; i < 20; ++i)
        lq.EnQueue(i);

    lq.Display();
    cout << endl;

    for (int i = 0; i < 5; ++i)
        lq.DeQueue();

    lq.Display();
    cout << endl;

    system("pause");
    return 0;
}