栈

一般考察出栈的顺序
出队顺序是否正确判断技巧：先出栈的元素，说明其前面的元素都是依次入栈没有出栈的，所以在它之前入栈的元素，顺序是一定的
例：1234依次次入栈，判断输出 4123是否正确
显然错误，因为4要先输出，123需要依次入栈，没有出栈，则输出只能为321，所以4先输出的答案只能是4321

1. 栈和队列具有相同的逻辑结构
2. 栈和队列是(限制存储点的线性结构)
3. 链栈的优势:通常不会出现满栈
4. n个元素依次进栈,出栈顺序排列种类$\frac{1}{n+1}C^n_r{2n}$n+11​Crn​2n
5. 一个栈的入栈序列为1,2,3,…,n,出栈序列是P1,P2,P3,…,Pn。若P2=3，则P3可能取值的个数是(n-1)。
6. 采用共享栈的好处:节省存储空间,降低发生上溢的可能
7. 下列关于栈的叙述中，错误的是( I III IV)。 .
   I. 采用非递归方式重写递归程序时必须使用栈
   II.函数调用时，系统要用栈保存必要的信息
   III. 只要确定了入栈次序，即可确定出栈次序
   IV.栈是一种受限的线性表，允许在其两端进行操作
   题解
   I.如斐波拉契数直接用for循环迭代
   III.入栈次序一定,但可以在任意时刻出栈,如汉诺塔
   IV.栈只能在一端进行操作
8. 设a, b,c,d,e,f以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为( D)。
   A. fedcba
   B. bcafed
   C. dcefba
   D. cabdef
9. [2009统考真题]设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S容量至少是©。
   A.1
   B.2
   C.3
   D.4
10. 设有一个顺序共享栈Share[0:n-1]，其中第一个栈顶指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是( A)，若top1初值为0，top2初值为n-1，则共享栈满条件是（B）
    A. top2 -top1 == 1
    B. top1-top2 == 1
    C. top1 == top2
    D.以上都不对

队列

一般考察队头指针和队尾指针在队空或队满或进行操作时的情况,尤其是循环队列,同时考察有限制的双端队列出队顺序

一、循环队列的几种情况
队头指针指向第一个元素,队头指针指向第一个元素前面位置
队尾指针指向最后一个元素,对尾指针指向最后一个指针后面位置
无论指向哪
插入元素一定在对尾rear++
删除元素一定在队头front++
假设初始第一个元素在0位置
(一) front:第一个元素 rear:最后一个元素
front=0 rear=n-1
判空:(rear+1)%n == front
队满:(rear+2)%n == front
长度:(rear-front+1+n)%n
(二) 队头:第一个元素前面位置 队尾:最后一个元素
front=n-1 rear=n-1
判空:rear == front
队满:(rear+1)%n == front
长度:(rear-front+n)%n
(三) 队头:第一个元素 队尾:最后一个元素后面位置
front=0 rear=0
判空:front == rear
队满:(rear+1)%n == front
长度:(rear-front+n)%n
(四) 队头:第一个元素前面位置 队尾:最后一个元素后面位置
front=n-1 rear=0
判空:(front+1)%n == rear
队满:rear== front
长度:(rear-front-1+n)%n
为了防止队空和队满判断条件一样,以上四种基本情况都有一个元素空间没有使用

二、队列的顺序输出
（一）队列是先进先出的操作，所以输出顺序只能有一种
例：依次输入1234，输出为1234
（二）两端输入，一端输出的双端队列
（三）两端输出，一端输入的双端队列

=========================================================

1. 栈和队列的主要区别在于(插入、删除操作的限定不一样)
2. 循环队列存储在数组A[0…n]中，入队时的操作为(rear= (rear+1) mod (n+1))
   解释:
   rear=n时可以存放,当rear=n+1时跳到下标0
3. 6.已知循环队列的存储空间为数组A[21], front指向队头元素的前一个位置,rear指向队尾元素，假设当前front和rear的值分别为8和3，则该队列的长度为( 16)。
   解释:
   len = (rear-front+n)%n=(3-8+21)%21=16
4. 最适合做链队的是带首尾指针的非循环单链表
5. 因为删除操作最适合在链队的首部进行,所以队头设在队链首部
6. 队链的删除操作在删除最后一个元素时,需要同时改变队头和队尾指针,使队头和队尾相等,其他情况只要移动队头指针
7. 若以1,2,3,4 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是( C)。
   A.1,2,3,4
   B.4,1,3,2
   C.4,2,3,1
   D.4,2,1,3
8. [2010统考真题]某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。
   若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是( C)。
   A. b,a,c,d, e
   B. d,b,a,c,e .
   C. d,b,c,a,e
   D. e,c,b,a,d
9. [2018统考真题]现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6 (1在队头)，S为空。若仅允许下列3种操作:①出队并输出出队元素;②出队并将出队元素入栈;③出栈并输出出栈元素，则不能得到的输出序列是( C)。
   A.1,2,5,6, 4,3
   B.2,3,4,5,6, 1
   C. 3,4,5,6,1,2
   D.6,5,4,3,2, 1

10.C