栈队列测试

栈和队列测试题

一、判断

1.队列中所有的插入操作都发生在表的一端，删除则发生在表的另一端

2.栈具有先进先出的特性

3.队列为先进后出的结构

4.栈用于实现子程序调用

5.栈、队列必须用数组来表示

6.队列用于操作系统中的作业调度

7.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

8.栈和链表是两种不同的数据结构。

9.栈和队列的存储方式既可是顺序方式，也可是链接方式。

二、单项选择

1．循环队列用数组A[maxsize] 表示，下面哪个选项表示该循环队列队满

(A) rear==maxsize-1 (B) front==(rear+1)%maxsize

(C) rear-front==maxsize (D) rear-front==maxsize-1

2．元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是

(A) dcba (B)abcd (C) dcab (D) cbad

3．链表仿真堆栈时，栈空的条件是

(A) top

4．在用数组queue[maxsize]仿真队列时(temp为int型变量)，假设队列中至少有一个元素，出队列操作应执行以下

(A) temp=queue[rear]；rear--； (B) rear++； temp=queue[rear]；

(C) temp=queue[front]；front--； (D) front++； temp=queue[front]；

5．在用链表仿真堆栈时(假设stack为栈顶指针)，将new指针指向的节点执行入栈操作应执行

(A) new->next=stack->next； stack=new； (B) new->next=stack； stack=new；

(C)new->next=stack；stack=new->next；(D) stack=new；stack->next=new->next；6．链表仿真堆栈时，栈满的条件是

(A) top

7．下列哪种数据结构常用于函数调用

(A) 堆栈 (B) 队列 (C) 链表 (D) 数组

8．编译器中通常以哪种数据结构处理递归程序调用

（A）队列（B）数组（C）堆栈（D）记录

9．下列哪些数据结构可用来实现堆栈

（1）链表（2）数组（3）树（4）图

（A）（2），（3）（B）（2），（4）（C）（1），（4）（D）（1），（2）

10．下列哪种数据结构常用于系统程序的作业调度

（A）栈（B）队列（C）链表（D）数组

11．栈和队列的共同点是

（A）都是先进后出（B）都是先进先出

（C）只允许在端点处插入和删除元素（D）没有共同点

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

Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

13．判定一个栈ST（最多元素为m0）为空的条件是

Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0

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

（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f （Ｄ）（n＋r－f）% n

15．用单链表表示的链式队列的队头在链表的位置

(A)链头(B)链尾(C)链中

16．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印.该缓冲区应该是一个结构.

(A)堆栈(B)队列(C)数组(D)线性表

17、判断一个队列QU（最多元素为m0）为空的条件是。

A. rear- front==m0

B. rear- front-1==m0

C. front== rear

D. front== rear+1

18、判断一个循环队列QU(最多元素为m0)为满队列的条件是。

A. front== rear

B. front!= rear

C. front==( rear+1)%m0

D. front!=( rear+1)%m0

19．一个队列（数组仿真，最多元素为MaxSize）下列哪个选项表示了队列空间全部被利用？

A.rear –front == MaxSize

B.rear –front == MaxSize –1

C.rear == front

D.rear + 1 == front

20．判定一个循环队列（数组仿真，最多元素为MaxSize）为空的条件是？

A. front == rear

B. front != rear

C. front == (rear + 1)%MaxSize

D. front != (rear + 1)%MaxSize

21、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？

A 1和5

B 2和4

C 4和2

D 5和1

22、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S 的容量至少应该是

a 6

b 4

c 3

d 2

三、 填空

1．栈和队列都是线性结构，对于栈只能在 栈顶 位置插入和删除元素，对于队列只能在 队尾 位置插入元素和 位置删除元素。

2．用大小为MaxSize 的数组仿真一个循环队列，front 和rear 分别记录该队列前后端的索引值，则该循环队列在某一状态下，队列中的元素个数为 。

3．在具有n 个单元的环状队列中，队满时共有 个元素。

4．堆栈、队列的建立可使用两种结构： 结构和 结构。

5、栈是一种特殊的线性表，允许插入和删除运算的一端称为 。不允许插入和删除运算的一端称为 。

6．表达式求值是（ ）应用的一个典型例子。

四、 简答

1．试写出执行函数之后的结果。

注：此为环状队列，且每次执行以上一次执行的结果为基础

－addqueue （）结果包含“队列数据内容”、“front ”、“rear ”及边界情况的输出 －delqueue （）结果包含“队列数据内容”、“front ”、“rear ”及输出数据值和边界情况的输出

