C++数据结构(栈)

栈是一种受限的线性表，将允许插入和删除的操作的一端称为栈顶，另一端称之为栈底，向栈中插入元素叫入栈，删除元素叫出栈。栈被称为是后进先出的线性表(LIFO)

顺序栈

顺序存储，即使用一段连续内存空间依次存储栈中数据。这里通过一维数组动态分配内存的方式保存数据

定义

代码如下:

#define InitSize 10
#define IncSize 5

template <typename T>
class SeqStack {
public:
    SeqStack(int length = InitSize);
    ~SeqStack();

public:
    bool Push(const T& e);
    bool Pop(T &e);
    bool GetTop(T &e);

    void DispList();
    init ListLength();

    bool IsEmpty();
    bool IsFull();

private:
    void IncreaseSize();

private:
    T *m_data;
    int m_maxsize;
    int m_top;
};

template <typename T>
SeqStack<T>::SeqStack(int length) {
    m_data = new T[length];
    m_maxsize = length;
    m_top = -1;
}

template <typename T>
SeqStack<T>::~SeqStack() {
    delete[] m_data;
}

操作

template <typename T>
bool SeqStack<T>::Push(const T& e) {
    if (IsFull() == true) {
        IncreaseSize();
    }
    m_top++;
    m_data[m_top] = e;
    return true;
}

// 顺序栈扩容
template <typename T> 
void SeqStack<T>::IncreaseSize() {
    T *p = m_data;
    m_data = new T[m_maxsize + IncSize];

    // 将数据复制到新区域
    for (int i = 0; i <= m_top; i++) {
        m_data[i] = p[i];
    }
    m_maxsize = m_maxsize + IncSize;
    delete[] p;
}

// 出栈
template<typename T>
bool SeqStack<T>::Pop(T& e) {
    if (IsEmpty() == true) {
        std::cout << "Empty Stack" << std::endl;
        return false;
    }
    e = m_data[m_top];
    m_top--;
    return true;
}

template <typename T>
bool SeqStack<T>::GetTop(T &e) {
    if (IsEmpty() == true) {
        std::cout << "Empty Stack" << std::endl;
        return false;
    }
    e = m_data[m_top];
    return true;
}

template <class T>
void SeqStack<T>::DispList() {
    for (int i = m_top; i >= 0; i--) {
        std::cout << m_data[i] << " ";
    }
    std::cout << std::endl;
}

template <class T>
int SeqStack<T>::ListLength() {
    return m_top + 1;
}

template <class T>
bool SeqStack<T>::IsEmpty() {
    if (m_top == -1) {
        return true;
    }
    return false;
}

template <class T>
bool SeqStack<T>::IsFull() {
    if (m_top >= m_maxsize - 1) {
        return true;
    }
    return false;
}

共享栈

两个顺序栈共享存储空间为共享栈，对于顺序栈来说，一个较大的缺点是保存数据的空间初始尺寸不好确定，如果太大就会浪费空间，如果太小就得等存满数据后进行扩容

假设有两个相同数据类型的顺序栈，开辟一块保存数据的空间后，让这两个栈同时使用，也就是共享这块空间，就可以最大限度利用这块空间了

代码实现：

#include <iostream>

#define InitSize 10
#define IncSize 5

template <typename T>
class ShareStack {
public:
    ShareStack(int length = InitSize) {
        m_data = new T[length];
        m_maxsize = length;
        m_top1 = -1;
        m_top2 = length;
    }

    ~ShareStack() {
        delete[] m_data;
    }

public:
    bool IsFull() {
        if (m_top1 == m_top2) {
            return true;
        }
        return false;
    }

    bool Push(int stackNum,const T &e) {
        if (IsFull() == true) {
            std::cout << "Full Stack" << std::endl;
            return false;
        }
        if (stackNum == 1) {
            m_top1++;
            m_data[m_top1] = e;
        } else {
            m_top2--;
            m_data[m_top2] = e;
        }
        return true;
    }

    bool Pop(int stackNum,T &e) {
        if (stackNum == 1) {
            if (m_top1 == -1) {
                std::cout << "Share Stack 1 Empty" << std::endl;
                return false;
            }
            e = m_data[m_top1];
            m_top1--;
        } else {
            if (m_top2 == m_maxsize) {
                std::cout << "Share Stack 2 Empty" << std::endl;
                return false;
            }
            e = m_data[m_top2];
            m_top2++;
        }
        return true;
    }

private:
    T *m_data;
    int m_maxsize;
    int m_top1;
    int m_top2;
};

int main(void) {
    ShareStack<int> shareobj(10);
    shareobj.Push(1,150);
    shareobj.Push(2,200);

    int eval2 = 0;
    shareobj.Pop(1,eval2);
    shareobj.Pop(1,eval2);

    return 0;
}

链式栈

链式栈就是链式存储方式实现的栈，本质上是一个受限的单链表

#include <iostream>

template <typename T>
struct StackNode {
    T data;
    StackNode<T> *next;
};

template <typename T>
class LinkStack {
public:
    LinkStack();
    ~LinkStack();
public:
    bool Push(const T &e);
    bool Pop(T& e);
    bool GetTop(T &e);
    void DispList();
    int ListLength();
    bool Empty();

private:
    StackNode<T> *m_top;
    int m_length;
};

template <typename T>
LinkStack<T>::LinkStack() {
    m_top = nullptr;
    m_length = 0;
}

template <typename T>
bool LinkStack<T>::Push(const T &e) {
    StackNode<T> *node = new StackNode<T>;
    node->data = e;
    node->next = m_top;
    m_top = node;
    m_length++;
    return true;
}

template <typename T>
bool LinkStack<T>::Pop(T &e) {
    if (Empty() == true) {
        return false;
    }
    StackNode<T> *p_willdel = m_top;
    m_top = m_top->next;
    m_length--;
    e = p_willdel->data;
    delete p_willdel;
    return true;
}

template <typename T>
bool LinkStack<T>::GetTop(T &e) {
    if (Empty() == true) {
        return false;
    }
    e = m_top->data;
    return true;
}

template <class T>
void LinkStack<T>::DispList() {
    if (Empty() == true) {
        return;
    }

    StackNode<T> *p = m_top;
    while (p != nullptr) {
        std::cout << p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
}

template <class T>
int LinkStack<T>::ListLength() {
    return m_length;
}

template <class T>
bool LinkStack<T>::Empty() {
    if (m_top == nullptr) {
        return true;
    }
    return false;
}

template <typename T>
LinkStack<T>::~LinkStack() {
    T tmpnousevalue = {0};
    while (Pop(tmpnousevalue) == true) {}
}

int main(void) {
    LinkStack<int> slinkobj;
    slinkobj.Push(12);
    slinkobj.Push(24);
    slinkobj.Push(48);
    slinkobj.Push(100);

    int eval3 = 0;
    slinkobj.Pop(eval3);
    slinkobj.DispList();

    return 0;
}

链式栈没有长度限制，不存在内存空间的浪费问题。但对于数据的入栈和出栈这些需要对数据进行定位的操作，顺序栈更加方便，而链式栈中的每个数据节点都需要额外的指针域以指向下一个数据节点，这会略微降低数据的存储效率，当然也会多占用一些内存。所以，如果要存储的数据数量无法提前预估，一般考虑使用链式栈，而如果数据的数量比较固定，可以考虑使用顺序栈。