Aczy156

Algorithm11.3 数据结构 栈

[TOC]

数据结构 线性表 - 栈

1、通过STL库中的stack，直接可以使用的链表

2、通过手写栈

  • 利用「顺序表」实现：用数组来模拟容器，用变量来作为栈顶
  • 利用「链接表』实现：用链表实现
    • 链首做为栈底，链尾做为栈顶：栈顶添加O(n)，查看栈顶O(n)，栈顶移除O(n)
    • 链首做为栈顶，链尾做为栈底：栈顶添加O(1)，查看栈顶O(1)，栈顶移除O(1)

进出栈顺序问题 - 利用STL库中的栈进行实现

https://www.luogu.com.cn/problem/P4387

题目大意：给定进栈顺序和出栈顺序，根据进栈顺序来比对出栈顺序是否正确

1、push、pop、empty

#include <iostream>
using namespace std;
#define maxn 100010
int t, len, in[maxn], out[maxn], idx_out;
#include <stack>
stack<int> s;

int main() {
    scanf("%d", &t);
    while (t--) {
        // init
        idx_out = 1;
        scanf("%d", &len);
        for (int i = 1; i <= len; ++i) scanf("%d", &in[i]);
        for (int i = 1; i <= len; ++i) scanf("%d", &out[i]);
        for (int i = 1; i <= len; ++i) {
            s.push(in[i]);
            while ((s.top()) == out[idx_out]) {s.pop();idx_out++;if (s.empty()) break;}
        }
        if (!s.empty()) printf("No\n");
        else printf("Yes\n");
        while (!s.empty()) s.pop();
    }
    return 0;
}

进出栈顺序问题 - 利用手写栈进行实现

1、数据结构：用一个数组来模拟栈

stk[maxn]用做存放数据的容器，top用来做栈的唯一索引。【注意，堆用作存放数据的容器是myheap[maxn]，size用来做堆的唯一索引。】

2、基本操作：push、pop、empty

// push添加元素
void push(int x) {stk[++top] = x;}
// pop弹出栈顶元素
void pop() {top--;}
// 判断是否为空 => 就看栈顶的索引top的值即可，看索引是否是0，是0的话就代表栈顶
bool empty() {if (!top) return true;return false;}

AC代码

#include <iostream>
using namespace std;
#define maxn 100010
int t, stk[maxn], top, len, in[maxn], out[maxn], idx_out;

void push(int x) {stk[++top] = x;}
void pop() {top--;}
bool empty() { if(!top)return true;return false;}

int main() {
    scanf("%d", &t);
    while (t--) {
        // init
        top=0;idx_out=1;
        scanf("%d", &len);
        for (int i = 1; i <= len; ++i) scanf("%d", &in[i]);
        for (int i = 1; i <= len; ++i) scanf("%d", &out[i]);
        for (int i = 1; i <= len; ++i) {
            push(in[i]);
            while (stk[top] == out[idx_out]) {pop();idx_out++;if (empty())break;}
        }
        if (!empty()) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}
Posted on Feb 1, 2021