队列和栈

栈 栈的操作原则是：先进后出，后进先出二、栈的特点根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。 三、栈的运算 1.初始化栈：INISTACK(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：PUSH(&S,X)将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压入”。3.出栈： POP(&S) 删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。4.取栈顶元素： GETTOP(S)取栈S中栈顶元素。5.判栈空： EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。  栈总是处于栈空、栈满或不空不满三种状态之一，它们是通过栈顶指针top的值体现出来的。规定：top的值为下一个进栈元素在数组中的下标值。栈空时（初始状态），top=0;栈满时，top=MAXN. 三、栈的五种运算
（一） 进栈1） 进栈算法（1） 检查栈是否已满，若栈满，进行“溢出”处理。（2） 将新元素赋给栈顶指针所指的单元。（3） 将栈顶指针上移一个位置（即加1）。  （二） 出栈1） 出栈算法（1） 检查栈是否为空，若栈空，进行“下溢”处理。（2）将栈顶指针下移一个位置（即减1） 。（3）取栈顶元素的值，以便返回给调用者。 四．栈的共享存储单元有时，一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。 为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。 4、两个栈共享同一存储空间    　当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。    只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为 └ m/2┘和┌m/2┐的向量空间比较，前者发生上溢的概率比后者要小得多。  队列   1、定义    　队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表 （1）允许删除的一端称为队头（Front）。　　（2）允许插入的一端称为队尾（Rear）。　　（3）当队列中没有元素时称为空队列。　　（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。    　队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。 队列的存储结构： 顺序队列队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个数组来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置。  
1.队列先进先出，栈先进后出。2. 对插入和删除操作的"限定"。 栈是限定只能在表的一端进行插入和删除操作的线性表。      队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。     从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"限定"。     栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按"后进先出"的规则进行操作，而队列必须按"先进先出" 的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。3.遍历数据速度不同。栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"限定"。栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按"后进先出"的规则进行操作，而队列必须按"先进先出"的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。可将线性表和栈及队列的插入和删除操作对比如下：线性表 Insert(L,i,x)(1≤i≤n+1) Delete(L,i)(1≤i≤n) 如线性表允许在表内任一位置进行插入和删除 栈 Insert(L,n+1,x) Delete(L,n) 而栈只允许在表尾一端进行插入和删除 队列 Insert(L,n+1,x) Delete(L,1) 队列只允许在表尾一端进行插入，在表头一端进行删除-5