栈
栈是只能从一端插入或删除的特殊线性表
如图,栈就像通堆积物品一样,先堆积的在下面,取走时,只能从上往下一个个取。
1.进栈
viod push(int s[],int *top,int*x) { if(*top==n) printf("overflow");//检查栈是否已满 else {*top)++;s[*top]=*x; //未满的话栈指针+1,指向新栈地址,x元素进栈 } }
2.出栈
viod push(int s[],int *top,int*y) { if(*top==0) printf("underflow"); else {*y=s[*top];(*top)--; } }
#include <iostream> using namespace std; class SqStack { private: enum { MaxSize = 100 }; int data[MaxSize]; int top; public: SqStack(); ~SqStack(); bool isEmpty(); void pushint(int x); int popint(); int getTop(); void display(); }; SqStack::SqStack() { top = -1; } SqStack::~SqStack() {} bool SqStack::isEmpty() //判断栈为空 { return(top == -1); } void SqStack::pushint(int x)//元素进栈 { if (top == MaxSize - 1) { cout << "栈上溢出!" << endl; } else { ++top; data[top] = x; } } int SqStack::popint()//退栈 { int tmp = 0; if (top == -1) { cout << "栈已空!" <<endl; } else { tmp = data[top--]; } return tmp; } int SqStack::getTop()//获得栈顶元素 { int tmp = 0; if (top == -1) { cout << "栈空!" << endl; } else { tmp = data[top]; } return tmp; } void SqStack::display()//打印栈里元素 { cout << "栈中元素:" << endl; for (int index = top; index >= 0; --index) { cout << data[index] << endl; } } int main() { SqStack st; cout << "栈空:" << st.isEmpty() << endl; for (int i = 1; i < 10; i++) { st.pushint(i); } st.display(); cout << "退一次栈" << endl; st.popint(); cout << "栈顶元素:" << st.getTop() << endl; st.popint(); st.display(); return 0; }
题目背景
栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。
栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。
题目描述
宁宁考虑的是这样一个问题:一个操作数序列,1,2,\ldots ,n1,2,…,n(图示为 1 到 3 的情况),栈 A 的深度大于 nn。
现在可以进行两种操作,
- 将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作)
- 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)
使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由
1 2 3
生成序列2 3 1
的过程。(原始状态如上图所示)
你的程序将对给定的 nn,计算并输出由操作数序列 1,2,\ldots,n1,2,…,n 经过操作可能得到的输出序列的总数。
输入格式
输入文件只含一个整数 nn(1 \leq n \leq 181≤n≤18)。
输出格式
输出文件只有一行,即可能输出序列的总数目。
输入输出样例
输入 #13输出 #15说明/提示
【题目来源】
NOIP 2003 普及组第三题
#include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll f[MAX_N][MAX_N]; ll dfs(int i,int j) { if(f[i][j]) return f[i][j]; if(i==0)return 1; //边界 if(j>0) f[i][j]+=dfs(i,j-1); f[i][j]+=dfs(i-1,j+1); return f[i][j]; } int main() { scanf("%d",&n); printf("%lld",dfs(n,0)); return 0; } //递归转递推 递推做法 #include<cstdio> #define MAX_N 20 #define ll long long using namespace std; int n; ll f[MAX_N][MAX_N]; int main() { scanf("%d",&n); for(int i=0;i<=n;i++) { f[0][i]=1; } for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { if(i==j)f[i][j]=f[i-1][j]; else f[i][j]=f[i][j-1]+f[i-1][j]; } } printf("%lld",f[n][n]); return 0; }