资料结构 伫列(Queue)

目录：资料结构系列文章

伫列(Queue)是一种First-In-First-Out的资料结构
如同字面上意思，就像排队买票的队列一样
先买完票的人才能先出去，进来后面排队的人要等到前面的人都买完才能出去

使用c++实作

使用阵列(Array)实作

这里是採用记忆体空间会重複使用的Circular Queue

#include <iostream>using namespace std;template <typename T>class QueueArray{public:    QueueArray() : front(-1), back(-1), capacity(1)    {        ptr = new T[capacity];    }    void Push(T data) // 把资料放到最后端    {        if ((back + 1) % capacity == front) // 如果每个位置都放满了，把配置阵列大小变为2倍再放资料        {            DoubleCapacity();        }        if (isEmpty()) // 如果Queue为空，则Push时front要另外加1，让front变为0        {            front++;        }        ptr[(back + 1) % capacity] = data;        back = (back + 1) % capacity;    }    void Pop() // 把顶端的资料移除    {        if (isEmpty())        {            cout << "Queue is empty." << endl;        }        else        {            front++; // 只需要把front加1就行，因为之后如果有资料Push进来，会直接覆盖掉原本的，不须花费成本再delete跟new        }    }    bool isEmpty() // 回传Queue是否为空    {        return (front == -1);    }    int getSize() // 回传Queue大小    {        if (isEmpty())        {            return 0;        }        else if (front == back) // 如果front和back为同一个位置        {            return 1;        }        else if (front < back) // 如果front在back前面        {            return back - front + 1;        }        else // 如果front在back后面        {            return capacity - (front - back) + 1;        }    }    T getFront() // 回传最前端的资料    {        if (isEmpty())        {            cout << "Queue is empty." << endl;            return 0; // 回传0是因为不知道T是什么型态，如果回传别的数值会很容易出错        }        return ptr[front];    }    T getBack() // 回传最后端的资料    {        if (isEmpty())        {            cout << "Queue is empty." << endl;            return 0; // 回传0是因为不知道T是什么型态，如果回传别的数值会很容易出错        }        return ptr[back];    }private:    int front;            // 最前端的index    int back;             // 最后端的index    int capacity;         // 目前配置空间的大小    int *ptr;             // 目前配置的阵列(第一个元素的指标)    void DoubleCapacity() // 把配置的阵列变成两倍的大小    {        int *newptr = new int[capacity * 2];        int j = front - 1;        for (int i = 0; i < capacity; i++) // 把旧的阵列里的资料複製到新的阵列        {            newptr[i] = ptr[(++j) % capacity];        }        delete[] ptr;        ptr = newptr;        front = 0;        back = capacity - 1;        capacity *= 2;    }};int main(){    QueueArray<int> q;    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(24);    cout << "After push 24:\n";    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(8);    q.Push(23);    cout << "After push 8, 23:\n";    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Pop();    cout << "After pop 24:\n";    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(13);    cout << "After push 13:\n";    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Pop();    cout << "After pop 8:\n";    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(35);    cout << "After push 35:\n";    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(9);    cout << "After push 9:\n";    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(64);    cout << "After push 64:\n";    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    return 0;}

output:

Queue is empty.Queue is empty.1 0 0 00 24 24 10 24 23 30 8 23 20 8 13 30 23 13 20 23 35 30 23 9 40 23 64 5

使用链结串列(Linked List)实作

一样我们稍微修改一下之前的linklist后就直接继承
SinglyLinkedList.h

#include <iostream>using namespace std;template <typename T>class SinglyLinkedList; // 为了将class SinglyLinkedList设成class ListNode的friend，必须先宣告template <typename T>class ListNode{public:    ListNode(T x) : value(x), next(0) {} // 使用c++的成员初始化串列，将value初始化为x，next初始化为0private:    T value;    ListNode<T> *next;    friend class SinglyLinkedList<T>; // 将class SinglyLinkedList宣告为friend，让class SinglyLinkedList可以存取ListNode的private成员};template <typename T>class SinglyLinkedList{public:    SinglyLinkedList() : head(0), size(0),tail(0) {}    int getSize() // 回传list资料个数    {        return size;    }    bool isEmpty() // 回传list是否为空    {        return head == 0;    }protected: // 设为protected是因为不想让非成员函式可以存取到    void PushFront(T data) // 在list的最前端塞入资料    {        ListNode<T> *NewNode = new ListNode<T>(data);        if (head == 0)        {            head = NewNode;            tail = NewNode;        }        else        {            NewNode->next = head;            head = NewNode;        }        ++size;    }    void PushBack(T data) // 在list的最后端塞入资料    {        if (head == 0)        {            PushFront(data);        }        else        {            ListNode<T> *NewNode = new ListNode<T>(data);            tail->next=NewNode;            tail = NewNode;            ++size;        }    }    ~SinglyLinkedList()    {        ListNode<T> *current = head;        while (current != 0)        {            ListNode<T> *NextNode = current->next;            delete current;            current = NextNode;        }        head = 0; // 当指标被delete后, 将其指向NULL, 可以避免不必要bug    }    void PopFront() // 移除list中最前端的资料    {        if (head == 0)        {            cout << "List is empty." << endl;        }        else if(head!=0&& head->next==0) // 当list只有一笔资料时        {            delete head;            head = 0;            tail = 0;            --size;        }        else        {            ListNode<T> *NextNode = head->next;            delete head;            head = NextNode;            --size;        }    }    T getHead() // 回传第一个资料    {        if (isEmpty())        {            cout << "List is empty." << endl;            return 0;        }        else        {            return head->value;        }    }    T getTail() // 回传最后一个资料    {        if (isEmpty())        {            cout << "List is empty." << endl;            return 0;        }        else        {            return tail->value;        }    }private:    ListNode<T> *head;    ListNode<T> *tail;    int size;};

