如何实现一个简单的链表或栈结构

实现一个简单的链表或栈结构是面向对象编程中的基础任务。下面我将分别给出链表和栈的简单实现。

链表（单链表）的实现

链表是由一系列节点组成的集合，每个节点都包含数据部分和指向列表中下一个节点的链接（指针或引用）。

cpp复制代码

	#include <iostream>
	using namespace std;
	// 定义链表的节点
	struct ListNode {
	int val; // 节点存储的数据
	ListNode* next; // 指向下一个节点的指针
	// 构造函数
	ListNode(int x) : val(x), next(nullptr) {}
	};
	// 定义链表类
	class LinkedList {
	private:
	ListNode* head; // 链表的头节点
	public:
	// 构造函数
	LinkedList() : head(nullptr) {}
	// 析构函数（用于释放链表内存，这里为了简化省略）
	// 向链表末尾添加元素
	void append(int val) {
	ListNode* newNode = new ListNode(val);
	if (head == nullptr) {
	head = newNode;
	} else {
	ListNode* temp = head;
	while (temp->next != nullptr) {
	temp = temp->next;
	}
	temp->next = newNode;
	}
	}
	// 打印链表（为了演示）
	void print() {
	ListNode* temp = head;
	while (temp != nullptr) {
	cout << temp->val << " ";
	temp = temp->next;
	}
	cout << endl;
	}
	// 其他链表操作（如删除、查找等）可以按需添加
	};
	int main() {
	LinkedList list;
	list.append(1);
	list.append(2);
	list.append(3);
	list.print(); // 输出: 1 2 3
	return 0;
	}

栈的实现

栈是一种后进先出（LIFO）的数据结构，只能在一端（栈顶）进行添加（push）或删除（pop）元素的操作。

cpp复制代码

	#include <iostream>
	#include <stdexcept> // 用于抛出异常
	using namespace std;
	// 使用链表实现栈
	class Stack {
	private:
	ListNode* top; // 栈顶元素
	public:
	Stack() : top(nullptr) {}
	// 向栈中添加元素
	void push(int val) {
	ListNode* newNode = new ListNode(val);
	newNode->next = top;
	top = newNode;
	}
	// 从栈中删除元素
	int pop() {
	if (top == nullptr) {
	throw runtime_error("Stack is empty");
	}
	ListNode* temp = top;
	int val = top->val;
	top = top->next;
	delete temp;
	return val;
	}
	// 检查栈是否为空
	bool isEmpty() {
	return top == nullptr;
	}
	// 栈的其他操作（如查看栈顶元素但不删除等）可以按需添加
	};
	// 注意：ListNode 类已经在链表实现中定义，这里不再重复
	int main() {
	Stack stack;
	stack.push(1);
	stack.push(2);
	stack.push(3);
	while (!stack.isEmpty()) {
	cout << stack.pop() << " ";
	}
	// 输出: 3 2 1
	return 0;
	}

以上代码展示了如何使用C++中的类和结构来实现简单的链表和栈结构。链表通过节点间的链接来存储数据，而栈则通过限制只能在一端进行操作来实现后进先出的特性。