顺序栈论文哪有下关于顺序栈的论文
栈与队列的应用开发
摘要:
栈与队列是两种重要的线性结构,它们被广泛应用在各种软件系统。 下面我们就来初步了解谈谈栈与队列的应用开发。
关键字:栈 队列 应用开发
一:栈的定义
栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。 同时表的另一端被称为栈底 (Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。
根据上述定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次...全部
栈与队列的应用开发
摘要:
栈与队列是两种重要的线性结构,它们被广泛应用在各种软件系统。
下面我们就来初步了解谈谈栈与队列的应用开发。
关键字:栈 队列 应用开发
一:栈的定义
栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。
同时表的另一端被称为栈底 (Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。
根据上述定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。
在图3。1（a）所示的栈中，元素是以a1，a2，a3，…，an的顺序进栈的，而退栈的次序却是an，…，a3，a2，a1。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出的线性表，简称为LIFO表。
在日常生活中也可以见到很多“后进先出”的例子，如：手枪子弹夹中的子弹，子弹的装入与子弹弹出膛均在弹夹的最上端进行，先装入的子弹后发出，而后装入的子弹先发出。又如：铁路调度站，都是栈结构的实际应用。
下面 给出栈的抽象数据类型的定义：
ADT Stack{
数据对象：D={ai|ai ElemSet,I=1。2…,n,n>=0}
数据关系：R1={〈ai-1,ai>|ai-1,ai D,I=2,…,n〉
约定AN端为栈顶，A1端为栈底。
ADT Stack
数据元素：可以是任意类型的数据，但必须属于同一个数据对象。
关系：栈中数据元素之间是线性关系。
基本操作：
（1） InitStack(S)
操作前提：S为未初始化的栈。
操作结果：将S初始化为空栈。
（2） ClearStack(S)
操作前提：栈S已经存在。
操作结果：将栈S置成空栈。
（3） IsEmpty(S)
操作前提：栈S已经存在。
操作结果：判栈空函数，若S为空栈则函数值为“TRUE真”，否则为“FALSE”。
（4） IsFull(S)
操作前提：栈S已经存在。
操作结果：判栈满函数，若S栈已满，则函数值为“TRUE”，否则为“FALSE”。
（5） Push(S,x)
操作前提：栈S已经存在。
操作结果：在S的顶部插入(亦称压入)元素x；若S栈未满，将x插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则，返回TRUE。
（6） Pop(S, x)
操作前提：栈S已经存在。
操作结果：删除(亦称弹出)栈S的顶部元素，并用x带回该值；
若栈为空，返回值为FALSE，表示操作失败，否则，返回TRUE。
（7） GetTop(S, x)
操作前提：栈S已经存在。
操作结果：取栈S的顶部元素。与Pop(S, x)不同之处在于GetTop(S,x)不改变栈顶的位置。
二:栈的应用开发
1。
数制转换
假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步，直到N等于零：
X = N mod d (其中mod为求余运算)
N = N div d (其中div为整除运算 )
在上述计算过程中，第一次求出的X值为d进制数的最低位，最后一次求出的X值为d进制数的最高位，所以上述算法是从低位到高位顺序产生d进制数各个数位上的数。
下面以d=2为例给出上述算法：输入任意一个非负十进制整数，打印输出与其相应的二进制数。由于上述计算过程是从低位到高位顺序产生二进制数各个数位上的数，而打印输出时应从高位到低位进行，恰好与计算过程相反。
根据这个特点，我们可以利用栈来实现，即将计算过程中依次得到的二进制数码按顺序进栈，计算结束后，再顺序出栈，并按出栈序列打印输出。这样即可得到给定的十进制数对应的二进制数。这是利用栈先进后出特性的最简单的例子。
2。 括号匹配问题
假设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如 ( [ { } ] ( [ ] ) )或( { ( [ ] [ ( ) ] ) } )等均为正确的格式，而 { [ ] } ) }或 { [ ( ) ] 或 ( [ ] }均为不正确的格式。
在检验算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。
当输入序列和栈同时变为空时，说明所有括号完全匹配。
3．表达式求值
表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。
操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。
三: 队列的定义
队列 (Queue) 是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出 (Fist In Fist Out，缩写为FIFO)的特性。
这与我们日常生活中的排队是一致的，最早进入队列的人最早离开，新来的人总是加入到队尾。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。假设队列为q = (a1，a2，…，an)，那么a1就是队头元素，an则是队尾元素。
队列中的元素是按照a1，a2，…，an的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在a1，a2，…，an-1都离开队列之后，an才能退出队列。
队列在程序设计中也经常出现。
一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。凡是申请输出的作业都从队尾进入队列。
下面我们给出队列的抽象数据类型定义：
ADT Queue
数据元素：可以是任意类型的数据，但必须属于同一个数据对象。
关系：队列中数据元素之间是线性关系。
基本操作：
（1） InitQueue(&Q)：初始化操作。
设置一个空队列。
（2） IsEmpty(Q)：判空操作。若队列为空，则返回TRUE，否则返回FALSE。
（3） EnterQueue(&Q，x)：进队操作。在队列Q的队尾插入x。
操作成功，返回值为TRUE，否则返回值为FALSE。
（4） DeleteQueue(&Q,&x)：出队操作。使队列Q的队头元素出队，并用x带回其值。操作成功，返回值为TRUE，否则返回值为FALSE。
（5） GetHead（Q,&x）：取队头元素操作。用x取得队头元素的值。操作成功，返回TRUE，否则返回值为FALSE。
（6） ClearQueue(&Q)：队列置空操作。
将队列Q置为空队列。
（7） DestroyQueue(&Q)：队列销毁操作。释放队列的空间。
四: 队列的应用开发
1．打印杨辉三角
在这一部分中，我们介绍利用队列打印杨辉三角形的算法。
杨辉三角形的特点是两个腰上的数字都为1，其它位置上的数字是其上一行中与之相邻的两个整数之和。所以在打印过程中，第i行上的元素要由第i-1行中的元素来生成。我们可以利用循环队列实现打印杨辉三角形的过程。
在循环队列中依次存放第i-1行上的元素，然后逐个出队并打印，同时生成第i行元素并入队。
2．键盘输入循环缓冲区问题
在操作系统中，循环队列经常用于实时应用程序。例如，当程序正在执行其它任务时，用户可以从键盘上不断键入所要输入的内容。
很多字处理软件就是这样工作的。系统在利用这种分时处理方法时，用户键入的内容不能在屏幕上立刻显示出来，直到当前正在工作的那个进程结束为止。但在这个进程执行时，系统是在不断地检查键盘状态，如果检测到用户键入了一个新的字符，就立刻把它存到系统缓冲区中，然后继续运行原来的进程。
当当前工作的进程结束后，系统就从缓冲区中取出键入的字符，并按要求进行处理。这里的键盘输入缓冲区采用了循环队列。队列的特性保证了输入字符先键入、先保存、先处理的要求，循环结构又有效地限制了缓冲区的大小，并避免了假溢出问题。
五: 结束语:
以上只是我的一点对 栈与队列的初步了解。不足之处,再所难免。还请老师多多批评指正!
栈的应用
栈和队列的应用非常之广，只要问题满足后进先出和先进先出原则，均可使用栈和队列作为其数据结构。
栈的应用
1、 数制转换
将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过"除B取余法"来解决。
【例】将十进制数13转化为二进制数。
解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。
分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。
转换算法如下：
typedef int DataType;//应将顺序栈的DataType定义改为整型
void MultiBaseOutput (int N,int B)
{//假设N是非负的十进制整数，输出等值的B进制数
int i;
SeqStack S;
InitStack(&S);
while(N){ //从右向左产生B进制的各位数字，并将其进栈
push(&S,N%B); //将bi进栈0<=i<=j
N=N/B;
}
while(!StackEmpty(&S)){ //栈非空时退栈输出
i=Pop(&S);
printf("%d",i);
}
}
除数制的转换外，栈还可用于解决括号匹配检查、行编辑处理和表达式求解等问题。
2、栈与递归
（1）递归
所谓递归是指：若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。
递归是一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰。
递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适。
（2）递归算法的设计步骤
第一步骤（递归步骤）：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题。
即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题。
第二步骤：确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件）。
【例】非负整数n的阶乘可递归定义为：
（3）栈在递归算法的内部实现中所起的作用。
①调用函数时：系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻栈的栈顶也要为其分配相应的空间。
因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。
注意：
参数表的内容为实参，返回地址是函数调用语句的下一指令的位置。
②被调函数执行完毕时：系统将运行时刻栈栈顶的活动结构退栈，并根据退栈的活动结构中所保存的返回地址将程序的控制权转移给调用者继续执行。
【例】Factorial（4）递归函数执行期间运行时刻栈的变化（不考虑局部变量temp的入出栈情况）。
。收起
