10.1-5 双端队列

一、题目

栈的插入和删除操作都是在一端进行的，而队列的插入和删除却是在两头进行的。另有一种双端队列（deque），其两端都可以做插入和删除操作。对于一个用数组构造的双端队列，请写出四个在两端进行插入和删除的操作的过程，要求运行时间都为O(1)

二、伪代码

NEXT(p, l)
1    if p = l
2        then ret <- 1
3        else ret <- p + 1
4    return ret
PRE(p, l)
1    if p = 1
2        then ret <- l
3        else ret <- p - 1
4    return ret
DEQUEUE-LEFT-INSERT(D, x)
1    l <- PRE([left[D], length[D])
2    if l = right[D]
3        then error "overflow"
4    if left[D] = right[D]
5        right[D] <- NEXT(right[D], length[D])
6   D[left[D]] <- x
7   left[D] <- l
DEQUEUE-RIGHT-INSERT(D, x)
1    r <- NEXT([right[D], length[D])
2    if r = left[D]
3        then error "overflow"
4    if left[D] = right[D]
5        left[D] <- PRE(left[D], length[D])
6    D[right[D]] <- x
7   right[D] <- r 
DEQUEUE-LEFT-DELETE(D)
1    if left[D] = right[D]
2        then error "underflow"
3    ret <- D[left[D]]
4    left[D] <- NEXT(left[D], length[D])
DEQUEUE-RIGHT-DELETE(D)
1    if left[D] = right[D]
2        then error "underflow"
3    ret <- D[right]
4    right[D] <- PRE(right[D], length[D])

三、代码

//双端队列
struct deque
{
    //左端指针和右端指针都是指向待操作元素的下一个位置
    int left;//左端指针，初始化为1
    int right;//右端指针，初始化为1
    int length;//数组长度
    int *s;//数组
    deque(int size):left(1),right(1),length(size){s = new int[size+1];}
};
//输出双端队列
void Print(deque D)
{
    int i;
    if(D.right >= D.left)
    {
        for(i = D.left+1; i < D.right; i++)
            cout<<D.s[i]<<' ';
        cout<<endl;
    }
    //同样考虑循环的问题
    else
    {
        for(i = D.left + 1; i <= D.length; i++)
            cout<<D.s[i]<<' ';
        for(i = 1; i < D.right; i++)
            cout<<D.s[i]<<' ';
        cout<<endl;
    }
}
//判断双端队列是否为空
bool Deque_Empty(deque D)
{
    if(D.left == D.right)
        return 1;
    return 0;
}
//因为要处理循环，为了方便，把求下一个位置和上一个位置的函数提取出来
int Next(int p, int l)
{
    if(p == l)
        return 1;
    else return p+1;
}
int Pre(int p, int l)
{
    if(p == 1)
        return l;
    else
        return p - 1;
}
//左端插入
void Deque_Left_Insert(deque &D, int x)
{
    //处理越界
    int l = Pre(D.left, D.length);
    if(l == D.right)
    {
        cout<<"error:overflow"<<endl;
        return ;
    }
    //如果初始化时为空，两端的指针都要移动
    if(D.left == D.right)
        D.right = Next(D.right, D.length);
    D.s[D.left] = x;
    D.left = l;
}
//右端插入，处理方式类似左端插入
void Deque_Right_Insert(deque &D, int x)
{
    int r = Next(D.right, D.length);
    if(r == D.left)
    {
        cout<<"error:overflow"<<endl;
        return ;
    }
    if(D.left == D.right)
        D.left = Pre(D.left, D.length);
    D.s[D.right] = x;
    D.right = r;
}
//左端删除
int Deque_Left_Delete(deque &D)
{
    //下溢
    if(D.left == D.right)
    {
        cout<<"error:underflow"<<endl;
        return -1;
    }
    D.left = Next(D.left, D.length);
    //如果删除时只有一个元素，删除后两端的指针都要移动
    if(Next(D.left,D.length) == D.right)
        D.right = D.left;
    return D.s[D.left];
}
//右端删除，处理类似左端删除
int Deque_Right_Delete(deque &D)
{
    if(D.left == D.right)
    {
        cout<<"error:underflow"<<endl;
        return -1;
    }
    D.right = Pre(D.right, D.length);
    if(Next(D.left,D.length) == D.right)
        D.left = D.right;
    return D.s[D.right];
}