3 2 1 0

（1） addqueue （30）

（2） delqueue （）

（3） addqueue(30)

2．试写出执行函数之后的结果。

注：此为堆栈，且每次执行以上一次执行的结果为基础

－push （）结果包含“堆栈数据内容”、“top ”及边界情况的输出

－pop （）结果包含“堆栈数据内容”、“top ”及输出数据值和边界情况的输出

3 2 1 0

（1） push （30）

（2） pop （）

（3） push(30)

3．什么是栈？什么是队列？试分别举两个应用实例。

4．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。

5．顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

6．设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

①front=11，rear=19; ②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

7、计算表达式6*3/2-5*1，要求绘出堆栈的处理过程

8、假设CQ[0,….10]是一个环状队列，初始状front=rear=1, 画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。

d, e, b, g, h入队；

d, e 出队；

I, j, k, l, m入队；

b出队；

n, o, p, q, r入队。

五、改错

1．以下语句是堆栈的入栈操作，用数组stack仿真堆栈，数组类型是int，大小是MaxSize，

栈顶指针是top,初始化等于－1。

01void push(int value)

02{

03if(top>MaxSize-1)

04return –1;

05else

06{

07top++;

08stack[top]=value;

09}

10}

指出有错误的语句：_____

写出改正后的语句：________

2、以下语句是数据从堆栈中取出操作,top为栈顶指针,stack为堆栈数组

01 int pop()

02 {

03 int temp;

04 if(top<0)

05 return –1;

06 else

07 {

08 temp = stack[top];

09 top ++;

10 }

11 return temp;

12 }

指出有错误的语句：_______________________

写出改正后的语句：_______________________

3．以下语句是环状队列的出队操作，用数组queue仿真环状队列，数组类型是int，大小是MaxSize，队尾指针是rear，队头指针是front。

01int delqueue()

02{

03int temp;

04if(front==rear)

05return –1;

06else

07{

08front++;

09temp=que ue[front];

10queue[front]=0;

11return temp;

12}

13}

指出有错误的语句：___________

写出改正后的语句：_____

3 栈和队列答案

第3章栈和队列 一、基础知识题 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的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 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);

数据结构考研真题 栈和队列

第3章栈和队列 一选择题 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+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p 1,p 2 ,p 3 ，…，p N ,若p N 是n，则 p i 是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 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， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是

实验二 堆栈和队列基本操作的编程实现

实验二堆栈和队列基本操作的编程实现 【实验目的】 堆栈和队列基本操作的编程实现 要求： 堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 内容： 把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。 利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。 【思考问题】 1.栈的顺序存储和链表存储的差异？ 2.还会有数据移动吗？为什么？ 3.栈的主要特点是什么？队列呢？ 4.栈的主要功能是什么？队列呢？ 5.为什么会有环状队列？ 【参考代码】 （一）利用顺序栈实现十进制整数转换转换成r进制 1、算法思想 将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下： N N / 8 （整除）N % 8（求余） 3456 432 0 低 432 54 0 54 6 6 6 0 6 高 所以：（3456）10 =（6600）8 我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。 算法思想如下：当N>0时重复1，2 ①若N≠0，则将N % r 压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。 ②用N / r 代替N 2、转换子程序

栈和队列习题答案

第三章栈和队列习题答案 一、基础知识题 设将整数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种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 链栈中为何不设置头结点 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (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]); } .. // 设Q1已有内容，Q2已初始化过 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的

数据结构第3章栈和队列自测题答案

一、填空题 二、1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的前一个位置。 5. 在具有n个单元的循环队列中，队满时共有n-1 个元素。 6. 向栈中压入元素的操作是先存入元素，后移动栈顶指针。 7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。 8. 带表头结点的空循环双向链表的长度等于0。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。） 三、（×）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （×）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU中也用队列。

（√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同 而已。 （×）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同 类项。 （×）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不 同而已。 （√）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分） （B）1. 栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出

实验二_栈、队列地实现与应用

实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：：

/*构造空顺序栈*/ int InitStack(SqStack *S) //InitStack() sub-function { S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) { printf("分配空间失败!\n"); return (ERROR); } S->top = S->base; S->stacksize = STACK_INIT_SIZE; printf("栈初始化成功！\n"); return (OK); } //InitStack() end /*取顺序栈顶元素*/ int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function { if (S->top == S->base) { printf("栈为空!\n"); //if empty SqStack return (ERROR); } *e = *(S->top - 1); return (OK); } //GetTop() end /*将元素压入顺序栈*/ int Push(SqStack *S) //Push() sub-function { SElemType e; if (S->top - S->base>S->stacksize) { S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType))); if (!S->base) { printf("存储空间分配失败!\n"); return (ERROR); } S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量x

