1需求分析；（1）本题目是栈类模板的设计与实现，栈类模板是采；（2）设计的内容为：初始化栈操作，清空栈，判断是；（3）设计采用链式存储结构；2算法基本原理；(1)链式存储结构的栈称为链栈（Linked-s；进栈：对于链栈的进栈操作，需要让top引用指向新；（2）基本操作：；InitStack(S)；操作前提：S为未初始化的栈；操作结果：将S初始化为空栈；Cl
（1）本题目是栈类模板的设计与实现，栈类模板是采用C++语言将栈面向对象化，用C++语言设计了一个栈类模板，类带变了某一批对象的共性与特征，是用来定义对象的一种抽象类型。
（2）设计的内容为：初始化栈操作，清空栈，判断是否空栈，求栈的长度，返回栈顶元素，入栈出栈，栈的遍历，输出元素。
（3）设计采用链式存储结构。
2算法基本原理
(1)链式存储结构的栈称为链栈（Linked-stack）,对于链栈而言，栈顶元素不断改变，程序只有使用一个top引用来记录当前栈顶元素即可。Top引用变了永远引用栈顶元素，在使用一个size变量记录当前栈中包含多少元素。
进栈：对于链栈的进栈操作，需要让top引用指向新添加的元素，新元素的next引用执行原来的栈顶元素，同时记录栈内元素个数的size变量+1出栈：对于链栈的出栈操作，需要将栈顶元素弹出栈，程序需要让top引用执行原栈顶元素的下一个元素，并释放原来的栈顶元素，同时记录下栈内元素size变量-1.
（2）基本操作：
InitStack(S)
操作前提：S为未初始化的栈
操作结果：将S初始化为空栈
ClearStacck(S)
操作前提：栈S已经存在
操作结果：将栈S置成空栈
IsEmpty(S)
操作前提：栈S已经存在
操作结果：判断栈空函数，若S为空栈，则函数值为TRUE，否则为
Stacklength(S)
操作前提：栈S已经存在
操作结果：返回栈中元素的个数
Push(S，x)
操作前提：栈S已经存在
操作结果：在S的顶部插入元素，若S栈未满，将元素插入栈顶位置。
若已满，返回FALSE，表示操作失败，否则返回TRUE。
（3）首先要定义一个类为stack，其类型名为Th，操作分为九个步骤，具体步骤如下：
第1步，实现栈初始化操作，建立一个空栈stack。
第2步，实现清空栈的操作，执行clear语句，例如本题输入元素为5、7、9，执行clear语句，将其清空。
第3步，实现判断栈是否为空的操作，执行empty判断语句，对其进行判断，未清空前输出true，清空后输出false。
第4步，实现求栈长度的操作，例如本题输入元素5、7、9执行出栈操作后删除栈顶元素9，输出长度为2。
第5步，实现返回栈顶元素操作，本题输入元素5、7、9依次进栈顺序为9、7、5，然后执行返回栈顶语句，返回栈顶元素9。
第6步，实现入栈操作，例如本题输入元素5、7、9后依次入栈，为9、7、5。
第7步，实现出栈操作，本题中当执行返回栈顶元素9后，只剩下元素7、5，然后依次出栈。
第8步，实现栈的遍历操作输出栈的每一个元素，此题输出为9、7。第9步，将上述功能作为类的成员函数实现，编写主函数测试上述功能。
从上面的算法分析可以看到，本设计面临的主要问题是将这些要求作为类的成员函数，可以定义一个类stack,然后将这些要求作为该类的成员函数，该类主要分为公有变量和私有变量两部分，执行过程主要是公有变量里面的八个成员函数，然后分别利用主函数里面的函数分别对他们依次调用，完成对类的操作。类公有变量及私有变量相互关系如图1所示。
#check_for_validity():void
++clear():void
+boolempty()const
+size():unsignedint
+_Thtop()const
+push:void
+pop():void
+print_all()const:void
图1stack类和公有变量及私有变量UML图形表示
4基于控制台的应用程序
整个程序首先定义了一个类stack，然后在公有变量中分别定义九个成员函数，首先是建立一个空栈stack，随后实现清空栈操作，即执行voidclear（），后判断栈是否为空，执行boolempty（）函数，然后是求栈长度，执行size（）函数，在返回栈顶元素，执行thetop（）const，后分别是实现入栈及出栈操作，最后实现栈的遍历，输出栈的每一个元素，在私有变量中主要是对栈的检验，main函数为程序的主函数，通过调用成员函数些实现程序的运行。
4.1类的接口设计
//Linequ.h文件，实现类的声明
#include&iostream&
usingstd::
usingstd::
template&typename_Th&
structnode{
_Tnode&_Th&*
node(const_Th&data=_Th(),node&_Th&*link=0):
value(data),next(link){}};
template&typename_Th&
classstack{
stack(){header=newnode&_Th&(_Th(),0);}
voidclear(){while(!empty())pop();}
boolempty()const{return!header-&}
unsignedintsize()const{unsignedints=0;
for(node&_Th&*cur=cur-&cur=cur-&next)
_Thtop()const{
check_for_validity();
returnheader-&}
voidpush(const_Th&element){
node&_Th&*new_node=create_node(element,header);
header=new_
voidpop(){
if(empty())
node&_Th&*peek=
header=header-&
voidprint_all()const{
for(node&_Th&*cur=cur-&cur=cur-&next)
cout&&cur-&value&&&&;cout&&
node&_Th&*
template&typename_Type&
staticnode&_Th&*create_node(const_Type&value,node&_Th&*n){
returnnewnode&_Th&(value,n);
voidcheck_for_validity()const{
if(empty())throw0;//shouldthrowsomethingmoremeaningful
在开头的程序中定义一个结构体，然后定义了类stack，公有变量中包含了全部的成员函数，并且基类继承来的成员全部可以访问，而类中的私有变量时不可访问的。
4.2类的实现
//Linequ.cpp文件，类实现
#include&linequ.h&//包含类的声明头文件
//stack类的实现
stack(){header=newnode&_Th&(_Th(),0);}
voidclear(){while(!empty())pop();}
boolempty()const{return!header-&}
unsignedintsize()const{unsignedints=0;
for(node&_Th&*cur=cur-&cur=cur-&next)
_Thtop()const{
check_for_validity();
returnheader-&}
voidpush(const_Th&element){
node&_Th&*new_node=create_node(element,header);
header=new_
voidpop(){
if(empty())
node&_Th&*peek=
header=header-&
voidprint_all()const{
包含各类专业文献、生活休闲娱乐、外语学习资料、中学教育、幼儿教育、小学教育、93栈类模板的设计与实现等内容。　
　C++实现链栈(模版类)_计算机软件及应用_IT/计算机_专业资料。C++模版类实现链栈...如果只用到链栈您可以自己设计一个类解决,也可以直接用上面的代码。 ... 　栈的模板C++_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 栈的模板C++_计算机软件及应用_IT/计算机_专业资料。#include &Stack.h&... 　类模板用两个栈模拟一个队列_互联网_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 类模板用两个栈模拟一个队列_互联网_IT/计算机_专业资料。[类... 　我们准备用类模板实现栈类 的封装, 程序员就在使用栈类新建栈对象时只要传入数据类型就可以方便地对各种类型的数 据进行入栈、出栈等操作,提高程序员程序设计的... 　栈实现的实验报告模板 实验报告实验报告隐藏&& 附件2: 北京理工大学珠海学院实验...二、实验内容及要求说明 1:学生在上机实验时,需要自己设计出所涉及到的函数,... 　学会利用类对象作为参数,通过运算符的重载,实现模板更好的通用性。 二、实验内容与设计思想 实验内容与设计思想 内容与 以下是一个整数栈类的定义: 以下是一个... 　C++程序设计 实验报告 课程名称: 实验名称: 任课...[SIZE]; }; 编写一个栈的类模板(包括...在 向显示器进行输出时,要求用一下 3 种方式实现... 　} 10 模板 设计一个堆栈的类模板 Stack,在模板中用类型参数 T 表示栈中存放...(N=5) ,包括姓名和语数外三名课的成绩,通过重载&&和&& 运算符实现学生... 　数据结构实验报告4栈的实现_表格类模板_表格/模板_实用文档。数据结构实验报告(...数据结构课程设计报告之... 8页 2下载券 数据结构课程设计报告 二... 17页...问题描述：栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，&，n，经过一系列操作可能得到的输出序列总数。
分析：之前就有看过这种问题。就是火车进站问题，判断序列是否合法，当时是用STL栈做的。这个题只需统计次数，那么，方法就十分简便了，递归和动归都可以实现，当然用栈模拟当然也OK。值得一提的是网上看到的一个分析方法（引自石家庄铁道大学 刘莉等论文）
1&&&&&&引&言
在实际应用和数据结构课程的教学中，栈作为一种基本结构非常重要[1][3][4][6]。已知给定序列，求出栈序列的数目、求所有出栈的序列、以及判断某个序列是否为合法的出栈序列[5][7]，这类问题经常出现。在[3]中，对出栈序列的计数问题给出了介绍性的说明，由于结果的证明需要用到生成函数，[3]也只是直接给出了结论。本文提出使用&两点之间路径计数&的方法解决出栈序列的计数问题，在此基础上可以求所有出栈的序列，以及判断某个序列是否为合法的出栈序列。
2&&&&&&问题分析
&&&&&&&&&&&两点之间路径计数的问题
问题：假设A、B两点之间所有道路如图1中的方形网格线（5&5），规定从A到B只能够向右或向上移动，求A点到B点有几条路。
图1&两点之间路径计数问题的路径图
分析：因为规定从A到B只能够向右或向上移动，因此任意一点只能从该点的左邻点或下邻点到达，例如，任意一点C点只能从D点或E点到达。因此，从A点到C点的路只能由这两部分组成：①从A点到D点，再从D点到C点;②从A点到E点，再从E点到C点。
结论1：A点到任意一点C的路径数目=从A点到D点（C的左邻点）的路径数目+从A点到E点（C的下邻点）的路径数目
其中，由于A点正上方的点没有左邻点，而且问题中已规定从A到B只能够向右或向上运动，所以A点到A点正上方点的路径数目为1。同理，A点到A点正右方点的路径数目为1。
根据结论1，将A点到任意一点的路径数目求出，如图1中网格线交点处的数字所示。
&&&&&&&&&&&栈的操作与两点之间路径计数问题的操作的比较
栈的操作有两种：入栈、出栈。其中需要注意的问题有三个：①所有节点入栈之后只能出栈；②栈空时只能入栈；③其它情况下入栈、出栈任意执行。
两点之间路径计数问题的操作有两种：向右移动、向上移动。其中需要注意的问题有三个：①移到最右边后只能向上移；②移到最上边只能向右移；③其它情况下上移、右移任意执行。
由以上分析可见，栈的操作与两点之间路径计数问题的操作有很大的相似性，不妨将入栈和右移相关联，出栈和上移相关联。但是，这样关联之后，由于两个问题并不等价（例如，图1中的D点，按照栈的操作是不可到达的），所以需要对图1中的所有点进一步分析。
&&&&&&&&&&&对操作关联后图1中点的分析
首先，在图1中添加A点到B点的对角虚线。这条虚线将所有的点分成三类：①虚线上的点；②虚线左上方的点；③虚线右下方的点。
其次，按照两点之间路径计数问题规定的操作容易得出：①从A点移到虚线上每一个点时，所执行的右移操作次数和上移操作次数相等；②从A点移到虚线左上方每一个点时，所执行的右移操作次数小于上移操作次数；③从A点移到虚线右下方每一个点时，所执行的右移操作次数大于上移操作次数。
再次，由于栈操作过程中的任意时刻必须有：入栈操作次数&出栈操作次数（取等号时栈空）。
很明显，图1中虚线左上方的点按照栈的操作是不可到达的，虚线上的点恰好是栈空时的状态，虚线右下方的点按照栈的操作都可以到达，所以考虑修改图1中的路径图。
&&&&&&&&&&&改进后的路径图及规则
将图1中虚线左上方的点去掉后如图2所示（5&5方形网格线的下三角）。
图2&改造后的的路径图
规定：从A到B只能够向右或向上移动，右移为入栈操作，上移为出栈操作。
根据2.3的分析可得结论2：
①&&从A点到A点正右方的点的路径数目&=&1；
②&&从A点到每一行最左的点（考虑B点，不考虑A点）的路径数目&=从A点到该点的下邻点的路径数目；
③&&从A点到其它任意一点C的路径数目=从A点到D点（C的左邻点）的路径数目+从A点到E点（C的下邻点）的路径数目；
④&&按照栈的操作从A点开始到B点，图2中的所有点都是可到达的；
⑤&&4个节点的入栈、出栈操作完全包含在图2中；
⑥&&将⑤扩展得：N个节点的出栈、入栈操作完全包含在(N+1)&(N+1)方形网格线的下三角中。
在此仅对结论2第⑤点作一些说明：首先A点和对角线上的其它点表示栈空，只能入栈（右移）；其次，移到最右的竖边时所有的元素都已经入栈，只能出栈（上移）；再次，B点为最终状态，不能入栈也不能出栈；最后，其它的点可以任意入栈（右移）、出栈（上移）。所以4个节点的入栈、出栈操作完全包含在图2中。
从结论2中可以看到栈的操作与两点之间路径计数问题的操作在图2中是等价的。根据结论2，将A点到任意一点的路径数目求出，如图2中网格线交点处的数字所示，图2中虚线箭头表示了执行结论2第①点，图2中实线箭头表示了执行结论2第③点。
&&&&&&&&&&&结论2推广
将结论2加以推广得结论3：对于如图2的形式（(N+1)&(N+1)方形网格线的下三角），规定从A到B只能够向右或向上移动，右移为入栈操作，上移为出栈操作，所求A点到B点的路径数目就是N个节点出栈序列的数目，并且从A点到B点的每一条路都代表一种出栈序列。
3&&&&&&设计实现
求N个节点出栈序列数目的算法在具体实现时，采用由下向上逐行处理，每一行从左至右逐点处理的方法。此外，在&计算当前行的值时，只需要使用上一行的值；在计算各行中的每一个值时左邻点的值为数组中当前元素的前一个元素，下邻点为数组中当前元素，把数组中当前元素&的前一个元素加到当前元素上就求出了当前点的值，所以在具体实现时，只使用一个数组来保存当前行的值即可。由于最后一行只有一个数，也是该行的第一个数，&根据结论2第③点可知该数在倒数第二行中已经计算出来，所以该行不用计算，直接取上一行计算结果中的最后一个数即可。
4&&&&&&结论
该方法简单方便，不需要记忆任何公式[3]，特别适合没有组合数学基础的人员。另外，根据图2还可以设计算法将入栈、出栈的操作序列求出来，这样就可以得到所有的出栈序列。同时根据图2也可以判断某个序列是否为合法的出栈序列，可以解决[5][7]中车厢调度问题。
代码：分为递归和这个论文的算法求解
1、递归版本
#include&iostream&
int num,n;
//sz表示当前栈大小，i是指向等待调度序列的指针
void calcuNum(int i,int sz){
if(i&n){//所有序列都已处理完毕
calcuNum(i+1,sz+1);//入栈
if(sz&0)//出栈
calcuNum(i,sz-1);
int main()
calcuNum(1,0);
2、两点路径问题
#include&iostream&
#include&stack&
int num,n;
//sz表示当前栈大小，i是指向等待调度序列的指针
void calcuNum(int i,int sz){
if(i&n){//所有序列都已处理完毕
calcuNum(i+1,sz+1);//入栈
if(sz&0)//出栈
calcuNum(i,sz-1);
void path(){
int s[n+1][n+1];
for(int i=0;i&=n;i++) s[0][i]=1;
for(int i=1;i&=n;i++){
for(int j=1;j&=n;j++){
if(i & j) s[i][j] = s[i-1][j]+s[i][j-1];
if(i == j) s[i][j] = s[i-1][j];
num = s[n][n];
int main()
某列车调度站的铁道联接结构如Figure 1所示。
其中，A为入口，B为出口，S为中转盲端。所有铁道均为单轨单向式：列车行驶的方向只能是从A到S，再从S到B；另外，不允许超车。因为车厢可在S中驻留，所以它们从B端驶出的次序，可能与从A端驶入的次序不同。不过S的容量有限，同时驻留的车厢不得超过m节。
设某列车由编号依次为{1, 2, ..., n}的n节车厢组成。调度员希望知道，按照以上交通规则，这些车厢能否以{a1, a2, ..., an}的次序，重新排列后从B端驶出。如果可行，应该以怎样的次序操作?
第一行为两个整数n，m。
第二行为以空格分隔的n个整数，保证为{1, 2, ..., n}的一个排列，表示待判断可行性的驶出序列{a1，a2，...，an}。
若驶出序列可行，则输出操作序列，其中push表示车厢从A进入S，pop表示车厢从S进入B，每个操作占一行。
若不可行，则输出No
下面，是之前我在UVa上做的题解法（不完善）
#include &iostream&
#include&stack&
int const MAX = 1000;
int testOrder(int n)
stack&int&
int ch[MAX];
int curA=1,curB=1;
for(int i =1; i&=n; i++){
cin&&ch[i];
if(ch[i] ==0){
while(curB&=n){
if(ch[curB] == curA){
}else if(!train.empty() && ch[curB] == train.top()){
train.pop();
}else if(curA&=n){
train.push(curA++);
cout&&"No"&&
cout&&"Yes"&&
int main()
while(testOrder(n)==1);
if(n!=0) cout&&
}while(n != 0);
阅读(...) 评论()}