栈和队列问题

⼀选择题1. 对于栈操作数据的原则是（）。

【青岛⼤学 2001 五、2（2分）】A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2.在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈是否(②)。

当栈中元素为n个,作进栈运算时发⽣上溢,则说明该栈的最⼤容量为(③ )。

为了增加内存空间的利⽤率和减少溢出的可能性,由两个栈共享⼀⽚连续的内存空间时,应将两栈的 ( ④ )分别设在这⽚内存空间的两端,这样,当( ⑤ )时，才产⽣上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中⼼点.B. 其中⼀个栈的栈顶到达栈空间的中⼼点.C. 两个栈的栈顶在栈空间的某⼀位置相遇.D. 两个栈均不空,且⼀个栈的栈顶到达另⼀个栈的栈底.【上海海运学院1997⼆、1（5分）】【上海海运学院1999⼆、1（5分）】3.⼀个栈的输⼊序列为123…n，若输出序列的第⼀个元素是n，输出第i （1<=i<=n）个元素是（）。

A. 不确定B. n-i+1C. iD. n-i【中⼭⼤学 1999 ⼀、9(1分)】4.若⼀个栈的输⼊序列为1,2,3,…,n，输出序列的第⼀个元素是i，则第j个输出元素是（）。

A. i-j-1B. i-jC. j-i+1D. 不确定的【武汉⼤学 2000 ⼆、3】5. 若已知⼀个栈的⼊栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN 是n，则pi是( )。

A. iB. n-iC. n-i+1D. 不确定【南京理⼯⼤学 2001 ⼀、1（1.5分）】6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪⼀个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 6【北⽅交通⼤学 2001 ⼀、3（2分）】7. 设栈的输⼊序列是1，2，3，4,则（）不可能是其出栈序列。

第3章栈和队列一、填空题1、栈是限定仅在表尾进行插入或删除操作的线性表。

2、栈的修改是按照后进先出的原则进行的。

3、队是一种先进先出的线性表。

4、把队列头尾相接的顺序存储结构称为循环队列。

5、队列也是一种操作受限的线性表，允许插入的一端叫做__队尾___，允许删除的一端叫做__队头__。

二、判断题1、栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。

（√）2、任何一个递归过程都可以转换成非递归过程。

（√）3、若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。

（√）4、通常使用队列来处理函数的调用。

（╳）5、循环队列通常用指针来实现队列的头尾相接。

（╳）三、单项选择题1、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（C）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（C）。

A．i B．n-i C．n-i+1 D．不确定解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

3、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（D）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

数据结构实验三栈和队列的应用数据结构实验三：栈和队列的应用在计算机科学领域中，数据结构是组织和存储数据的重要方式，而栈和队列作为两种常见的数据结构，具有广泛的应用场景。

本次实验旨在深入探讨栈和队列在实际问题中的应用，加深对它们特性和操作的理解。

一、栈的应用栈是一种“后进先出”（Last In First Out，LIFO）的数据结构。

这意味着最后进入栈的元素将首先被取出。

1、表达式求值在算术表达式的求值过程中，栈发挥着重要作用。

例如，对于表达式“2 ＋ 3 4”，我们可以通过将操作数压入栈，操作符按照优先级进行处理，实现表达式的正确求值。

当遇到数字时，将其压入操作数栈；遇到操作符时，从操作数栈中弹出相应数量的操作数进行计算，将结果压回操作数栈。

最终，操作数栈中的唯一值就是表达式的结果。

2、括号匹配在程序代码中，检查括号是否匹配是常见的任务。

可以使用栈来实现。

遍历输入的字符串，当遇到左括号时，将其压入栈；当遇到右括号时，弹出栈顶元素，如果弹出的左括号与当前右括号类型匹配，则继续，否则表示括号不匹配。

3、函数调用和递归在程序执行过程中，函数的调用和递归都依赖于栈。

当调用一个函数时，当前的执行环境（包括局部变量、返回地址等）被压入栈中。

