栈和队列习题

第3章栈和队列
课堂练习

1、栈和队列是 的线性表；
▲2、有一栈，元素A，B，C，D只能依次进栈,则出栈序列中以下哪

3、试写出队列中的出队算法。

习题
将出栈操作按任何次序夹入其中，请回答下述问题：
▲(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3), Pop(),
Pop(),则出栈的数字序列为何(这里Push(i)表示
Pop(),Push(4), i 进栈，Pop( )表示出栈)?

▲(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。

(3)请分析1，2，3，4的24种排列中，哪些序列是可以通过相应

1

▲3.3循环队列的优点是什么?如何判别它的空和满?

▲3.4设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?若只设尾指针呢?

3.5指出下述程序段的功能是什么?

(1) ▲void Demo1(SeqStack *S)
{ int i,arr[],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;
while ( ! StackEmpty (&S1))
{ x=Pop(&S1) ;
Push(&tmp,x);
}
while( ! StackEmpty (&tmp) )
x=Pop( &tmp); {
Push( &S1,x);

2

▲(3) void Demo2( SeqStack *S, int m)
{ // 设DataType为int 型
SeqStackT;
int i;
InitStack (&T);
while (!StackEmpty( S))
if(( i=Pop(S)) !=m) Push( &T,i);
while (! StackEmpty( &T))
{ i=Pop(&T);
Push(S,i);
}
{
// 设DataType为int 型 intx;
SeqStack S;
InitStack( &S);
while(! QueueEmpty( Q ))
{ x=DeQueue( Q);
Push(&S,x);

{ x=Pop(&S);
EnQueue( Q,x );
}
}// Demo3
(5) CirQueue Q1, Q2; // 设DataType为int 型
intx, i , m = 0;
... // 设Q1已有内容， Q2 已初始化过
while( ! QueueEmpty( &Q1) )
{ x=DeQueue( &Q1 ) ;EnQueue(&Q2, x); m++;}
for (i=0; i< m; i++)
{x=DeQueue(&Q2) EnQueue( &Q2, x);}
是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否
为回文。(提示：将一半字符入栈)
3.7 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void
ClearStack( SeqStack *S)，并说明S为何要作为指针参数?

3.8利用栈的基本操作，写一个返回S中结点个数的算法intStackSize( SeqStack S),并说明S为何不作为指针参数?

▲3.9 设计算法判断一个算术表达式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表 达式被扫描完毕，栈应为空。

4

3.10一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack( S ) 、入栈Push(S , i , x) 和出栈Pop(S , i )等算法，其中i为0或1，用以表示栈号。

▲3.11Ackerman 函数定义如下：请写出递归算法。

[ n+1 当m=0 时
AKM ( m , n ) = { AKM( m-1 ,1) 当m≠0，n=0 时
[ AKM( m-1, AKM( m,n-1)) 当m≠0,n ≠ 0 时
3.12 用第二种方法，即少用一个元素空间的方法来区别循环队列的
队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取
队头元素等六个基本操作的算法。
入队和出队等算法。

▲3.14对于循环向量中的循环队列，写出求队列长度的公式。

▲3.15假设循环队列中只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。

5