手机个人网站制作教程,上海优化外包公司,网站架构设计图怎么做,绵阳企业网站建设线性表的定义 前面文章有讲过#xff0c;线性表就是一次保存单个同类型元素#xff0c;多个元素之间逻辑上连续 例子#xff1a;数组#xff0c;栈#xff0c;队列#xff0c;字符串 栈
1.1 栈和队列的特点
栈和队列都是操作受限的线性表。 前面学过的数组#xff0c;…线性表的定义 前面文章有讲过线性表就是一次保存单个同类型元素多个元素之间逻辑上连续 例子数组栈队列字符串 栈
1.1 栈和队列的特点
栈和队列都是操作受限的线性表。 前面学过的数组链表是可以菜任意位置插入和删除的 而栈和队列只能在一端插入元素和删除元素
1.2 栈的定义
只能在一端插入元素栈顶也只能从这一端取出元素栈顶
先看下入栈的动画
再看下出栈的动画
利用数组模拟栈每次入栈从数组后面追加数组开头是栈底数组末尾为栈顶。
模拟实现栈思路
1、定义
定义stk[N]栈 top 为栈顶 因为栈是一种先进后出的结构。
2、实现初始化
top-1对栈进行初始化表示空
3、实现压栈和出栈
压栈 需要top 然后读入即可 stk[top]x 出栈 只需 --top
4、判断栈是否为空
只要top0栈就不为空 栈顶stk[top]
#include iostreamusing namespace std;const int N 100010;// stk[N] 为栈 tt 为栈顶下标
int stk[N], tt;// 插入一个数, 栈顶
stk[ tt] x;// 弹出
tt --;// 判断栈是否为空
if(tt 0) not empty
else empty// 栈顶
stk[tt];Acwing 828
#include iostreamusing namespace std;const int N 100010;int m;
int stk[N], top;int main()
{cin m;while(m --){string op;int x;cin op;if(op push){cin x;stk[ top] x;}else if(op pop){-- top;}else if(op empty){//如果top0 则输出no 否则输出yescout (top ? NO : YES) endl;}else{cout stk[top] endl;}}return 0;
}Acwing 830 单调栈
#include iostreamusing namespace std;const int N 100010;int n;
int stk[N], tt;int main()
{cin n;for(int i 0; i n; i ){int x;cin x;while(tt stk[tt] x) tt --;if(tt) cout stk[tt] ;else cout -1 ;stk[ tt] x;}return 0;
}时间复杂度
每个数只会进栈一次出栈一次整个时间复杂度是O(n)。
总结 学数据结构 最主要的还是要画图先画一遍代码自然就能够写了