当函数返回时，从栈中弹出之前保存的环境，继续之前的执行。

递归函数的执行也是通过栈来实现的，每次递归调用都会在栈中保存当前的状态，直到递归结束，依次从栈中恢复状态。

二、队列的应用队列是一种“先进先出”（First In First Out，FIFO）的数据结构。

1、排队系统在现实生活中的各种排队场景，如银行排队、餐厅叫号等，可以用队列来模拟。

新到达的顾客加入队列尾部，服务完成的顾客从队列头部离开。

通过这种方式，保证了先来的顾客先得到服务，体现了公平性。

2、广度优先搜索在图的遍历算法中，广度优先搜索（BreadthFirst Search，BFS）常使用队列。

从起始节点开始，将其放入队列。

栈和队列(答案)1. 一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是__ C __。

A. edcbaB. decbaC. dceabD. abcde2. 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为__ C __。

A. iB. n=iC. n-i+1D. 不确定3. 栈结构通常采用的两种存储结构是__ A __。

A. 顺序存储结构和链式存储结构散列方式和索引方式链表存储结构和数组线性存储结构和非线性存储结构4. 判定一个顺序栈ST(最多元素为m0)为空的条件是_ B ___。

A. top !=0B. top= =0C. top !=m0D. top= =m0-15. 判定一个顺序栈ST(最多元素为m0)为栈满的条件是__ D __。

A. top!=0B. top= =0C. top!=m0D. top= =m0-16. PUSH 和POP 命令常用于(C)操作。

A 队列B 数组C 栈D 记录7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时,则执行__ C __。

(不带空的头结点)A. HS—>next=s;B. s—>next= HS—>next; HS—>next=s;C. s—>next= HS; HS=s;D. s—>next= HS; HS= HS—>next;8. 从一个栈顶指针为HS的链栈中删除一个结点时,用x 保存被删结点的值,则执行_ B _ __。

(不带空的头结点)A. x=HS; HS= HS—>next;B. x=HS—>data;C. HS= HS—>next; x=HS—>data;D. x=HS—>data; HS= HS—>next;9. 一个队列的数据入队序列是1,2,3,4,则队列出队时的输出序列是__ B __ 。

第三章栈和队列练习题一、单项选择题1．一个顺序栈一旦被声明，其占用空间的大小（）。

A．已固定B．可以改变C．不能固定D．动态变化2．链栈和顺序栈相比，有一个比较明显的缺点，即（）。

A．插入操作更加方便B．通常不会出现栈满的情况C．不会出现栈空的情况D．删除操作更加方便3．用单链表表示的链式队列的队头在链表的（）位置。

A．链头B．链尾C．链中D．任意位置4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。

A．堆栈B．队列C．数组D．先性表5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…p n，若p1=30，则p10为（）。

A．11 B．20 C．19 D．216．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。

A．（rear+1)%m=front B．rear =front+1C．rear=front D．（rear+1)%m-1=front7．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。

A．top->next=p; B．p->next=top->next; top->next=p;C．p->next=top; top=p; D．p->next=top->next; top=top->next;8．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。

A．x=top;top=top->next; B．x=top->data;C．top=top->next; x=top->data; D．x=top->data; top=top->next;9．表达式a*(b+c)-d的后缀表达式是（）。

1. 对于栈操作数据的原则是（B ）。

A. 先进先出 B．后进先出 C．后进后出D．不分顺序2.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。

A．不确定B．n-i+1 C．i D．n-i3. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（D ）。

A．i-j-1 B．i-j C．j-i+1 D．不确定的4. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( D )。

A. i B．n-i C．n-i+1 D. 不确定5. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（C ）。

A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 66. 设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。

A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，E. 3，2，1，4，7. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( C )。

A．XYZ B. YZX C. ZXY D. ZYX8. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。

A．仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（C ）的数据结构。

A．队列 B．多维数组C．栈 D. 线性表1. 消除递归不一定需要使用栈，此说法（√ ）2. 栈是实现过程和函数等子程序所必需的结构。

