数据结构和算法：06.递归和栈结构

递归和栈结构

• 知识点：

具体代码请看：NDKPractice项目的datastructure31recursionandstack

知识点：

1. 递归和循环的区别：

• 循环： 高效一些,循环能解决的问题递归也能解决
• 递归： 低效一些，递归能解决的问题循环不一定能解决

2. java 中的 stack（继承至 Vector）

• vector ：没指定大小的情况下，初始大小为 10,扩容为当前大小的一倍
• ArrayList ： 没指定大小的情况下，初始大小为 10,扩容为当前大小的二分之一

2. 数组实现栈结构

template<class E>
class ArrayStack {
private:
    // 栈顶元素的角标位置
    int top = -1;
    E *array = NULL;
    int size = 10; // 栈的初始大小
public:
    // 构造和析构
    ArrayStack();
    ~ArrayStack();

public:
    /**
     *  将元素压入栈中
     */
    void push(E e);

    /**
     *  获取栈顶的元素，不弹出
     */
    E peek();

    /**
     * 弹出栈顶元素
     */
    E pop();

    /**
     *  栈是否为空
     */
    bool isEmpty();

private:
    void growArray();
};

template<class E>
ArrayStack<E>::ArrayStack() {
    array = (E*)malloc(sizeof(E)*size);
}

template<class E>
ArrayStack<E>::~ArrayStack() {
    delete[] array;
}

template<class E>
void ArrayStack<E>::growArray(){
    size = size << 1;
    // 改变内存空间大小
    array = (E*) realloc(array,size * sizeof(E));
}

template<class E>
void ArrayStack<E>::push(E e) {
    if(top + 1 >= size)
        growArray(); // 扩容
    array[top++] = e;
}

template<class E>
E ArrayStack<E>::peek() {
    return array[top];
}

template<class E>
E ArrayStack<E>::pop() {
    assert(top >= 0);
    E e = peek();
    array[top--] = NULL;
    return e;
}

template<class E>
bool ArrayStack<E>::isEmpty() {
    return top < 0;
}

3. 链表实现栈结构

template<class E>
class Node {
public:
    E value = NULL;
    Node<E> *next = NULL;
public:
    Node(E value, Node<E> *next) : value(value), next(next) {
    }
};

template<class E>
class LinkedStack {
private:
    Node<E> *first = NULL; // 头结点
    int index = -1;
    Node<E> *top = NULL; // 栈顶元素
public:
    LinkedStack();

    ~LinkedStack();

public:
    /**
     *  将元素压入栈中
     */
    void push(E e);

    /**
     *  获取栈顶的元素，不弹出
     */
    E peek();

    /**
     * 弹出栈顶元素
     */
    E pop();

    /**
     *  栈是否为空
     */
    bool isEmpty();

private:
    Node<E> *node(int index);
};

template<class E>
Node<E> *LinkedStack<E>::node(int index) {

    if (index == 0)
        return first;
    else if (index < 0)
        return NULL;

    Node<E> *h = first;

    for (int i = 0; i < index; ++i) {
        h = h->next;
    }
    return h;
}


template<class E>
void LinkedStack<E>::push(E e) {
    Node<E> *new_node = new Node<E>(e, NULL);
    if (!first)
        first = new_node;
    else
        top->next = new_node;
    top = new_node;
    index++;
}

template<class E>
E LinkedStack<E>::peek() {
    return top;
}

template<class E>
E LinkedStack<E>::pop() {
    assert(index >= 0);
    E e = top->value;
    delete top;

    top = node(--index);
    return e;
}

template<class E>
bool LinkedStack<E>::isEmpty() {
    return index < 0;
}

template<class E>
LinkedStack<E>::LinkedStack() {}

template<class E>
LinkedStack<E>::~LinkedStack() {
    for (int i = 0; i < index; ++i) {
        delete(node(i));
    }

    first = NULL;
    top = NULL;
    index = -1;
}