1 栈的基本概念与链表实现简介

栈是一种后进先出​（LIFO, Last In First Out）的线性数据结构，只允许在栈顶进行插入和删除操作。栈的两个基本操作是压栈​（push，将数据放入栈顶）和弹栈​（pop，从栈顶移出数据）

。除了栈顶的元素外，其他元素都不可直接访问或修改。

栈可以通过数组或链表来实现

。链表实现栈的主要优势在于它可以动态地分配内存，不需要预定义大小，从而避免了数组实现中可能出现的栈满情况，提高了内存利用率。链表实现的栈只需要一个链接结点即可表示栈，然后再用一个整型变量表示栈的长度。

在计算机科学中，栈被广泛应用于编程语言的解析、内存管理、函数调用和算法实现等方面

。本文将详细讲解如何使用C++中的链表来实现栈数据结构。

2 链表节点的定义与栈类的结构

2.1 链表节点定义

在链表实现的栈中，每个节点需要包含两个部分：

• ​数据域​：存储栈中的元素值
• ​指针域​：指向下一个节点的指针

template<typename T>
struct Node
{
    T data;
    Node* next;
    Node(T d) : data(d), next(nullptr) {};
};

上述代码定义了一个模板结构体Node，使用模板允许栈存储任意类型的数据。构造函数使用初始化列表来初始化节点的data和next指针，确保新创建的节点指向nullptr

。

2.2 栈类的结构

栈类需要维护两个核心成员变量：

• ​头指针​：指向栈顶节点的指针
• ​大小计数器​：记录当前栈中元素的数量

template<typename T>
class Stack
{
private:
    struct Node
    {
        T data;
        Node* next;
        Node(T d) : data(d), next(nullptr) {};
    };
    int size;
    Node* head;
    
public:
    Stack() : size(0), head(nullptr) {};
    ~Stack();
    void push(T element);
    T pop();
    T top() const;
    int getsize() const;
};

栈类提供了基本的栈操作接口，包括构造函数、析构函数、压栈、弹栈、获取栈顶元素和获取栈大小等方法

。

3 核心功能实现：压栈(push)与弹栈(pop)

3.1 压栈操作

压栈操作即在栈顶添加一个新元素，对应于链表的头插法。新节点的next指针指向当前栈顶节点，然后头指针更新为新节点

template<typename T>
void Stack<T>::push(T element)
{
    Node* newNode = new Node(element);
    newNode->next = head;
    head = newNode;
    size++;
}

​算法步骤​：

1. 创建一个新节点，存储要入栈的元素
2. 将新节点的next指针指向当前栈顶节点（head）
3. 更新head指针，使其指向新节点
4. 增加栈大小计数器

​时间复杂度​：O(1)，因为只需要固定数量的操作

3.2 弹栈操作

弹栈操作即移除并返回栈顶元素。需要先检查栈是否为空，然后保存栈顶节点的数据，更新头指针指向下一个节点，并释放原栈顶节点的内存

template<typename T>
T Stack<T>::pop()
{
    if (head == nullptr)
    {
        throw std::underflow_error("Stack is empty");
    }
    Node* temp = head;
    T data = head->data;
    head = head->next;
    delete temp;
    size--;
    return data;
}

​算法步骤​：

1. 检查栈是否为空，若空则抛出异常
2. 保存当前栈顶节点的指针和数据
3. 更新head指针，使其指向下一个节点
4. 释放原栈顶节点的内存
5. 减少栈大小计数器
6. 返回保存的栈顶数据

​时间复杂度​：O(1)，因为只需要固定数量的操作

。

4 辅助功能实现：获取栈顶(top)与大小(getsize)

4.1 获取栈顶元素

获取栈顶元素操作返回栈顶节点的数据而不移除它。需要先检查栈是否为空，然后直接返回头指针所指节点的数据

template<typename T>
T Stack<T>::top() const
{
    if (head == nullptr)
    {
        throw std::underflow_error("Stack is empty");
    }
    return head->data;
}

​时间复杂度​：O(1)，因为只需要访问一个节点

4.2 获取栈大小

获取栈大小操作直接返回栈的大小计数器值

template<typename T>
int Stack<T>::getsize() const
{
    return size;
}

​时间复杂度​：O(1)，因为只需要返回一个整数值

5 内存管理：析构函数的实现

析构函数负责在栈对象销毁时释放所有节点的内存，防止内存泄漏。它通过循环删除所有节点来实现这一点