#include <iostream>#include "SinglyLinkedList.h"using namespace std;template <typename T>class QueueList : public SinglyLinkedList<T>{public:    void Push(T data) // 在最后端放入资料    {        SinglyLinkedList<T>::PushBack(data);    }    void Pop() // 移除最前端的资料    {        if (SinglyLinkedList<T>::isEmpty())        {            cout << "Queue is empty." << endl;        }        else        {            SinglyLinkedList<T>::PopFront();        }    }    T getFront() // 取得最前端的资料    {        if (SinglyLinkedList<T>::isEmpty())        {            cout << "Queue is empty." << endl;            return 0;        }        else        {            SinglyLinkedList<T>::getHead();        }    }    T getBack() // 取得最后端的资料    {        if (SinglyLinkedList<T>::isEmpty())        {            cout << "Queue is empty." << endl;            return 0;        }        else        {            SinglyLinkedList<T>::getTail();        }    }};int main(){    QueueList<int> q;    cout << q.isEmpty() << endl;    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(24);    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Pop();    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(8);    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Pop();    cout << q.isEmpty() << endl;    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(23);    cout << q.isEmpty() << endl;    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(13);    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Pop();    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(35);    q.Push(36);    cout << q.isEmpty() << endl;    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Pop();    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Push(38);    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Pop();    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    q.Pop();    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;    cout << q.isEmpty() << endl;    return 0;}

output:

1Queue is empty.Queue is empty.0 0 024 24 1Queue is empty.Queue is empty.0 0 08 8 11Queue is empty.Queue is empty.0 0 0023 23 123 13 213 13 1013 36 335 36 235 38 336 38 238 38 10

使用python实作

class Queue:    def __init__(self):        self.queue = []  # 使用串列来实作        self.size = 0    def Push(self, data):  # 把资料放到最后端        self.queue.append(data)  # append函式 把资料加进串列的末端        self.size += 1    def Pop(self):  # 把最前端的资料移除        if self.size == 0:            print("Queue is empty.")        else:            self.queue = self.queue[1:]  # 把串列的第一个元素移除            self.size -= 1    def getFront(self):        if self.size == 0:            print("Queue is empty.")            return 0        else:            return self.queue[0]    def getBack(self):  # 回传最后端的资料        if self.size == 0:            print("Queue is empty.")            return 0        else:            return self.queue[self.size - 1]    def isEmpty(self):  # 回传queue是否为空        return self.size == 0    def getSize(self):  # 回传queue大小        return self.sizedef main():    s = Queue()    s.Pop()    print(s.isEmpty())    print(s.getFront())    print(s.getBack())    print(s.getSize())    s.Push(2)    print(s.isEmpty())    print(s.getFront(), end=" ")    print(s.getBack(), end=" ")    print(s.getSize())    s.Push(4)    print(s.getFront(), end=" ")    print(s.getBack(), end=" ")    print(s.getSize())    s.Push(6)    print(s.getFront(), end=" ")    print(s.getBack(), end=" ")    print(s.getSize())    s.Pop()    print(s.isEmpty())    print(s.getFront(), end=" ")    print(s.getBack(), end=" ")    print(s.getSize())    s.Pop()    print(s.getFront(), end=" ")    print(s.getBack(), end=" ")    print(s.getSize())    s.Push(8)    print(s.getFront(), end=" ")    print(s.getBack(), end=" ")    print(s.getSize())    s.Push(10)    print(s.isEmpty())    print(s.getFront(), end=" ")    print(s.getBack(), end=" ")    print(s.getSize())    s.Pop()    print(s.getFront(), end=" ")    print(s.getBack(), end=" ")    print(s.getSize(), end=" ")    print(s.isEmpty())if __name__ == "__main__":    main()

output:

Queue is empty.TrueQueue is empty.0Queue is empty.00False2 2 12 4 22 6 3False4 6 26 6 16 8 2False6 10 38 10 2 False

上一篇：资料结构 堆叠(Stack)