[数据结构与算法]0641-设计循环双端队列

问题描述

https://leetcode-cn.com/problems/design-circular-deque/

求解思路

双端队列有两种实现方式：一种是借助数组，这时需要考虑其循环特性，对于front和rear的操作要注意取模；另一种是借助双向链表，链表的动态存储特性使我们不必像数组那样考虑循环性质，但是涉及较多的指针操作。

代码实现

采用数组实现的循环双端队列：

typedef struct {
    int* data;
    int front;
    int rear;
    int arraySize;
} MyCircularDeque;

bool myCircularDequeIsEmpty(MyCircularDeque* obj);
bool myCircularDequeIsFull(MyCircularDeque* obj);

/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque* myCircularDequeCreate(int k) {
    //没有检查malloc返回值
    MyCircularDeque* mydq = (MyCircularDeque*)malloc(sizeof(MyCircularDeque));
    mydq->data = (int*)malloc(sizeof(int) * (k + 1));
    for (int i = 0; i < (k + 1); ++i)
        mydq->data[i] = -1;
    mydq->front = 0;
    mydq->rear = 0;
    mydq->arraySize = k + 1;
    return mydq;
}

/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if (myCircularDequeIsFull(obj))
        return false;
    obj->data[obj->front] = value;
    obj->front = (obj->front) == 0 ? obj->arraySize - 1 : obj->front - 1;
    return true;
}

/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    if (myCircularDequeIsFull(obj))
        return false;
    obj->rear = (obj->rear + 1) % (obj->arraySize);
    obj->data[obj->rear] = value;
    return true;
}

/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj))
        return false;
    obj->front = (obj->front + 1) % (obj->arraySize);
    return true;
}

/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj))
        return false;
    obj->rear = (obj->rear) == 0 ? obj->arraySize - 1 : obj->rear - 1;
    return true;
}

/** Get the front item from the deque. */
int myCircularDequeGetFront(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj))
        return -1;
    else
        return obj->data[(obj->front + 1) % (obj->arraySize)];
}

/** Get the last item from the deque. */
int myCircularDequeGetRear(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj))
        return -1;
    else
        return obj->data[obj->rear];
}

/** Checks whether the circular deque is empty or not. */
bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->front == obj->rear;
}

/** Checks whether the circular deque is full or not. */
bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return (obj->rear + 1) % (obj->arraySize) == obj->front;
}

void myCircularDequeFree(MyCircularDeque* obj) {
    if (obj == NULL)
        return;
    if (obj->data != NULL)
        free(obj->data);
    free(obj);
    return;
}

采用双向链表实现双端队列：

//双向链表实现
typedef struct dqNode dqNode;

//双向链表节点
struct dqNode {
    dqNode* prev;
    dqNode* succ;
    int data;
};

typedef struct {
    int capacity;
    int size;
    dqNode* front;
    dqNode* rear;
} MyCircularDeque;

bool myCircularDequeIsEmpty(MyCircularDeque* obj);
bool myCircularDequeIsFull(MyCircularDeque* obj);
/** Initialize your data structure here. Set the size of the deque to be k. */

MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque* mydq = (MyCircularDeque*)malloc(sizeof(MyCircularDeque));
    mydq->capacity = k;
    mydq->size = 0;
    mydq->front = mydq->rear = NULL;
    return mydq;
}

/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    //return obj->size == obj->capacity;
    if (myCircularDequeIsFull(obj))
        return false;
    dqNode* dqn = (dqNode*)malloc(sizeof(dqNode));
    dqn->data = value;
    //第一次插入
    if (myCircularDequeIsEmpty(obj)) {
        obj->front = obj->rear = dqn;
        dqn->prev = dqn->succ = NULL;
    } else {
        obj->front->prev = dqn;
        dqn->succ = obj->front;
        dqn->prev = NULL;
        obj->front = dqn;
    }
    obj->size++;
    return true;
}

/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    //return obj->size == obj->capacity;
    if (myCircularDequeIsFull(obj))
        return false;
    dqNode* dqn = (dqNode*)malloc(sizeof(dqNode));
    dqn->data = value;
    if (myCircularDequeIsEmpty(obj)) {
        obj->front = obj->rear = dqn;
        dqn->prev = dqn->succ = NULL;
    } else {
        obj->rear->succ = dqn;
        dqn->prev = obj->rear;
        dqn->succ = NULL;
        obj->rear = dqn;
    }
    obj->size++;
    return true;
}

/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    //return obj->size == 0;
    if (myCircularDequeIsEmpty(obj))
        return false;
    if (obj->front == obj->rear) {
        dqNode* t = obj->front;
        obj->front = obj->rear = NULL;
        free(t);
    } else {
        dqNode* t = obj->front;
        obj->front = obj->front->succ;
        obj->front->prev = NULL;
        free(t);
    }
    obj->size--;
    return true;
}

/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    //return obj->size == 0;
    if (myCircularDequeIsEmpty(obj))
        return false;
    if (obj->front == obj->rear) {
        dqNode* t = obj->rear;
        obj->front = obj->rear = NULL;
        free(t);
    } else {
        dqNode* t = obj->rear;
        obj->rear = obj->rear->prev;
        obj->rear->succ = NULL;
        free(t);
    }
    obj->size--;
    return true;
}

/** Get the front item from the deque. */
int myCircularDequeGetFront(MyCircularDeque* obj) {
    //return obj->size == 0;
    if (myCircularDequeIsEmpty(obj))
        return -1;
    else
        return obj->front->data;
}

/** Get the last item from the deque. */
int myCircularDequeGetRear(MyCircularDeque* obj) {
    //return obj->size == 0;
    if (myCircularDequeIsEmpty(obj))
        return -1;
    else
        return obj->rear->data;
}

/** Checks whether the circular deque is empty or not. */
bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->size == 0;
    //return obj->front==NULL;
    //return obj->rear==NULL;
}

/** Checks whether the circular deque is full or not. */
bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return obj->size == obj->capacity;
}

void myCircularDequeFree(MyCircularDeque* obj) {
    while (myCircularDequeIsEmpty(obj)) {
        myCircularDequeDeleteFront(obj);
    }
    free(obj);
    return;
}

功能测试代码：

void test1() {
    MyCircularDeque* mydq;
    assert((mydq = myCircularDequeCreate(8)) != NULL);
    assert(true == myCircularDequeInsertFront(mydq, 5));
    assert(5 == myCircularDequeGetFront(mydq));
    assert(false == myCircularDequeIsEmpty(mydq));
    assert(true == myCircularDequeDeleteFront(mydq));
    assert(true == myCircularDequeInsertLast(mydq, 3));
    assert(3 == myCircularDequeGetRear(mydq));
    assert(true == myCircularDequeInsertLast(mydq, 7));
    assert(true == myCircularDequeInsertFront(mydq, 7));
    assert(true == myCircularDequeDeleteLast(mydq));
    assert(true == myCircularDequeInsertLast(mydq, 4));
    assert(false == myCircularDequeIsEmpty(mydq));
    return;
}

收获和疑惑

适度的抽象有助于对整体的把握。