数据结构第3章栈和队列自测卷答案(供参考)

head 1. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。） （每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU 中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ × ）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （ × ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底 分别设在这片内存空间的两端。 （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分） （ B ）1.栈中元素的进出原则是 Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出 （ C ）2.若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，则pi 为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n ，即n 是最先出栈的，根据栈的原理，n 必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n ，则出栈的序列是n ，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （ B ）3.判定一个栈ST （最多元素为m0）为空的条件是

数据结构 用两个栈模拟队列的操作

《数据结构》实验报告 ◎实验题目:用两个栈模拟队列的操作。 ◎实验目的：1、掌握使用Visual C++6.0上机调试程序的基本方法； 2、掌握栈与队列中的基本操作并学会灵活运用； 3、提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。 ◎实验内容：通过两个栈s1和s2模拟队列的进队操作，出队操作，对队满和队空的判断，遍历输出队列中的所有数据。 一、需求分析 1、输入的形式和输入值的范围：根据提示，输入序号以选择要进行的操作（进队、出队、结束），进行进队或出队前，需输入进队或出队数据的个数，再输入相应个数的数据。 2、输出的形式：在进队的数据输入完毕后后，输出已经进入队列的所有数据，若队已满存在未进入队列的数据，则输出相应的队满的提示；在输入出队数据的个数完成后，则输出要出队的所有数据，若队列中的数据个数小于操作者想要输出的数据个数，则提示队空，然后再输出出队后队列中的所有数据。 3、程序所能达到的功能：根据提示进行操作，模拟进队，出队，判断队满和队空，以及输出队列中的所有数据。 4、测试数据： 请选择要进行的操作(1.进队 2.出队 3.结束):1 请输入进队数据个数:14 输入数据:1 2 3 4 5 6 7 8 9 10 11 12 13 14 队已满,11未进入队列 队已满,12未进入队列 队已满,13未进入队列 队已满,14未进入队列 此时队列中的数据依次为:1 2 3 4 5 6 7 8 9 10 请选择要进行的操作(1.进队 2.出队 3.结束):2 请输入出队数据个数:3 出队的数据为:1 2 3 此时队列中的数据依次为:4 5 6 7 8 9 10 请选择要进行的操作(1.进队 2.出队 3.结束):2 请输入出队数据个数:10 出队的数据为:4 5 6 7 8 9 10 队空! 此时队列中已没有数据 请选择要进行的操作(1.进队 2.出队 3.结束):3 谢谢你的使用 二概要设计

栈和队列答案

栈和队列 一选择题 1. 对于栈操作数据的原则是（）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ②A)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为 p1,p2,p3，…，pN,若pN 是n，则pi 是( )。 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。 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， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2

数据结构第3章栈和队列自测卷答案

head 第3章 栈和队列 自测卷答案 班级 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU 中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ × ）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （ × ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是方式。 （ √ ）8. 两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别 设在这片存空间的两端。 （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分） （ B ）1.栈中元素的进出原则是 Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出 （ C ）2.若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，

实验二栈队列的实现及应用

百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct

1 2 3 4 5远 兀 1 一 7U- 元 谴 段 囑 :> o 1 2 3 R * 元 元 栈 書 t 出 一 ^ 零 遐 次 :± 谨 虚 1 2 3 ^ 5 I B

D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选 的 操 一 兀 一 b 一 丁 一 丁 栈 ? 遐 次 嘆 區 1 2 3 4 5 5 ^ 元 元 栈 S 退 、 灵 岀 祓 S I ■ i 9 I I I i 主 至 ..T' 一 兀 元 栈 ￡ 1 2 3 4 5 \Z

百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈 化 出 取 示 艮 i元一一 选 的 操 元 -> 入 中 >c 1- 苴翻（05）: 5 栈 化 亍 1 2 元 元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。 要求生成链栈时，从键盘上读取数据元素。 （1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode

数据结构第三章栈和队列习题及答案

习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front

第三章+栈和队列(参考答案)

第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。

本题15分请利用两个栈S1和S2来模拟一个队列。已

