C++栈(stack)详解_c++ stack

作者：代码探险家 | 2024-08-12 15:30:58

踩

c++ stack

C++栈(stack)详解

一、引言

在编程和算法设计中，栈（Stack）是一种非常常见且重要的数据结构。栈遵循后进先出（LIFO, Last In First Out）的原则，即最后一个被添加到栈中的元素总是第一个被移除。本文将详细介绍栈的基本概念、操作以及在实际编程中的应用。

二、栈的基本概念

栈是一种线性数据结构。栈只允许在一端（称为栈顶）进行插入和删除操作。栈中没有元素时，称为空栈。栈的插入操作通常被称为“压栈”（push），而删除操作则被称为“弹栈”（pop）。
在这里插入图片描述

三、栈的基本操作

压栈（push）：在栈顶添加一个新元素。如果栈已满，则无法进行压栈操作。
弹栈（pop）：移除栈顶的元素，并返回该元素的值。如果栈为空，则无法进行弹栈操作。
查看栈顶（peek）：返回栈顶元素的值，但不移除该元素。如果栈为空，则无法进行查看栈顶操作。
判断栈是否为空（isEmpty）：检查栈中是否包含任何元素。
获取栈的大小（size）：返回栈中元素的数量。
在这里插入图片描述
图片解释:

图1是一个初始的栈，含有元素 $1\space7\space2$ ，
图2在栈顶插入了元素 $8$ ，（注意是在栈顶插入，不能在栈尾插入)
图3在栈顶插入了元素 $2$ ，
图4(第二行最右边)在栈顶删除了元素 $2$ ，这时栈顶为 $8$ ,
图5在栈顶删除了元素 $8$ ，这时栈顶为 $1$ ,
图6在栈顶删除了元素 $1$ ，这时栈顶为 $7$

仔细观察，可以发现栈的结构类似于将要洗的衣服叠在一起，后放上衣服堆的衣服（相当于入栈）会被先洗（后进先出），洗完以后就拿走晾干（相当于出栈）。

四、栈的实现方式

栈可以用数组或链表来实现。使用数组实现的栈在性能上通常优于链表，因为数组在内存中是连续的，访问速度快。然而，数组实现的栈在大小上通常是固定的，如果栈的大小超过数组的容量，就需要进行扩容操作，这可能会带来一定的性能开销。

链表实现的栈则更加灵活，可以根据需要动态地分配和释放内存。但是，链表中的元素在内存中并不是连续的，因此访问速度可能会慢一些。

(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;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

(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;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

(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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

五、栈的应用

函数调用栈：在大多数编程语言中，函数调用都是通过栈来实现的。当函数被调用时，它的局部变量、参数和返回地址等信息会被压入栈中。当函数返回时，这些信息会被弹出栈，并恢复到函数调用之前的状态。
表达式求值：在编译器中，栈经常用于后缀表达式的求值。例如，在计算算术后缀表达式时，可以使用栈来保存中间结果和操作数。
代码: $\space\space\space\space$ (题目)

#include <bits/stdc++.h>
using namespace std;
long long k,i,ans;
stack<int> v;
bool judgeopt(char x) {
	return x=='+'||x=='-'||x=='*'||x=='/';
}
int main() {
	string s;
	cin>>s;
	int l=s.size();
	for(;i<l-1;i++) {
		if(s[i]>='0'&&s[i]<='9') 
			k=10*k+(s[i]-'0');
		else if(s[i]=='.') 
			v.push(k),k=0;
		else if(judgeopt(s[i])) {
			int x=v.top();v.pop();
			int y=v.top();v.pop();
			if(s[i]=='+') 
				v.push(x+y);
			else if(s[i]=='-') 
				v.push(y-x);
			else if(s[i]=='*')
				v.push(x*y);
			else if(s[i]=='/')
				v.push(y/x);
		}
	}
	cout<<v.top();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

括号匹配：在解析文本或代码时，栈可以用于检查括号是否匹配。
代码: $\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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

浏览器后退/前进按钮：浏览器的后退和前进按钮实际上就是使用栈来实现的。当用户浏览网页时，每个访问过的页面都会被压入一个栈中。当用户点击后退按钮时，栈顶的页面会被弹出并显示给用户；点击前进按钮时，则会把之前弹出的页面再次压入栈中并显示。

六、总结

栈是一种非常重要的数据结构，它遵循后进先出的原则，并且在许多场景中都有广泛的应用。通过深入理解栈的基本概念、操作以及实现方式，我们可以更好地利用栈来解决实际问题。同时，栈也是学习和理解其他复杂数据结构（如队列、树、图等）的基础之一。

写作不易，留个赞吧！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/970365