C++用数组与链表实现栈与双向队列

前言

栈是以先进后出,后进先出,队列是先进先出的原则,一端队尾插入另一端队头取出,双向队列相当两头都可以插入数据,两头都可以取出数据。前文了解了ArrayList与LinkedList的实现后,栈与堆的实现就比较简单了

一：栈的实现

栈

1：Stack基类

template <class E>
class Stack {
protected:
    int len = 0;
public:
    virtual ~Stack();
    virtual int size();
    virtual bool isEmpty();
    //弹出
    virtual E pop() = 0;
    //获取栈顶不弹出
    virtual E peek() = 0;
    //栈中添加元素
    virtual bool push(const E &e) = 0;
};
template <class E>
Stack<E>::~Stack() {
}
template <class E>
int Stack<E>::size() {
    return len;
}
template <class E>
bool Stack<E>::isEmpty() {
    return len <= 0;
}

2： ArrayStack类

template <class E>
class ArrayStack : public Stack<E> {
private:
    int capacity = 10;
    E *datas = NULL;
public:
    ArrayStack();
    ~ArrayStack();
    E pop();
    E peek();
    bool push(const E &e);
};

template <class E>
ArrayStack<E>::ArrayStack() {
    this->datas = (E*) malloc(sizeof(E) * capacity);
}

template <class E>
ArrayStack<E>::~ArrayStack() {
    if (this->datas) {
        free(this->datas);
        this->datas = NULL;
    }
}

template <class E>
E ArrayStack<E>::pop() {
    assert(Stack<E>::len > 0);
    int index = Stack<E>::len - 1;
    E data = datas[index];
    Stack<E>::len--;
    return data;
}

template <class E>
E ArrayStack<E>::peek() {
    assert(Stack<E>::len > 0);
    return datas[Stack<E>::len - 1];
}

/**
 * 这里忽略扩充数组后大小超过int最大值
 * @tparam E
 * @param e
 * @return
 */
template <class E>
bool ArrayStack<E>::push(const E &e) {
    if (Stack<E>::len == capacity) //需要扩充
    {
        capacity += capacity >> 1;//扩充成原先的1.5倍
        this->datas = (E*) realloc(this->datas, sizeof(E) * capacity);
    }
    datas[Stack<E>::len] = e;
    Stack<E>::len++;
    return true;
}

3：LinkedStack类

template <class E>
class LinkedStack : public Stack<E> {
private:
    struct Node {
        E data;
        Node *next = NULL;
        Node(const E &data, Node *next) : data(data) {
            this->next = next;
        }
    };
    Node *popNode = NULL;
public:
    ~LinkedStack();
    E pop();
    E peek();
    bool push(const E& e);
};

template <class E>
LinkedStack<E>::~LinkedStack() {
    if (this->popNode) {
        Node *curr = this->popNode;
        while (curr)
        {
            Node *next = curr->next;
            delete curr;
            curr = next;
        }
        this->popNode = NULL;
    }
}

template <class E>
E LinkedStack<E>::pop() {
    assert(Stack<E>::len > 0 && this->popNode);
    Node *next = this->popNode->next;
    E data = this->popNode->data;
    delete this->popNode;
    this->popNode = next;
    Stack<E>::len--;
    return data;
}

template <class E>
E LinkedStack<E>::peek() {
    assert(Stack<E>::len > 0 && this->popNode);
    return this->popNode->data;
}

template <class E>
bool LinkedStack<E>::push(const E &e) {
    Node *newNode = new Node(e, this->popNode);
    this->popNode = newNode;
    Stack<E>::len++;
    return true;
}

二：这里介绍双向队列ArrayDeuqe的实现

前文中LinkedList已经实现了链表式的Deque

1：单向数组队列原理

队列不会像ArrayList那样会有操作中间某个index的数据,如果按照ArrayList那种原理的话,每次弹出第一个元素的时候,数组都要整体移动,这样大大降低了效率,所以要用到循环双向的数组原理

循环数组

单向队列的添加与删除

在队列中数组的大小必须为2的冥次, 在扩充的时候数组大小 <<1 原因可以参考前文位运算技巧

单向的添加与删除

单向队列扩充

单向队列扩充

双向队列的添加与删除

