c++栈（stack）详解
c++栈（stack）详解
一、引言
在编程和算法设计中，栈（Stack）是一种非常常见且重要的数据结构。栈遵循后进先出（LIFO, Last In First Out）的原则，即最后一个被添加到栈中的元素总是第一个被移除。本文将详细介绍栈的基本概念、操作以及在实际编程中的应用。
二、栈的基本概念
栈是一种线性数据结构。栈只允许在一端（称为栈顶）进行插入和删除操作。栈中没有元素时，称为空栈。栈的插入操作通常被称为“压栈”（push），而删除操作则被称为“弹栈”（pop）。
图1是一个初始的栈，含有元素1 7 2 1\space7\space21 7 2，
图2在栈顶插入了元素8 88，（注意是在栈顶插入，不能在栈尾插入)
图3在栈顶插入了元素2 22，
图4(第二行最右边)在栈顶删除了元素2 22，这时栈顶为8 88,
图5在栈顶删除了元素8 88，这时栈顶为1 11,
图6在栈顶删除了元素1 11，这时栈顶为7 77
仔细观察，可以发现栈的结构类似于将要洗的衣服叠在一起，后放上衣服堆的衣服（相当于入栈）会被先洗（后进先出），洗完以后就拿走晾干（相当于出栈）。
四、栈的实现方式
栈可以用数组或链表来实现。使用数组实现的栈在性能上通常优于链表，因为数组在内存中是连续的，访问速度快。然而，数组实现的栈在大小上通常是固定的，如果栈的大小超过数组的容量，就需要进行扩容操作，这可能会带来一定的性能开销。
链表实现的栈则更加灵活，可以根据需要动态地分配和释放内存。但是，链表中的元素在内存中并不是连续的，因此访问速度可能会慢一些。
(1) 数组实现：
#include <iostream>
#include <stdexcept>
class Stack {
private:
int top; // 栈顶指针
unsigned capacity; // 栈的最大容量
int* array; // 指向数组的指针
// 辅助函数，用于检查栈是否已满
bool isFull() const {
return top == capacity - 1;
}
// 辅助函数，用于检查栈是否为空
bool isEmpty() const {
return top == -1;
}
public:
// 构造函数
Stack(unsigned capacity) {
this->capacity = capacity;
top = -1;
array = new int[capacity];
}
// 析构函数
~Stack() {
delete[] array;
}
// 入栈操作
void push(int value) {
if (isFull()) {
throw std::out_of_range("Stack is full");
}
array[++top] = value;
}
// 出栈操作
int pop() {
if (isEmpty()) {
throw std::out_of_range("Stack is empty");
}
return array[top--];
}
// 查看栈顶元素
int peek() const {
if (isEmpty()) {
throw std::out_of_range("Stack is empty");
}
return array[top];
}
// 检查栈是否为空
bool isEmptyStack() const {
return isEmpty();
}
};
int main() {
Stack s(5); // 创建一个容量为5的栈
s.push(1);
s.push(2);
s.push(3);
std::cout << "Top element: " << s.peek() << std::endl; // 输出: 3
s.pop();
std::cout << "Top element after pop: " << s.peek() << std::endl; // 输出: 2
return 0;
}
(2).STL实现
#include <iostream>
#include <stack>
int main() {
// 创建一个空的int类型的栈
std::stack<int> s;
// 压栈（push）元素
s.push(1);
s.push(2);
s.push(3);
// 查看栈顶元素（不弹出）
std::cout << "栈顶元素是: " << s.top() << std::endl;
// 弹栈（pop）元素
s.pop();
std::cout << "弹出元素后，栈顶元素是: " << s.top() << std::endl;
// 检查栈是否为空
if (s.empty()) {
std::cout << "栈为空" << std::endl;
} else {
std::cout << "栈不为空" << std::endl;
}
// 获取栈的大小（元素数量）
std::cout << "栈的大小是: " << s.size() << std::endl;
return 0;
}
(3).链表实现
#include <iostream>
// 定义链表节点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 定义栈类
class Stack {
private:
ListNode* top; // 栈顶指针
public:
// 构造函数
Stack() : top(nullptr) {}
// 析构函数
~Stack() {
while (!isEmpty()) {
pop();
}
}
// 入栈操作
void push(int value) {
ListNode* newNode = new ListNode(value);
newNode->next = top;
top = newNode;
}
// 出栈操作
int pop() {
if (isEmpty()) {
throw std::out_of_range("Stack is empty");
}
ListNode* temp = top;
int value = temp->val;
top = top->next;
delete temp;
return value;
}
// 查看栈顶元素
int peek() const {
if (isEmpty()) {
throw std::out_of_range("Stack is empty");
}
return top->val;
}
// 检查栈是否为空
bool isEmpty() const {
return top == nullptr;
}
};
int main() {
Stack s;
// 压栈元素
s.push(1);
s.push(2);
s.push(3);
// 查看栈顶元素
std::cout << "栈顶元素是: " << s.peek() << std::endl;
// 弹栈元素
s.pop();
std::cout << "弹出元素后，栈顶元素是: " << s.peek() << std::endl;
// 检查栈是否为空
if (s.isEmpty()) {
std::cout << "栈为空" << std::endl;
} else {
std::cout << "栈不为空" << std::endl;
}
return 0;
}
五、栈的应用
1.函数调用栈：在大多数编程语言中，函数调用都是通过栈来实现的。当函数被调用时，它的局部变量、参数和返回地址等信息会被压入栈中。当函数返回时，这些信息会被弹出栈，并恢复到函数调用之前的状态。
2.表达式求值：在编译器中，栈经常用于后缀表达式的求值。例如，在计算算术后缀表达式时，可以使用栈来保存中间结果和操作数。
代码: \space\space\space\space (题目)
#include<bits/stdc++.h>
using namespace std;
char n;
struct Stack{
int top,a[100000];
void inti(){top=0;}
void push(int x){a[++top]=x;}
void pop(){if(top) top--;}
int empty(){if(top>0) return 0;else return 1;}
int quary(){return a[top];}
}z;
int main(){
z.inti();
while(cin>>n){
if(z.empty()){
if(n==')') {
cout<<"NO";
return 0;
}
}
if(n=='(') z.push(n);
if(n==')') z.pop();
}
if(z.empty()) cout<<"YES";
else cout<<"NO";
return 0;
}
- 浏览器后退/前进按钮：浏览器的后退和前进按钮实际上就是使用栈来实现的。当用户浏览网页时，每个访问过的页面都会被压入一个栈中。当用户点击后退按钮时，栈顶的页面会被弹出并显示给用户；点击前进按钮时，则会把之前弹出的页面再次压入栈中并显示。
六、总结
栈是一种非常重要的数据结构，它遵循后进先出的原则，并且在许多场景中都有广泛的应用。通过深入理解栈的基本概念、操作以及实现方式，我们可以更好地利用栈来解决实际问题。同时，栈也是学习和理解其他复杂数据结构（如队列、树、图等）的基础之一。
制作不易，给个赞吧c++栈（stack）详解
c++栈（stack）详解
一、引言
在编程和算法设计中，栈（Stack）是一种非常常见且重要的数据结构。栈遵循后进先出（LIFO, Last In First Out）的原则，即最后一个被添加到栈中的元素总是第一个被移除。本文将详细介绍栈的基本概念、操作以及在实际编程中的应用。
二、栈的基本概念
栈是一种线性数据结构。栈只允许在一端（称为栈顶）进行插入和删除操作。栈中没有元素时，称为空栈。栈的插入操作通常被称为“压栈”（push），而删除操作则被称为“弹栈”（pop）。
image
image
1459×739 18.4 KB
image
image
604×526 22.1 KB
图1是一个初始的栈，含有元素1 7 2 1\space7\space21 7 2，
图2在栈顶插入了元素8 88，（注意是在栈顶插入，不能在栈尾插入)
图3在栈顶插入了元素2 22，
图4(第二行最右边)在栈顶删除了元素2 22，这时栈顶为8 88,
图5在栈顶删除了元素8 88，这时栈顶为1 11,
图6在栈顶删除了元素1 11，这时栈顶为7 77
仔细观察，可以发现栈的结构类似于将要洗的衣服叠在一起，后放上衣服堆的衣服（相当于入栈）会被先洗（后进先出），洗完以后就拿走晾干（相当于出栈）。
四、栈的实现方式
栈可以用数组或链表来实现。使用数组实现的栈在性能上通常优于链表，因为数组在内存中是连续的，访问速度快。然而，数组实现的栈在大小上通常是固定的，如果栈的大小超过数组的容量，就需要进行扩容操作，这可能会带来一定的性能开销。
链表实现的栈则更加灵活，可以根据需要动态地分配和释放内存。但是，链表中的元素在内存中并不是连续的，因此访问速度可能会慢一些。
(1) 数组实现：
#include
#include
class Stack {
private:
int top; // 栈顶指针
unsigned capacity; // 栈的最大容量
int* array; // 指向数组的指针
// 辅助函数，用于检查栈是否已满
bool isFull() const {
return top == capacity - 1;
}
// 辅助函数，用于检查栈是否为空
bool isEmpty() const {
return top == -1;
}
public:
// 构造函数
Stack(unsigned capacity) {
this->capacity = capacity;
top = -1;
array = new int[capacity];
}
// 析构函数
~Stack() {
delete[] array;
}
// 入栈操作
void push(int value) {
if (isFull()) {
throw std::out_of_range("Stack is full");
}
array[++top] = value;
}
// 出栈操作
int pop() {
if (isEmpty()) {
throw std::out_of_range("Stack is empty");
}
return array[top--];
}
// 查看栈顶元素
int peek() const {
if (isEmpty()) {
throw std::out_of_range("Stack is empty");
}
return array[top];
}
// 检查栈是否为空
bool isEmptyStack() const {
return isEmpty();
}
};
int main() {
Stack s(5); // 创建一个容量为5的栈
s.push(1);
s.push(2);
s.push(3);
std::cout << "Top element: " << s.peek() << std::endl; // 输出: 3
s.pop();
std::cout << "Top element after pop: " << s.peek() << std::endl; // 输出: 2
return 0;
}
(2).STL实现
#include
#include
int main() {
// 创建一个空的int类型的栈
std::stack s;
// 压栈（push）元素
s.push(1);
s.push(2);
s.push(3);
// 查看栈顶元素（不弹出）
std::cout << "栈顶元素是: " << s.top() << std::endl;
// 弹栈（pop）元素
s.pop();
std::cout << "弹出元素后，栈顶元素是: " << s.top() << std::endl;
// 检查栈是否为空
if (s.empty()) {
std::cout << "栈为空" << std::endl;
} else {
std::cout << "栈不为空" << std::endl;
}
// 获取栈的大小（元素数量）
std::cout << "栈的大小是: " << s.size() << std::endl;
return 0;
}
(3).链表实现
#include
// 定义链表节点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 定义栈类
class Stack {
private:
ListNode* top; // 栈顶指针
public:
// 构造函数
Stack() : top(nullptr) {}
// 析构函数
~Stack() {
while (!isEmpty()) {
pop();
}
}
// 入栈操作
void push(int value) {
ListNode* newNode = new ListNode(value);
newNode->next = top;
top = newNode;
}
// 出栈操作
int pop() {
if (isEmpty()) {
throw std::out_of_range("Stack is empty");
}
ListNode* temp = top;
int value = temp->val;
top = top->next;
delete temp;
return value;
}
// 查看栈顶元素
int peek() const {
if (isEmpty()) {
throw std::out_of_range("Stack is empty");
}
return top->val;
}
// 检查栈是否为空
bool isEmpty() const {
return top == nullptr;
}
};
int main() {
Stack s;
// 压栈元素
s.push(1);
s.push(2);
s.push(3);
// 查看栈顶元素
std::cout << "栈顶元素是: " << s.peek() << std::endl;
// 弹栈元素
s.pop();
std::cout << "弹出元素后，栈顶元素是: " << s.peek() << std::endl;
// 检查栈是否为空
if (s.isEmpty()) {
std::cout << "栈为空" << std::endl;
} else {
std::cout << "栈不为空" << std::endl;
}
return 0;
}
五、栈的应用
1.函数调用栈：在大多数编程语言中，函数调用都是通过栈来实现的。当函数被调用时，它的局部变量、参数和返回地址等信息会被压入栈中。当函数返回时，这些信息会被弹出栈，并恢复到函数调用之前的状态。
2.表达式求值：在编译器中，栈经常用于后缀表达式的求值。例如，在计算算术后缀表达式时，可以使用栈来保存中间结果和操作数。
代码: \space\space\space\space (题目)
#include<bits/stdc++.h>
using namespace std;
char n;
struct Stack{
int top,a[100000];
void inti(){top=0;}
void push(int x){a[++top]=x;}
void pop(){if(top) top–;}
int empty(){if(top>0) return 0;else return 1;}
int quary(){return a[top];}
}z;
int main(){
z.inti();
while(cin>>n){
if(z.empty()){
if(n==‘)’) {
cout<<“NO”;
return 0;
}
}
if(n==‘(’) z.push(n);
if(n==‘)’) z.pop();
}
if(z.empty()) cout<<“YES”;
else cout<<“NO”;
return 0;
}
浏览器后退/前进按钮：浏览器的后退和前进按钮实际上就是使用栈来实现的。当用户浏览网页时，每个访问过的页面都会被压入一个栈中。当用户点击后退按钮时，栈顶的页面会被弹出并显示给用户；点击前进按钮时，则会把之前弹出的页面再次压入栈中并显示。
六、总结
栈是一种非常重要的数据结构，它遵循后进先出的原则，并且在许多场景中都有广泛的应用。通过深入理解栈的基本概念、操作以及实现方式，我们可以更好地利用栈来解决实际问题。同时，栈也是学习和理解其他复杂数据结构（如队列、树、图等）的基础之一。
制作不易，给个赞吧