template<typename T>
Stack<T>::~Stack()
{
    while (head)
    {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

​算法步骤​：

1. 循环遍历栈中的所有节点
2. 保存当前节点的指针
3. 将头指针移动到下一个节点
4. 删除保存的节点
5. 直到头指针为nullptr时停止

​时间复杂度​：O(n)，其中n是栈的大小，因为需要遍历所有节点

。

6 代码测试与输出结果

为了验证栈的实现是否正确，我们可以编写测试代码来测试各种操作

#include <iostream>
#include <stdexcept>
using namespace std;

// 此处插入上述Stack类的实现

int main()
{
    Stack<int> s;
    
    // 测试压栈操作
    s.push(1);
    s.push(2);
    s.push(3);
    cout << "当前栈顶元素: " << s.top() << endl; // 应输出3
    
    s.push(4);
    cout << "当前栈顶元素: " << s.top() << endl; // 应输出4
    
    // 测试弹栈操作
    s.pop();
    s.pop();
    cout << "弹栈两次后栈顶元素: " << s.top() << endl; // 应输出2
    
    cout << "当前栈大小: " << s.getsize() << endl; // 应输出2
    
    return 0;
}

​预期输出结果​：

当前栈顶元素: 3
当前栈顶元素: 4
弹栈两次后栈顶元素: 2
当前栈大小: 2

7 链表实现的优势与适用场景

相比于数组实现，链表实现栈有以下优点​

：

1. ​动态大小​：链表的大小可以动态增减，不需要事先指定容量。可以根据实际情况灵活地分配内存，避免了数组实现中固定大小带来的限制。
2. ​内存利用率高​：链表在需要增加或删除元素时，可以动态分配或释放内存，避免了固定容量带来的空间浪费。
3. ​高效的增删操作​：在链表中插入或删除元素的时间复杂度为O(1)，效率较高。

但链表实现也有一些缺点​

：

1. ​需要额外的指针​：链表节点除了存储元素本身的值，还需要一个指针来连接下一个节点，占用了额外的空间。
2. ​随机访问较慢​：链表中的元素不是连续存储的，无法像数组一样通过索引进行快速随机访问。

​适用场景​：

• 当需要频繁进行插入和删除操作，并且栈的大小不确定时，链表实现的栈是更好的选择。
• 在内存分配方面，链表实现的栈更加灵活，因为它不需要连续的内存空间。

总结

本文详细介绍了如何使用C++中的链表来实现栈数据结构。链表实现的栈具有动态扩容、内存利用率高和操作高效等优点，特别适合元素数量变化大的场景

。通过模板编程，我们可以实现一个类型安全且通用的栈数据结构，能够存储任意类型的数据。

与数组实现的栈相比，链表实现的栈在插入和删除操作上更加高效，但在随机访问和内存开销方面略有不足

。在实际应用中，应根据具体需求选择合适的实现方式。

掌握栈的链表实现不仅有助于理解栈的基本原理，还能加深对链表操作和内存管理的理解，为进一步学习更复杂的数据结构打下坚实基础。

有用的话可以点点赞和关注！！！

源码附上：

#include<iostream>
#include<string>
#include<algorithm>
#include<stdexcept>
using namespace std;
template<typename T>
class Stack
{private:
	struct Node
	{
		T data;
		Node* next;
		Node(T d) :data(d), next(NULL) {};
	};
	int size;
	 Node* head;
public:
	Stack() :size(0), head(NULL) {};
	~Stack();
	void push(T element);
	T pop();
	T top()const;
	int  getsize()const;
};
template<typename T>
Stack<T>::~Stack()
{
	while (head)
	{
		Node* temp = head;
		head = head->next;
		delete temp;
	}
}
template<typename T>
void  Stack<T>::push(T element)
{
	Node* newNode = new Node(element);
	newNode->next = head;
	head = newNode;
	size++;
}
template<typename T>
T Stack<T>::pop()
{
	if (head == NULL)
			 {
				 throw std::underflow_error("Stack is empty");
			 }
	Node* temp = head;
	head = head->next;
	delete temp;
	size--;
}
template<typename T>
T Stack<T>::top()const
{
	if (head == NULL)
	{
		throw std::underflow_error("Stack is empty");
	}

	return head->data;
}
template<typename T>
int Stack<T>::getsize()const
{
	return size;
}
int main()
{
	Stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	cout << s.top() << endl;
	s.push(4);
	cout << s.top() << endl;
	s.pop();
	s.pop();
	cout << s.top() << endl;
	cout << s.getsize() << endl;

	return 0;
}