双向队列

2：ArrayDeque代码实现

template <class E>
class ArrayDeque {
private:
    static const int DEF_CAPACITY = 16;
    /**
     * 阀值
     */
    int initialCapacity;
    int len = 0;
    /**
     * 队列头位置与尾位置
     */
    int headIndex = 0;
    int backIndex = 0;
    E *datas;
    /**
     * 扩充数组
     */
    void grow();
public:
    ArrayDeque();
    ArrayDeque(int numElements);
    ~ArrayDeque();
    bool isEmpty();
    int size();
    /**
     * 从队列尾部添加
     */
    bool push(const E &e);
    /**
     * 弹出队首
     */
    E pop();
    /**
     * 取队首不弹出
     */
    E peek();
    /**
     * 从队列首部添加
     */
    bool pushFront(const E &e);
    /**
     * 弹出队尾数据
     */
    E popBack();
    E peekBack();
};

/**
 * 这里忽略扩充数组后大小超过int最大值
 * @tparam E
 */
template <class E>
void ArrayDeque<E>::grow() {
    int new_size = initialCapacity << 1;
    E *newDatas = (E*) malloc(sizeof(E) * new_size);
    int copyIndex = initialCapacity - backIndex;
    for (int i = 0; i < backIndex; i++) {
        newDatas[copyIndex + i] = datas[i];
    }
    for (int i = 0; i < copyIndex; i++) {
        newDatas[i] = datas[i + backIndex];
    }
    headIndex = 0;
    backIndex = initialCapacity;
    initialCapacity = new_size;
    free(this->datas);
    datas = newDatas;
}

template <class E>
ArrayDeque<E>::ArrayDeque() {
    initialCapacity = DEF_CAPACITY;
    this->datas = (E*) malloc(sizeof(E) * initialCapacity);
}

template <class E>
ArrayDeque<E>::ArrayDeque(int numElements) {
    if (numElements > DEF_CAPACITY) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >> 1);
        initialCapacity |= (initialCapacity >> 2);
        initialCapacity |= (initialCapacity >> 4);
        initialCapacity |= (initialCapacity >> 8);
        initialCapacity |= (initialCapacity >> 16);
        initialCapacity++;
    }
    this->datas = (E*) malloc(sizeof(E) * initialCapacity);
}

template <class E>
ArrayDeque<E>::~ArrayDeque() {
    if (this->datas) {
        free(this->datas);
        this->datas = NULL;
    }
}

template <class E>
bool ArrayDeque<E>::isEmpty() {
    return headIndex == backIndex;
}

template <class E>
int ArrayDeque<E>::size() {
    return this->len;
}

template <class E>
bool ArrayDeque<E>::push(const E &e) {
    headIndex = (headIndex - 1) & (initialCapacity - 1);
    datas[headIndex] = e;
    if (headIndex == backIndex) {//需要扩充
        grow();
    }
    this->len++;
    return true;
}

template <class E>
E ArrayDeque<E>::pop() {
    assert(this->len > 0);
    backIndex = (backIndex - 1) & (initialCapacity - 1);
    E data = datas[backIndex];
    this->len--;
    return data;
}

template <class E>
E ArrayDeque<E>::peek() {
    assert(this->len > 0);
    int popIndex = (backIndex - 1) & (initialCapacity - 1);
    return datas[popIndex];
}

template <class E>
bool ArrayDeque<E>::pushFront(const E &e) {
    datas[backIndex] = e;
    backIndex = (backIndex + 1) & (initialCapacity - 1);
    if (headIndex == backIndex) {//需要扩充
        grow();
    }
    this->len++;
    return true;
}

template <class E>
E ArrayDeque<E>::popBack() {
    assert(this->len > 0);
    E data = datas[headIndex];
    headIndex = (headIndex + 1) & (initialCapacity - 1);
    this->len--;
    return data;
}

template <class E>
E ArrayDeque<E>::peekBack() {
    assert(this->len > 0);
    return datas[headIndex];
}

最后附上源码https://github.com/youxiaochen/DataStructArrayLink

数据结构看10次都不如自己动手敲一次印象深,代码中如有错误欢迎指教

更多文章请关注:http://www.jianshu.com/u/b1cff340957c