C++数据结构之链表栈

这里我们通过C++实现一个链表栈结构，内核是链表，但是需要遵循栈的规则，并包含初始化空栈，判断栈是否为空，判断栈是否已满，插入元素，删除元素，获取栈顶元素，具体操作如下所示：

堆栈的基本操作

• 初始化空栈：使用列表创建一个空栈，并令栈顶元素指针 self.top 指向 None，即 self.top = None。
• 判断栈是否为空：当 self.top == None 时，说明堆栈为空，返回 True，否则返回 False。
• 插入元素（进栈、入栈）：创建值为 value 的链表节点，插入到链表头节点之前，并令栈顶指针 self.top 指向新的头节点。
• 删除元素（出栈、退栈）：先判断堆栈是否为空，为空直接抛出异常。如果堆栈不为空，则先使用变量 cur 存储当前栈顶指针 self.top 指向的头节点，然后令 self.top 沿着链表移动 1 位，然后再删除之前保存的 cur 节点。
• 获取栈顶元素：先判断堆栈是否为空，为空直接抛出异常。不为空则返回 self.top 指向的栈顶节点的值，即 self.top.value。

首先整体结构如下：

template <class T>
class Stack {

public:
    Stack();
    Stack(const Stack &list_head);
    ~Stack();

public:
    bool Empty();
    void Push(T &val);
    void Push(T &&val);
    void Pop();
    T Top();

public:
    int size() { return size_; }

private:
    typedef struct Node {
        T val;
        Node* next;
        Node(T x) :val(x), next(NULL) {};
    }ListHead;
    int size_;
    Node* top;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

如上图所示，这里定义了默认构造和拷贝构造，没定义有参构造。

然后是堆栈基础操作，判空，判满，入栈，出栈以及获取栈顶元素等操作。

最后还加了size()，用于判断链表中的数据是否存在。

数据成员则有两个，分别是当前的元素个数、栈指针。

接下来，我们看各自的实现。

1.初始化

template <class T>
Stack<T>::Stack():top(NULL),size_(0){}

template <class T>
Stack<T>::Stack(const Stack& list_head) {
    Node* cur = list_head.top;  //得到指针
    this->size_ = list_head.size_;
    while (cur) {
        Node* temp = new Node(cur->val); // 拷贝数据
        temp->next = this->top;
        this->top = temp;
        cur = cur->next;
    }
}

template <class T>
Stack<T>::~Stack() {
    if (this->top != NULL) {
        while (this->top != NULL) {
            Node* temp = top->next;
            delete top;
            top = temp;
        }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

上面三个分别为默认构造，拷贝构造和析构函数。

其中析构函数，对链表还剩余的节点都进行了析构。

拷贝构造函数，则是采用的深拷贝，重新在堆区开辟了空间。

2.判空

template <class T>
bool Stack<T>::Empty() {
    return NULL==top;
}
1
2
3
4

判空实现比较简单，top指针等于NULL就可以了。

3.压栈

template <class T>
void Stack<T>::Push(T &val) {
    Node* cur = new Node(val);
    cur->next = this->top;
    this->top = cur;
    this->size_++;
}

template <class T>
void Stack<T>::Push(T&& val) {
    Node* cur = new Node(val);
    cur->next = this->top;
    this->top = cur;
    this->size_++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这里压栈的值为自定义类型，虽然内部结构实现是指针，但是对外还是以正常数据类型进行压栈。

之所以还需要重载一个Push函数，是因为不能对右值取引用

4.出栈

template <class T>
void Stack<T>::Pop() {
    if (Empty()) {
        cout << "stack is empty" << endl;
    }
    else {
        size_--;
        Node* temp = top->next;  //移动一格
        delete top; //析构
        top = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

除了将top指针向前进一步之外，还需要进行节点的析构。

5.获取首部元素

template <class T>
T Stack<T>::Top() {
    if (Empty()) {
        cout << "stack is empty" << endl;
    }
    else {
        return this->top->val;
    }
}
1
2
3
4
5
6
7
8
9

直接通过首部的指针进行访问即可。

最后是测试代码：

测试了int和string两种数据类型，均可以实现。

int main()
{
    Stack<string> s;
    cout << s.Empty() << endl;
    s.Push("nihao");
    s.Push("wohao");
    s.Push("tahao");
    s.Push("dajiahao");
    s.Push("buhao");
    s.Pop();
    cout << s.size() << endl;

    Stack<string> test(s);  //测试拷贝构造函数
    while (!test.Empty()) {
        cout << test.Top() << "\t";
        test.Pop();
    }  cout << endl;

    /***************int****************/
    Stack<int> s_int;
    cout << s.Empty() << endl;
    s_int.Push(4);
    s_int.Push(5);
    s_int.Push(6);
    s_int.Push(8);
    s_int.Push(9);
    s_int.Pop();

    while (!s_int.Empty()) {
        cout << s_int.Top() << "\t";
        s_int.Pop();
    }  cout << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

老规矩，有用二连，感谢大家。