C++线性表中的栈
在C++中，栈(Stack)是一种常见的线性数据结构，用于存储和管理数据。它的特点是先进后出，即最后入栈的元素会最先出栈。
下面是C++中使用数组实现栈的示例代码：
#include <iostream>
using namespace std;
#define MAX_SIZE 100 // 栈的最大容量
class Stack {
private:
int arr[MAX_SIZE]; // 存储栈中元素的数组
int top; // 栈顶指针，指向栈顶元素的下一个位置
public:
Stack() {
top = 0;
}
bool isEmpty() {
return top == 0;
}
bool isFull() {
return top == MAX_SIZE;
}
void push(int value) {
if (isFull()) {
cout << "Stack overflow!" << endl;
return;
}
arr[top++] = value;
}
int pop() {
if (isEmpty()) {
cout << "Stack underflow!" << endl;
return -1;
}
return arr[--top];
}
int peek() {
if (isEmpty()) {
cout << "Stack underflow!" << endl;
return -1;
}
return arr[top-1];
}
};
int main() {
Stack s;
s.push(1);
s.push(2);
s.push(3);
cout << s.pop() << endl; // 输出 3
cout << s.pop() << endl; // 输出 2
cout << s.peek() << endl; // 输出 1
return 0;
}在上面的示例代码中，我们定义了一个Stack类，该类包含一个整型数组arr和一个整型变量top。其中，arr用于存储栈中的元素，top指向栈顶元素的下一个位置。
Stack类包含了几个常用的方法，包括isEmpty()、isFull()、push()、pop()和peek()。其中，isEmpty()和isFull()方法用于判断栈是否为空和是否已满；push()方法用于将元素压入栈中；pop()方法用于弹出栈顶元素并返回其值；peek()方法用于返回栈顶元素的值但不弹出。
在main()函数中，我们首先创建了一个Stack对象s，然后向其中压入了三个元素。接着，我们依次弹出了栈顶的两个元素，并使用peek()方法查看了栈顶元素的值。
除了使用数组实现栈，C++中还可以使用链表来实现栈。下面是使用链表实现栈的示例代码：
#include <iostream>
using namespace std;
class Node {
public:
int value;
Node* next;
Node(int v) {
value = v;
next = nullptr;
}
};
class Stack {
private:
Node* top; // 栈顶指针，指向栈顶元素
public:
Stack() {
top = nullptr;
}
bool isEmpty() {
return top == nullptr;
}
void push(int value) {
Node* newNode = new Node(value);
newNode->next = top;
top = newNode;
}
int pop() {
if (isEmpty()) {
cout << "Stack underflow!" << endl;
return -1;
}
Node* nodeToPop = top;
int value = nodeToPop->value;
top = top->next;
delete nodeToPop;
return value;
}
int peek() {
if (isEmpty()) {
cout << "Stack underflow!" << endl;
return -1;
}
return top->value;
}
};
int main() {
Stack s;
s.push(1);
s.push(2);
s.push(3);
cout << s.pop() << endl; // 输出 3
cout << s.pop() << endl; // 输出 2
cout << s.peek() << endl; // 输出 1
return 0;
}在上面的示例代码中，我们定义了一个Node类和一个Stack类。Node类表示栈中的元素，包含一个整型变量value和一个指向下一个节点的指针next。Stack类包含一个指向栈顶元素的指针top。
Stack类包含了几个常用的方法，包括isEmpty()、push()、pop()和peek()。其中，isEmpty()方法用于判断栈是否为空；push()方法用于将元素压入栈中；pop()方法用于弹出栈顶元素并返回其值；peek()方法用于返回栈顶元素的值但不弹出。
在main()函数中，我们首先创建了一个Stack对象s，然后向其中压入了三个元素。接着，我们依次弹出了栈顶的两个元素，并使用peek()方法查看了栈顶元素的值。与使用数组实现栈不同，使用链表实现栈可以动态地添加或删除元素，而不需要预先指定栈的大小。
另外，使用链表实现栈的时候，需要注意内存管理的问题。在压入元素时，需要动态分配内存并将新节点的next指针指向当前的栈顶节点；在弹出元素时，需要删除被弹出的节点并将栈顶指针指向下一个节点。如果不注意内存管理，就可能会出现内存泄漏或者访问已释放的内存的情况。
在实际开发中，可以使用智能指针等工具来辅助管理内存，避免出现内存泄漏等问题。下面是使用智能指针实现链表栈的示例代码：
#include <iostream>
#include <memory>
using namespace std;
class Node {
public:
int value;
shared_ptr<Node> next;
Node(int v) {
value = v;
next = nullptr;
}
};
class Stack {
private:
shared_ptr<Node> top;
public:
Stack() {
top = nullptr;
}
bool isEmpty() {
return top == nullptr;
}
void push(int value) {
shared_ptr<Node> newNode = make_shared<Node>(value);
newNode->next = top;
top = newNode;
}
int pop() {
if (isEmpty()) {
cout << "Stack underflow!" << endl;
return -1;
}
shared_ptr<Node> nodeToPop = top;
int value = nodeToPop->value;
top = top->next;
return value;
}
int peek() {
if (isEmpty()) {
cout << "Stack underflow!" << endl;
return -1;
}
return top->value;
}
};
int main() {
Stack s;
s.push(1);
s.push(2);
s.push(3);
cout << s.pop() << endl; // 输出 3
cout << s.pop() << endl; // 输出 2
cout << s.peek() << endl; // 输出 1
return 0;
}在这个示例代码中，我们使用了std::shared_ptr智能指针来管理节点的内存。当一个节点不再被栈所引用时，智能指针会自动将其释放。这样可以避免手动管理内存时的繁琐和容易出错的问题，提高代码的可维护性。
