链式队列

队列是一种受限制的特殊线性表,插入元素从队列的尾插入,删除元素从队列的头删除,所以最先插入(入队)的元素最先删除(出队),形成了“先进先出”的效果。

一般的队列是由数组实现的,并且用两个指针进行管理。一个头指针指向队列的头,另一个是尾指针,指向的是队列的尾部。而且队列头是连着队列尾的,实现了循环的效果,就像“Josephus环”那样。这种数组实现的队列最不好的地方就是有长度限制,而且处理不当会出现“溢出”。所以我通过链表的形式实现了队列,而不是数组。链表实现的队列继承了链表的特性,只是做了一些的限制。

下面是实现队列的详细代码:

Queue.h 队列的头文件

class Queue{
public:
    Queue():front(nullptr), rear(nullptr){};
    ~Queue();

    struct Node{
        char Values;
        Node *Next;
    };

    void Insert(char Values);
    void Show();
    void Delete();
    bool Empty();

private:
    Node *front;
    Node *rear;
};

Queue.cpp 队列的源文件

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

using namespace std;

void Queue::Insert(char Values){
    Node *New = new Node;
    New->Values = Values;

    if(front == nullptr){
        New->Next = New;
        front = New;
        rear = front;
    }else{
        New->Next = front;
        rear->Next = New;
        rear = rear->Next;
    }
}

void Queue::Show(){
    Node *p = front;

    if(front != nullptr){
        do{
            cout << p << "\t" << p->Values << "\t" << p->Next << endl;
            p = p->Next;
        }while(p != front);
    }

    cout << endl;
}

void Queue::Delete(){
    Node *p = nullptr;
    
    if(front->Next != front){
        rear->Next = front->Next;
        p = front->Next;
        delete front;
        front = p;
        
    }else{
        delete front, rear;
        front = rear = nullptr;
    }
}

bool Queue::Empty(){
    if(front != nullptr && rear != nullptr){
        return false;
    }else{
        return true;
    }
}

Queue::~Queue(){
    delete front, rear;
    front = rear = nullptr;
}

Main.cpp 程序的入口文件

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

using namespace std;

int main(){
    Queue QueueList;
    QueueList.Insert('a');
    QueueList.Insert('b');
    QueueList.Insert('c');
    QueueList.Show();

    QueueList.Delete();
    QueueList.Show();

    cout << QueueList.Empty() << endl;

    QueueList.Delete();
    QueueList.Delete();
    QueueList.Show();

    cout << QueueList.Empty() << endl;

    system("pause");
    return 0;
}

标签:计算机, 程序, 设计, 常用, 算法, 链式, 队列

该文章由 Shiqi Qiu 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源:http://blog.fdawn.com/CPP/21.html

添加新评论