使用c++超详细解释数据结构中的顺序栈和链栈
在C++中，栈（Stack）是一种数据结构，它可以用来存储数据，并支持两种基本操作：压入（Push）和弹出（Pop）。栈的特点是后进先出（Last In First Out，LIFO），也就是最后压入的元素最先弹出。栈可以用数组或链表等数据结构来实现。
在C++中，STL（Standard Template Library）提供了一个名为stack的容器，用于实现栈。stack容器是一个适配器（Adapter），它使用了一种已有的容器作为其底层实现，例如vector，deque等。stack容器提供了以下一些常用的成员函数：
- push()：将一个元素压入栈顶。
- pop()：从栈顶弹出一个元素。
- top()：返回栈顶元素的引用，但不删除该元素。
- empty()：判断栈是否为空。
- size()：返回栈中元素的个数。
下面是一个使用stack容器实现栈的示例代码：
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s; // 定义一个int类型的栈
// 压入元素
s.push(1);
s.push(2);
s.push(3);
// 弹出并输出元素
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
return 0;
}
运行上述代码，将输出：3 2 1，说明栈的特点是后进先出。
顺序栈
除了stack容器以外，C++中还可以使用数组或链表等数据结构来实现栈。例如，下面是一个使用数组实现栈的示例代码：
#include <iostream>
using namespace std;
const int MAX_SIZE = 100; // 定义最大栈空间
class Stack {
private:
int data[MAX_SIZE]; // 栈的数据存储数组
int top; // 栈顶指针
public:
Stack() { // 构造函数，初始化栈顶指针为-1
top = -1;
}
void push(int value) { // 压入元素
if (top == MAX_SIZE - 1) { // 判断栈是否已满
cout << "Stack overflow!" << endl;
return;
}
top++; // 栈顶指针加1
data[top] = value; // 压入元素
}
void pop() { // 弹出栈顶元素
if (top == -1) { // 判断栈是否已空
cout << "Stack underflow!" << endl;
return;
}
top--; // 栈顶指针减1
}
int getTop() { // 获取栈顶元素
if (top == -1) { // 判断栈是否已空
cout << "Stack underflow!" << endl;
return -1;
}
return data[top]; // 返回栈顶元素
}
bool isEmpty() { // 判断栈是否为空
return (top == -1);
}
int size() { // 返回栈中元素的个数
return (top + 1);
}
};
int main() {
Stack s; // 定义一个栈
// 压入元素
s.push(1);
s.push(2);
s.push(3);
// 弹出并输出元素
while (!s.isEmpty()) {
cout << s.getTop() << " ";
s.pop();
}
cout << endl;
return 0;
}
运行上述代码，将输出：3 2 1。
链栈
下面是一个使用链表实现栈的示例代码：
#include <iostream>
using namespace std;
class Node { // 定义链表节点
public:
int data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
Node(int value) { // 构造函数
data = value;//存放栈顶元素，链栈的头指针就是栈顶
next = NULL;//空栈相当于头指针指向空
}
};
class Stack {
private:
Node* top; // 栈顶指针
public:
Stack() { // 构造函数，初始化栈顶指针为NULL
top = NULL;//构造一个空栈，栈顶指针指向空
}
void push(int value) { // 压入元素
Node* newNode = new Node(value); // 创建新节点
newNode->next = top; // 新节点指向当前栈顶节点
top = newNode; // 更新栈顶指针
}
void pop() { // 弹出栈顶元素
if (top == NULL) { // 判断栈是否已空
cout << "Stack underflow!" << endl;
return;
}
Node* delNode = top; // 记录要删除的节点
top = top->next; // 更新栈顶指针
delete delNode; // 释放删除节点的空间
}
int getTop() { // 获取栈顶元素
if (top == NULL) { // 判断栈是否已空
cout << "Stack underflow!" << endl;
return -1;
}
return top->data; // 返回栈顶元素
}
bool isEmpty() { // 判断栈是否为空
return (top == NULL);
}
int size() { // 返回栈中元素的个数
int count = 0;
Node* p = top;
while (p != NULL) {
count++;
p = p->next;
}
return count;
}
};
int main() {
Stack s; // 定义一个栈
// 压入元素
s.push(1);
s.push(2);
s.push(3);
// 弹出并输出元素
while (!s.isEmpty()) {
cout << s.getTop() << " ";
s.pop();
}
cout << endl;
return 0;
}
运行上述代码，将输出：3 2 1。在使用链表实现栈时，需要注意链表节点的定义和操作，以及链表头指针（即栈顶指针）的更新。
总之，栈是一种常用的数据结构，在C++中可以使用stack容器、数组、链表等数据结构来实现。在编写栈的实现代码时，需要注意栈的特点是后进先出，即最后压入的元素最先弹出，同时需要注意栈的空间限制和边界条件。
链栈入栈操作
链栈（Linked Stack）是一种使用链表实现的栈（Stack）数据结构，在C++中可以使用类（Class）来定义链栈。链栈的入栈（Push）操作就是将一个元素压入栈顶，下面是一个使用类实现链栈入栈操作的示例代码：
#include <iostream>
using namespace std;
class Node { // 定义链表节点
public:
int data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
Node(int value) { // 构造函数
data = value;
next = NULL;
}
};
class LinkedStack { // 定义链栈类
private:
Node* top; // 栈顶指针
public:
LinkedStack() { // 构造函数，初始化栈顶指针为NULL
top = NULL;
}
void push(int value) { // 入栈操作
Node* newNode = new Node(value); // 创建新节点
newNode->next = top; // 新节点指向当前栈顶节点
top = newNode; // 更新栈顶指针
cout << "Push " << value << " into the stack." << endl;
}
};
int main() {
LinkedStack s; // 定义一个链栈
// 入栈操作
s.push(1);
s.push(2);
s.push(3);
return 0;
}
在上述代码中，我们定义了一个Node类作为链表节点，其中data表示节点存储的数据，next表示指向下一个节点的指针。然后定义了一个LinkedStack类作为链栈，其中top表示栈顶指针。在push方法中，我们首先创建一个新节点，并将其指向当前栈顶节点，然后将栈顶指针更新为新节点，最后输出入栈操作的信息。
运行上述代码，将输出：
Push 1 into the stack.
Push 2 into the stack.
Push 3 into the stack.
这说明我们已经成功地进行了链栈的入栈操作。在实际使用中，我们可以根据需要修改push方法的实现，比如添加入栈元素的判断和处理等。
链栈的出栈操作
链栈（Linked Stack）是一种使用链表实现的栈（Stack）数据结构，在C++中可以使用类（Class）来定义链栈。链栈的出栈（Pop）操作就是将栈顶元素弹出，下面是一个使用类实现链栈出栈操作的示例代码：
#include <iostream>
using namespace std;
class Node { // 定义链表节点
public:
int data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
Node(int value) { // 构造函数
data = value;
next = NULL;
}
};
class LinkedStack { // 定义链栈类
private:
Node* top; // 栈顶指针
public:
LinkedStack() { // 构造函数，初始化栈顶指针为NULL
top = NULL;
}
void push(int value) { // 入栈操作
Node* newNode = new Node(value); // 创建新节点
newNode->next = top; // 新节点指向当前栈顶节点
top = newNode; // 更新栈顶指针
cout << "Push " << value << " into the stack." << endl;
}
void pop() { // 出栈操作
if (top == NULL) { // 判断栈是否已空
cout << "Stack underflow!" << endl;
return;
}
Node* delNode = top; // 记录要删除的节点
top = top->next; // 更新栈顶指针
cout << "Pop " << delNode->data << " from the stack." << endl;
delete delNode; // 释放删除节点的空间
}
};
int main() {
LinkedStack s; // 定义一个链栈
// 入栈操作
s.push(1);
s.push(2);
s.push(3);
// 出栈操作
s.pop();
s.pop();
s.pop();
s.pop();
return 0;
}
在上述代码中，我们在LinkedStack类中添加了pop方法，用于出栈操作。首先判断栈是否为空，如果是则输出“Stack underflow!”并返回；否则，我们记录要删除的节点，将栈顶指针更新为其下一个节点，输出出栈操作的信息，并释放删除节点的空间。
运行上述代码，将输出：
Push 1 into the stack.
Push 2 into the stack.
Push 3 into the stack.
Pop 3 from the stack.
Pop 2 from the stack.
Pop 1 from the stack.
Stack underflow!
这说明我们已经成功地进行了链栈的出栈操作。在实际使用中，我们可以根据需要修改pop方法的实现，比如添加出栈元素的返回值和异常处理等。