链式队列

时间 2021-03-13 标签 ios 数据结构 ide 函数 spa 指针 code blog 队列图片

声明：图片及内容基于https://www.bilibili.com/video/av94576761ios

原理分析

数据结构

注意本文只考虑有头节点类型数据结构

基本数据类型

定义节点ide

template<class T>
struct Node { T data; struct Node<T>* next; };

声明队列函数

template<class T>
class LinkQueue { private: Node<T>* front, * rear;  //先后结构体指针 int length; //队列长度 public: LinkQueue(); ~LinkQueue(); void enQueue(T x); //入队 bool deQueue(T& item); //出队 bool getFront(T& item); //得到头元素 bool isEmpty();  //是否为空 void clearQueue(); //清空队列 void displayQueue(); //打印队列 int queueLength(); //得到队列长度 };

队列初始化

LinkQueue<T>::LinkQueue() { front = new Node<T>; front->next = NULL; rear = front; length = 0; //别忘了 }

析构函数

LinkQueue<T>::~LinkQueue() { struct Node<T>* p =NULL; while (front) { p = front->next; delete front; front = p; } }

入队

template<class T>
void LinkQueue<T>::enQueue(T x) { struct Node<T>* p = new Node<T>; p->data = x; rear->next = p; rear = p; rear->next = NULL;   //vs里必须让尾节点next=NULL不然异常
    length++;  //别忘了 }

出队

template<class T>
bool LinkQueue<T>::deQueue(T &item) { if (isEmpty()) return false; item = front->next->data; struct Node<T>* p = front->next; //front是头节点没有数据 front->next = p->next; if (p->next == NULL)  rear = front; //防止只有一个元素时，其被删除后rear变为野指针
    delete p; length--;  //别忘了 return true; }

得到头元素

template<class T>
bool LinkQueue<T>::getFront(T& item) { if(isEmpty()) return false; item = front->next->data; //front是头节点没有数据 return true; }

判断是否为空

template<class T>
bool LinkQueue<T>::isEmpty() { if (front == rear) return true; return false; }

清空队列

template<class T>
void LinkQueue<T>::clearQueue() { struct Node<T>* p ; while (front) { p = front->next; delete front; front = p; } front = rear = NULL; //初始化头尾指针 length = 0;  //别忘了 }

打印队列

template<class T>
void LinkQueue<T>::displayQueue() { if (front == NULL) {  //队列为空return; } struct Node<T>* p = front->next; while (p!=NULL) { cout << p->data << " "; p = p->next; } cout << endl; }

得到队列长度

template<class T>
int LinkQueue<T>::queueLength() { return length; }

完整代码

#include<iostream>
using namespace std; template<class T>
struct Node { T data; struct Node<T>* next; }; template<class T>
class LinkQueue { private: Node<T>* front, * rear; int length; public: LinkQueue(); ~LinkQueue(); void enQueue(T x); bool deQueue(T& item); bool getFront(T& item); bool isEmpty(); void clearQueue(); void displayQueue(); int queueLength(); }; template<class T> LinkQueue<T>::LinkQueue() { front = new Node<T>; front->next = NULL; rear = front; length = 0; } template<class T> LinkQueue<T>::~LinkQueue() { struct Node<T>* p =NULL; while (front) { p = front->next; delete front; front = p; } } template<class T>
void LinkQueue<T>::enQueue(T x) { struct Node<T>* p = new Node<T>; p->data = x; rear->next = p; rear = p; rear->next = NULL;   //vs里必须让尾节点next=NULL不然异常
    length++; } template<class T>
bool LinkQueue<T>::deQueue(T &item) { if (isEmpty()) return false; item = front->next->data; struct Node<T>* p = front->next; front->next = p->next; if (p->next == NULL)  rear = front; //防止只有一个元素时rear以后变为野指针
    delete p; length--; return true; } template<class T>
bool LinkQueue<T>::getFront(T& item) { if(isEmpty()) return false; item = front->next->data; return true; } template<class T>
bool LinkQueue<T>::isEmpty() { if (front == rear) return true; return false; } template<class T>
void LinkQueue<T>::clearQueue() { struct Node<T>* p ; while (front) { p = front->next; delete front; front = p; } front = rear = NULL; length = 0; } template<class T>
void LinkQueue<T>::displayQueue() { if (front == NULL) { return; } struct Node<T>* p = front->next; while (p!=NULL) { cout << p->data << " "; p = p->next; } cout << endl; } template<class T>
int LinkQueue<T>::queueLength() { return length; } int main() { LinkQueue<int> Queue; Queue.enQueue(1); Queue.enQueue(2); Queue.enQueue(3); Queue.displayQueue(); int d; Queue.deQueue(d); Queue.displayQueue(); cout << "d=" << d << endl; cout << "length=" << Queue.queueLength()<<endl; int f; Queue.getFront(f); cout << "front=" <<f <<endl; Queue.clearQueue(); if (Queue.isEmpty()) cout << "empty" << endl; cout << "length=" << Queue.queueLength()<<endl; Queue.displayQueue(); return 0; }