栈的应用
标签: 机试攻略 - 高分篇
学习人数: 28.7k


高清播放
赞赏支持

栈是一种只能在一端进行插入和删除操作的数据结构,它满足先进后出的特性。

 

我们通过stack<int> S来定义一个全局栈来储存整数的空的stack。当然stack可以存任何类型的数据,比如stack<string> S等等。

 

#include <iostream>  
#include <stack>  
using namespace std;  
stack<int> S;  
int main() {  
    S.push(1);  
    S.push(10);  
    S.push(7);  
    while (!S.empty()) {  
      cout << S.top() << endl;  
      S.pop();  
    }  
    return 0;  
}  

 

只能使用C语言机试的同学直接用数组模拟栈即可。

//栈和队列都可以用数组模拟实现  
#include <stdio.h>  
  
int st[1005];//定义一个栈  
int main() {  
    int top = 0;//栈顶下标  
    st[++top] = 1;//将1入栈  
    st[++top] = 10;//将10入栈  
    st[++top] = 7;//将7入栈  
    while (top > 0) {//当栈不为空  
        printf("%d\n", st[top]);//输出栈顶元素  
        top--;//将栈顶元素出栈  
    }  
    return 0;  
}  


 

括号的匹配
题目描述:
假设表达式中允许包含两种括号:圆括号和方括号。编写一个算法判断表达式中的括号是否正确配对。
输入描述:
由括号构成的字符串,包含”(“、”)“、”[“和”]“。
输出描述:
如果匹配输出YES,否则输出NO。
输入样例#:
[([][]())]
输出样例#:
YES
题目来源:
DreamJudge 1501

题目解析:用栈模拟即可,和栈顶元素匹配就说明配对成功,将栈顶元素出栈,否则配对不成功,就将当前元素入栈。最后查看栈是否为空,若为空则是YES,否则就是NO。

 

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
int main() {  
    char s[300];  
    scanf("%s", &s);  
    int len = strlen(s);  
    stack<char> st;  
    for (int i = 0; i < len; i++) {  
        if (!st.empty()) {  
            char now = st.top();  
            if (s[i]==')...
登录查看完整内容


课后作业

练习题目

DreamJudge 1067 括号的匹配
DreamJudge 1296 括号匹配问题


登录后开始许愿

暂无评论,来抢沙发