一、【模板】栈

C语言版

#include
#include
#include
#define INITSIZE 10

typedef int STD;

typedef struct Stack
{
    STD*base;
    int top;
    int size;
}ST;

void StackInit(ST*s)
{
    s->base=(STD*)malloc(sizeof(STD)*INITSIZE);
    s->top=0;
    s->size=INITSIZE;
}
void checkcapacity(ST*s)
{
    if(s->size==s->top)
    {
        s->size*=2;
        s->base=(STD*)realloc(s->base,sizeof(STD)*s->size);
    }
}
void push(ST*s,STD n)
{
    checkcapacity(s);
    s->base[s->top++]=n;
}
int StackEmpty(ST*s)
{
    return s->top>0?1:0;
}
void pop(ST*s)
{
    if(StackEmpty(s))
        printf("%d\n",s->base[--s->top]);
    else
        printf("error\n");
}
void top(ST*s)
{
    if(StackEmpty(s))
        printf("%d\n",s->base[s->top-1]);
    else
        printf("error\n");
}
int main()
{
    ST s;
    StackInit(&s);
    int n;
    scanf("%d",&n);
    int num;
    getchar();
    while(n--)
    {
        char fun[5]={0};
        scanf("%s %d",fun,&num);
        if(!strcmp(fun,"push"))
        {
            scanf("%d",&num);
            push(&s,num);
        }
        if(!strcmp(fun,"pop"))
            pop(&s);
        if(!strcmp(fun,"top"))
            top(&s);
    }
    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

C++版

使用vector容器作为栈的存储空间

#include
#include
using namespace std;
class stack
{
    vector<int>_data;
public:
    void push(int x)
    {
        _data.push_back(x);
    }
    void pop()
    {
        if(_data.size())
        {
            cout<<_data.back()<<endl;
            _data.pop_back();
        }
        else
            cout<<"error"<<endl;
    }
    void top()
    {
        if(_data.size())
            cout<<_data.back()<<endl;
        else
             cout<<"error"<<endl;
    }
};
int main()
{
    stack s;
    int n;
    cin>>n;
    while(n--)
    {
        string tmp;
        int num;
        cin>>tmp;
        if(tmp=="push")
        {
            cin>>num;
            s.push(num);
        }
        if(tmp=="pop")
            s.pop();
        if(tmp=="top")
            s.top();
    }
    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

时间复杂度:O(n),进行n次对栈的操作
空间复杂度:O(1),除必要栈存储空间

二、栈的压入、弹出序列

解法一:辅助栈(推荐)

题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。

//入栈：栈为空或者栈顶不等于出栈数组
while(j < n && (s.isEmpty() || s.peek() != popA[i])){
    s.push(pushA[j]);
    j++;
}

1
2
3
4
5
6

如果能按照这个次序将两个序列都访问完，那说明是可以匹配入栈出栈次序的。

• 准备一个辅助栈，两个下标分别访问两个序列。
• 辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
• 栈顶等于出栈数组当前元素就出栈。
• 当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。
  

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int n = pushV.size();
        //辅助栈
        stack<int> s;
        //遍历入栈的下标
        int j = 0;
        //遍历出栈的数组
        for(int i = 0; i < n; i++){
            //入栈：栈为空或者栈顶不等于出栈数组
            while(j < n && (s.empty() || s.top() != popV[i])){
                s.push(pushV[j]);
                j++;
            }
            //栈顶等于出栈数组
            if(s.top() == popV[i])
                s.pop();
            //不匹配序列
            else
                return false;
        }
        return true;
    }
};

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)，其中n为数组长度，最坏情况下需要遍历两个数组各一次
空间复杂度：O(n)，辅助栈空间最大为一个数组的长度

解法二:原地栈

方法一我们使用了一个辅助栈来模拟，但是数组本来就很类似栈啊，用下标表示栈顶。在方法一种push数组前半部分入栈了，就没用了，这部分空间我们就可以用来当成栈。原理还是同方法一一样，只是这时我们遍历push数组的时候，用下标n表示栈空间，n的位置就是栈顶元素。

• 用下标n表示栈空间，用j表示出栈序列的下标。
• 遍历每一个待入栈的元素，加入栈顶，即push数组中n的位置，同时增加栈空间的大小，即n的大小。
• 当栈不为空即栈顶n大于等于0，且栈顶等于当前出栈序列，就出栈，同时缩小栈的空间，即减小n。
• 最后若是栈空间大小n为0，代表全部出栈完成，否则不匹配。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        //表示栈空间的大小，初始化为0
        int n = 0;
        //出栈序列的下标
        int j = 0;
        //对于每个待入栈的元素
        for(int num : pushV){
            //加入栈顶
            pushV[n] = num;
            //当栈不为空且栈顶等于当前出栈序列
            while(n >= 0 && pushV[n] == popV[j]){
                //出栈，缩小栈空间
                j++;
                n--;
            }
            n++;
        }
        //最后的栈是否为空
        return n == 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

时间复杂度：O(n)，其中n为数组长度，最坏还是遍历两个数组
空间复杂度：O(1)，常数级变量，无额外辅助空间