1、队列
特点:先进先出,后进后出
环形队列(依赖数组实现,单必须实现环形)
链式队列(依赖链表实现)
2、环形队列
理论
常规数组思想随着队列的不断使用,会出现越界
所以要将其设计成环形结构
边界判断
当不断加入元素,会出现队列使用满的情况,此时不是first == rear == 0
,
在环形队列中,会留下一个位置,用来区分队列是否满的一个状态。
first == rear //队列为空
(rear + 1)%length == first //队列为满
代码实现
#include<iostream>using namespace std;//环形队列
//容器适配器queue常用操作 -- push(入队) pop(出队) front(获取队头元素) back(获取队尾元素) empty(队列是否为空) size(队列元素个数)
class Queue
{
public:Queue(int size = 10): cap_(size), front_(0), rear_(0),size_(0){pQue_ = new int[cap_];}~Queue(){delete[]pQue_;pQue_ = nullptr;}//入队,入队尾void push(int val){if ((rear_ + 1) % cap_ == front_)//队满{expand(2 * cap_);}pQue_[rear_] = val;rear_ = (rear_ + 1) % cap_;size_++;}//出队,出队头void pop(){if (front_ == rear_)throw "queue is empty!";front_ = (front_ + 1) % cap_;size_--;}//获取队头元素int front()const{if (front_ == rear_)throw "stack is empty!";return pQue_[front_];}//获取队尾元素int back()const{if (front_ == rear_)throw "stack is empty!";/*if (rear_ == 0){return pQue_[cap_-1];}return pQue_[rear_-1];*/return pQue_[(rear_ - 1 + cap_) % cap_];}//判断是否栈空bool empty()const{return front_ == rear_;}//判断栈的元素个数int size() const //方法一,添加一个成员变量,如果考虑多线程操作,该方法不可行{//return size_;//方法二: 遍历一遍队列统计元素个数 O(n)int size = 0;for (int i = front_; i != rear_; i = (i + 1) % cap_){size++;}return size;}private:void expand(int size)//扩容接口,这里不能直接memcpy{int* p = new int[size];int i = front_; //遍历原队列int j = 0; //遍历新队列for (; i != rear_; i = (i + 1) % cap_,j++){p[j] = pQue_[i];}delete[]pQue_;pQue_ = p;cap_ = size;front_ = 0;rear_ = j;}
private:int* pQue_;int cap_; //空间容量int front_; //队头,入栈指针int rear_; //队尾、出栈指针int size_; //元素个数
};
测试
int main()
{int arr[] = { 5,10,66,77,88,99,100,111 }; Queue que;for (int v : arr){que.push(v);}cout << que.front() << endl;cout << que.back() << endl;//扩容que.push(200);que.push(300);que.push(400);cout << que.front() << endl;cout << que.back() << endl;while (!que.empty()){cout << que.front() <<" "<< que.back() << endl;que.pop();}
}
测试结果
3、链式队列
基于双向循环链表实现的链式队列
队尾进,队头出
Java 里面有Linkedin的数据结构,可以充当栈、队列,基于链表实现。
代码实现
//环形队列
//容器适配器queue常用操作 -- push(入队) pop(出队) front(获取队头元素) back(获取队尾元素) empty(队列是否为空) size(队列元素个数)
class LinkQueue
{
public:LinkQueue():size_(0){head_ = new Node();head_->next_ = head_;head_->pre_ = head_;}~LinkQueue(){Node* p = head_->next_;while (p != head_){head_->next_ = p->next_;p->next_->pre_ = head_;delete p;p = head_->next_;}delete head_;head_ = nullptr;}
public://入队,入队尾void push(int val){Node* node = new Node(val);node->next_ = head_;node->pre_ = head_->pre_;head_->pre_->next_ = node;head_->pre_ = node;size_++;}//出队,出队头void pop(){if (head_->pre_ == head_)throw "queue is empty!";Node* p = head_->next_;head_->next_ = p->next_;p->next_->pre_ = head_;delete p;p = nullptr;size_--;}//获取队头元素int front()const{if (head_->next_ == head_)throw "stack is empty!";return head_->next_->data_;}//获取队尾元素int back()const{if (head_->next_ == head_)throw "stack is empty!";return head_->pre_->data_;}//判断是否栈空bool empty()const{return head_->next_ == head_;}//判断栈的元素个数int size() const //方法一,添加一个成员变量,如果考虑多线程操作,该方法不可行{return size_;//方法二: 遍历一遍队列统计元素个数 O(n)}private:struct Node{Node(int data = 0):data_(data), next_(nullptr), pre_(nullptr){}int data_;Node* next_;Node* pre_;};Node* head_;//指向头节点int size_;};
测试
int main()
{int arr[] = { 5,10,66,77,88,99,100,111 }; LinkQueue que;for (int v : arr){que.push(v);}que.push(200);que.push(300);cout << que.front() << endl;cout << que.back() << endl;while (!que.empty()){cout << que.front() <<" "<< que.back() << endl;que.pop();}
}