（√ ）3. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。

（√ ）4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

第三章,栈和队列,练习题一、选择题1、栈结构通常采用的两种存储结构是。

A、顺序存储结构和链表存储结构B、散列和索引C、链表存储结构和数组D、线性链表和非线性存储2、设栈ST用顺序存储结构表示，则栈ST为空的条件是A、ST.top-ST.base0B、ST.top-ST.base==0C、ST.top-ST.basenD、ST.top-ST.base==n3、向一个栈顶指针为HS的链栈中插入一个s结点时，则执行A、HS->next=s;B、s->next=HS->next;HS->next=s;C、s->next=HS;HS=s;D、s->next=HS;HS=HS->next;4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行A、x=HS;HS=HS->next;B、HS=HS->next;x=HS->data;C、x=HS->data;HS=HS->next; D、s->next=Hs;Hs=HS->next;7、一个队列的入列序列是1，2，3，4，则队列的输出序列是//尾插入元素，头删除元素。

A、4，3，2，1B、1，2，3，C、1，4，3，D、3，2，4，19、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是//不懂啊！！！A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==%nD、Q.front!=%n11、用单链表表示的链式队列的队头在链表的位置A、链头B、链尾C、链中12、判定一个链队列Q为空的条件是A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==%nD、Q.front!=%n14、在一个链队列Q中，删除一个结点需要执行的指令是A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;15、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时 A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。

第一节栈
一、栈的定义及其运算
1、栈的定义
栈(Stack)：是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈项(top)，另一端称为栈底(bottom)。

不含元素的空表称为空栈。

栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(Last In First Out)的线性表，简称为LIFO表。

真题选解
（例题·填空题）1、如图所示，设输入元素的顺序是（A，B，C，D），通过栈的变换，在输出端可得到各种排列。

若输出序列的第一个元素为D，则输出序列为。

隐藏答案
【答案】DCBA
【解析】根据堆栈"先进后出"的原则，若输出序列的第一个元素为D，则ABCD入栈，输出序列为DCBA
2、栈的基本运算
(1)置空栈InitStack(&S)：构造一个空栈S。

第三章栈与队列习题及答案一、基础知识题3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。

(3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

3.2 链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

3.3 循环队列的优点是什么? 如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。

判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。

二是少用一个元素的空间。

每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。

三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。

若只设尾指针，则出入队时间均为1。

因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。

3.5 指出下述程序段的功能是什么?(1) void Demo1(SeqStack *S){int i; arr[64] ; n=0 ;while ( StackEmpty(S)) arr[n++]=Pop(S);for (i=0, i< n; i++) Push(S, arr[i]);} //Demo1(2) SeqStack S1, S2, tmp;DataType x;...//假设栈tmp和S2已做过初始化while ( ! StackEmpty (&S1)){x=Pop(&S1) ;Push(&tmp,x);}while ( ! StackEmpty (&tmp) ){x=Pop( &tmp);Push( &S1,x);Push( &S2, x);}(3) void Demo2( SeqStack *S, int m){ // 设DataType 为int 型SeqStack T; int i;InitStack (&T);while (! StackEmpty( S))if(( i=Pop(S)) !=m) Push( &T,i);while (! StackEmpty( &T)){i=Pop(&T); Push(S,i);}}(4)void Demo3( CirQueue *Q){ // 设DataType 为int 型int x; SeqStack S;InitStack( &S);while (! QueueEmpty( Q )){x=DeQueue( Q); Push( &S,x);}while (! StackEmpty( &s)){ x=Pop(&S); EnQueue( Q,x );}}// Demo3(5) CirQueue Q1, Q2; // 设DataType 为int 型int x, i , m = 0;... // 设Q1已有内容，Q2已初始化过while ( ! QueueEmpty( &Q1) ){ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); m++;}for (i=0; i< n; i++){ x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x);}二、算法设计题3.6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。