一、（本题15分）请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：Push(Stack ST,int x):元素x入ST栈；Pop(Stack ST,int x)：ST栈顶元素出栈，赋给变量x；StackEmpty(Stack ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：EnQueue:插入一个元素入队列； DeQueue:删除一个元素出队列；QueueEmpty：判队列为空。 解：利用两个栈S1、S2模拟一个队列（如客户队列）时，当需要向队列中输入元素时，用S1来存放输入元素，用push运算实现。当需要从队列中输出元素时，到栈S2中去取，如果S2为空，则将S1中的元素全部送入到S2中，然后再从S2中输出元素。判断队空的条件是：S1和S2同时为空。 Status EnQueue(DataType x) { if StackFull(S1){ //S1栈满 if StackEmpty(S2){ // S1栈满，S2栈空 while (!StackEmpty(S1)){ Pop(S1, y); Push(S2, y); //栈S1的内容反向搬到栈S2 Push(S1, x); return OK; } else //S1栈满，S2栈非空，则不可进行插入操作 return ERROR； } else{//S1栈不满，则直接进栈 Push(S1, x); return OK; } } Status DeQueue(DataType &x) { if !StackEmpty(S2) { Pop(S2, x);return OK; } else{ if !StackEmpty(S1){ while (!StackEmpty(S1)){ Pop(S1, y); Push(S2, y);} //栈S1的内容反向搬到栈S2 Pop(S2, x); return OK; } else //栈S1和S2都为空 return ERROR;

栈和队列练习题答案

第3章栈和队列练习题答案 一、填空题 1. 线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）3. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）6. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）7. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （D）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n E：①1 ②2 ③3 ④0 四、阅读理解 1.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); x=’c’;y=’k’;

数据结构-第3章栈和队列自测卷答案

head 第3章 栈和队列 自测卷答案 姓名 班级 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU 中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ × ）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （ × ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底 分别设在这片内存空间的两端。 （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分）

栈和队列自测题

第3章栈和队列自测卷 一、填空题 1. 向量(线性表)、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能 在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称 为。 3. 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的位置。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 向栈中压入元素的操作是先，后。 7. 从循环队列中删除一个元素时，其操作是先，后。 8. 带表头结点的空循环双向链表的长度等于。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （）5. 栈和链表是两种不同的数据结构。 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 三、单项选择题（每小题1分，共20分） （）1. 栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出

用两个栈模拟一个队列的操作

《数据结构》实验报告 ◎实验题目: 用两个栈模拟一个队列的操作 ◎实验目的：1.了解栈与队列的操作规则； 2.熟悉栈的基本操作； 3.掌握使用visual c++6.0上机调试程序的基本方法。 ◎实验内容：用两个栈模拟一个队列的操作。 一、需求分析 说明程序设计的任务，强调的是程序要做什么，明确规定： 1、入队值均为整型元素； 2、当队空时输出“队空”，当队满时输出“队满”，其他情况输出均为整型元素； 3、程序所能达到的功能：通过两个栈中元素的出栈与进栈来模拟队中元素的操作规则； 4、测试数据：本程序中先为选择部分，选择j代表有元素要入队，选择c代表有元素要出队，e代表结束，其他时为选择错误： （1）选择f，下一步需要输入需要进队的元素，本实验要求队中元素均为整型元素，按回车键，则会输出现有队中元素，均为整型元素； （2）选择c，然后选择出栈元素个数，则会输出出栈的元素及队中剩余元素； （3）选择e，则退出模拟操作； （4）选择其他，则要求重新选择。 二概要设计 1.定义栈； 2.初始化栈函数； 3.判断栈空函数； 4.判断栈满函数； 5.进栈函数 让元素进栈； 6.出队函数 { if(栈空) return 0; else {return 出栈元素}； } 9.输出队中元素函数 { if(栈1非空) { 将栈1元素全部倒入栈2； 将栈2元素逐个实现出栈，输出，压入栈1操作； } else { 将栈2元素逐个实现出栈，输出，压入栈1操作； } } 8.入队函数

{ if(栈2非空) 将栈2中元素全部压入栈1； 要入队元素压入栈1； else 直接将要入队元素压入栈1； } 9.出队函数 { if(栈2非空) 让栈2栈顶元素出栈并输出； else { if(栈1为空) 则队空； else { 将栈1元素全部压入栈2； 栈2栈顶元素出栈； } } 输出队中元素； } 10.主函数 { 定义两个栈s1,s2； 初始化栈1，栈2； 输入选择； 当不选择结束时 { if(选择入队) { 输入要入队元素个数； 输入要入队元素； 元素入队并输出； } if(选择出队) { 选择出队元素个数； 元素出队并输出； 判断队空； } 输入选择； } } 三详细设计 1.数据类型：选择元素类型为字符型，队中元素均为整型； 2. 定义栈