数据结构--栈

线性表的定义

前面文章有讲过，线性表就是一次保存单个同类型元素，多个元素之间逻辑上连续
例子：数组，栈，队列，字符串

栈

1.1 栈和队列的特点

栈和队列都是操作受限的线性表。
前面学过的数组，链表，是可以菜任意位置插入和删除的
而栈和队列只能在一端插入元素和删除元素

1.2 栈的定义

只能在一端插入元素（栈顶），也只能从这一端取出元素（栈顶）

先看下入栈的动画：

再看下出栈的动画：

利用数组模拟栈，每次入栈从数组后面追加，数组开头是栈底，数组末尾为栈顶。

模拟实现栈思路

1、定义

定义stk[N]栈 top 为栈顶 因为栈是一种先进后出的结构。

2、实现初始化

top=-1对栈进行初始化，表示空

3、实现压栈和出栈

压栈 需要++top 然后读入即可 stk[++top]=x
出栈 只需 --top

4、判断栈是否为空

只要top>0栈就不为空
栈顶stk[top]

#include 

using 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];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Acwing 828

#include 

using 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")
        {
            //如果top>0 则输出no 否则输出yes
            cout << (top ? "NO" : "YES") << endl;
        }
        else{
            cout << stk[top] << 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

Acwing 830 单调栈

#include 

using 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;
}
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

时间复杂度

每个数只会进栈一次，出栈一次，整个时间复杂度是O(n)。

总结

学数据结构 最主要的还是要画图，先画一遍，代码自然就能够写了