队列的实现（数组模拟）

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int q[N],hh,tt;

//队列每次都是往队尾插入元素，从队头取出或弹出元素
void init()
{
    hh=0;//head
    tt=-1;//tail
}

void push(int x)
{
    q[++tt]=x;
}

void pop()
{
    hh++;
}

void empty()
{
    if(hh<=tt) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}

void query()
{
    cout<<q[hh]<<endl;
}

int main()
{
    int M;
    scanf("%d",&M);
    init();
    while(M--)
    {
        string str;
       cin>>str;
        if(!str.compare("push")) 
        {
            int x;
            scanf("%d",&x);
            push(x);
        }
        else if(!str.compare("pop")) pop();
        else if(!str.compare("empty")) empty();
        else query();
    }
    
    return 0;
}

初始化是将hh=0,tt=-1
加入元素是想队尾加入q[++tt]=x;
判空:hh<=tt则不为空，否则hh>tt为空
判满:hh-tt=k?

循环双端队列

循环双端队列可以在队头插入元素也可以在队尾插入元素，并且队尾的下一个位置是队头，可以使用链表也可以使用数组进行模拟，那么如何开一个环形数组：其实就是开一个普通数组但是第k-1位和第0位是相邻的。

维护两个指针hh，tt分别表示队头和队尾。
整个数组的长度最大为k，但是由于实际上有队列中分别存储0,1,2,3,4…k个元素的K+1种状态，所以实际上只开一个长度为K的数组是不够的，因此数组的长度要开到k+1(初始化);
另外存储数据的位置是从hh开始，到tt-1结束。tt不存储数据，类似vector容器中：begin()表示开始位置end()表示最后一个元素的后一个位置。
判空：hh==tt;为空
判满: tt-hh=k;为满或者tt=hh-1;因为整个环形（数组）的长度是k+1所以tt-hh=k,实际上就是tt在hh-1的位置。
存储的时候0的前一个位置应该是K,

而在头部插入是

q[--hh]=x;

由于开始初始化的时候是将hh=0,tt=0,而直接插入的话hh-1=-1，为了使得在头部插入实际上是在循环队列的尾部插入，应该写一个辅助函数，对hh进行取模，让他重新分布在[0,k]的区间上，

int get(int x)
{
	return (x+q.size())%q.size();
}

x+q.size()之后再取模是因为要处理x为负数的情况。

hh=get(hh-1);
q[hh]=x'

完整代码：

class MyCircularDeque {
private:
    vector<int> q;
    int hh=0,tt=0;
public:
    MyCircularDeque(int k) {
        q.resize(k+1);
    }
    
    int get(int x)
    {
        return (x+q.size())%q.size();
    }

    bool insertFront(int value) {
        if(isFull()) return false;
        //先更新hh,再赋值
        hh=get(hh-1);
        q[hh]=value;
        return true;
    }
    
    bool insertLast(int value) {
        if(isFull()) return false;
        //先赋值，在更新tt
        q[tt]=value;
        tt=get(tt+1);
        return true;
    }
    
    bool deleteFront() {
        if(isEmpty()) return false;
        hh=get(hh+1);
        return true;
    }
    
    bool deleteLast() {
        if(isEmpty())  return false;
        tt=get(tt-1);
        return true;
    }
    
    int getFront() {
        if(isEmpty()) return -1;
        return q[hh];
    }
    
    int getRear() {
        if(isEmpty()) return -1;
        return q[get(tt-1)];
    }
    
    bool isEmpty() {
        if(hh==tt) return true;
        else return false;
    }
    
    bool isFull() {
        if(tt==get(hh-1)) return true;
        else return false;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

特别要注意的是凡是涉及有tt-1或者hh-1的操作的，为了防止越界，都应该取模：比如：

 bool deleteLast() {
        if(isEmpty())  return false;
        tt=get(tt-1);
        return true;
    }

 bool isFull() {
        if(tt==get(hh-1)) return true;
        else return false;
    }

最后

以上就是朴实飞鸟为你收集整理的队列的实现与双端循环队列队列的实现（数组模拟）循环双端队列的全部内容，希望文章能够帮你解决队列的实现与双端循环队列队列的实现（数组模拟）循环双端队列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。