带限制线性表 栈
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了带限制线性表 栈,现在分享给大家,供学习和参考。文章包含2121字,纯文字阅读大概需要6分钟。
教程信息
一、什么是栈(stack)
栈是一种带限制的线性表,
栈只能从表的一端存取数据,另一端是封闭,
开口端被称为栈顶,封口端被称为栈底。
栈遵循"先进后出(LIFO)"的原则,即最先进栈的元素最后出栈。
例如图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。
栈的具体实现有两种——顺序栈(底层是数组)
、链栈(底层是链表)
。
在实际应用中,通常只会对栈执行以下两种操作:
1、向栈中添加元素,
此过程被称为"进栈
"(入栈或压栈);
2、从栈中提取出指定元素,
此过程被称为"出栈
"(或弹栈);
二、C/C++中的栈
1、C/C++中可以使用“数组”来表示栈
(1)进栈/压栈PUSH:元素进入栈
①设置指向栈顶的指针top,如果top>n(栈的最大容量),则给出溢出信息
②如果没溢出,top++,并为新的a[top]赋值
if (top < n) a[++top] = elem;
(2)出栈/弹栈POP:元素离开栈
①设置指向栈顶的指针top,如果top<=0(栈已经为空),则给出溢出信息
②如果没溢出,x=a[top],top--
if (top >= 0) { x = a[top]; top--; }
2、C/C++中可以使用“链表”来表示栈
(1)将链表头部作为栈顶的一端,可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作。
(2)在实现数据"入栈"操作时,需要将数据从链表的头部插入
(3)在实现数据"出栈"操作时,需要删除链表头部的首元节点
3、C++的STL中有stack容器来表示栈
1)stack 的定义与初始化:stack<int> st
,初始化方式与其他容器类似。
2)stack 的内部函数。
(1)增加元素
st.push(x)
:入栈(2)删除元素
st.pop()
:弹栈(3)控制函数
①
int x=q.top()
:获取栈顶元素②
st.empty()
:当 stack 栈中没有元素时,该成员函数返回 true;反之,返回 false③
st.size()
:返回 stack 栈中存储元素的个数
三、栈结构的典型应用情境
(一)函数调用与栈
函数调用和栈之间有密切的关系。在程序执行过程中,每当一个函数被调用时,系统都会为该函数创建一个新的栈帧(也称为活动记录或函数帧),用于存储函数的局部变量、参数值以及其他与函数调用相关的信息。
在函数调用期间,每个函数的栈帧都会被依次推入栈中,形成一个栈的层次结构。 被调用的函数会被推入栈顶,而调用函数会保持在栈底。 这样,当被调用的函数执行完毕后,它的栈帧会从栈中弹出,控制权回到调用函数。
栈的管理由编译器和运行时系统负责。编译器在编译过程中会为每个函数生成相应的栈帧代码,而运行时系统负责栈的分配和释放,确保函数调用和返回的正确执行。
(二)表达式与栈
C/C++中,表达式计算值本质上由栈实现。
(三)括号匹配与栈
C/C++中,表达式的括号匹配也由栈实现。
四、程序实现样例
例一:使用stack实现逆序输出数组
代码实现:
#include <bits/stdc++.h> using namespace std; int main() { int arr[5] = { 1, 2, 3, 4, 5 }; stack < int > myStack; for (int i = 0; i < 5; i++) { myStack.push(arr[i]); } while (myStack.empty() == false) { cout << myStack.top() << " "; myStack.pop(); } return 0; }
执行结果:
例二:使用stack实现十进制转二进制
代码实现:
#include <bits/stdc++.h> using namespace std; int main() { int decimalNumber; cin >> decimalNumber; stack < int > binaryStack; while (decimalNumber > 0) { binaryStack.push(decimalNumber % 2); decimalNumber /= 2; } while (binaryStack.empty() == false) { cout << binaryStack.top(); binaryStack.pop(); } return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供带限制线性表 栈的全部内容,希望教程文章能够帮你了解学习带限制线性表 栈,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-268.html