栈和队列的顺序存储结构
标签: 数据结构
学习人数: 4561


全屏播放
赞赏支持

栈的顺序存储结构实现

参考代码(使用数组实现)

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
  
#define OK 1  
#define ERROR 0  
#define TRUE 1  
#define FALSE 0  
  
#define MAXSIZE 100  
  
typedef int ElemType;  
typedef int Status;  
  
typedef struct  
{  
    ElemType data[MAXSIZE];  
    int top;  
}sqStack;  
  
//四个基础操作  
Status InitStack(sqStack *s);    //初始化操作,建立一个空栈  
Status ClearStack(sqStack *s);    //将栈清空  
Status StackEmpty(sqStack ...
登录查看完整内容


课后作业

课后习题

 

【2010年真题】某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作,则不可能得到的出队序列是()。 
A.b a c d e         B.d b a c e         C.d b c a e         D.e c b a d

参考答案:C
答案解析:考查受限的双端队列的出队序列。 
A 可由左入,左入,右入,右入,右入得到 B 可由 左入,左入,右入,左入,右入得到。 
D 可由左入,左入,左入,右入,左入得到 所以不可能得到 C。 


【2009年真题】为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()。 
A.栈         B.队列         C.树         D.图

参考答案:B
答案解析:考查栈和队列的特点及应用。 
C 和 D 直接排除,缓冲区的特点需要先进先出,若用栈,则先进入缓冲区的数据则要排队到最后才能打印,不符题意,所以只有队列符合题意。 


【2014年真题】循环队列放在一维数组 A[0…M-1]中,end1 指向队头元素,end2 指向队尾元素的后 一个位置。假设队列两端均可进行入队和出队操作,队列中最多能容纳 M-1 个元素。初始 时为空。下列判断队空和队满的条件中,正确的是() 
A.队空:end1 == end2; 队满:end1 == (end2+1)mod M 
B.队空:end1 == end2; 队满:end2 == (end1+1)mod (M-1) 
C.队空:end2 == (end1+1)mod M; 队满:end1 == (end2+1)mod M 
D.队空:end1 == (end2+1)mod M;队满:end2 == (end1+1)mod (M-1)

参考答案:A
答案解析:end1 指向队头元素,那么可知出队的操作是先从 A[end1]读数,然后 end1 再加 1。 end2 指向队尾元素的后一个位置,那么可知入队操作是先存数到 A[end2],然后 end2 再加 1。若把 A[0]储存第一个元素,当队列初始时,入队操作是先把数据放到 A[0],然后 end2 自增,即可知 end2 初值为 0;而 end1 指向的是队头元素,队头元素的在数组 A 中的下标为 0,所以得知 end1 初值也为 0,可知队空条件为 end1==end2;然后考虑队列满时,因为队列 最多能容纳 M-1 个元素,假设队列存储在下标为 0 到下标为 M-2 的 M-1 个区域,队头为 A[0],队尾为 A[M-2],此时队列满,考虑在这种情况下 end1 和 end2 的状态,end1 指向队 头元素,可知 end1=0,end2 指向队尾元素的后一个位置,可知 end2=M-2+1=M-1,所以可 知队满的条件为 end1==(end2+1)mod M,选 A。 
注意:考虑这类具体问题时,用一些特殊情况判断往往比直接思考问题能更快的得到答案,并可以画出简单的草图以方便解题。


【2019年真题】设栈 S 和队列 Q 的初始状态均为空,元素 a,b,c,d,e,f,g 依次进入栈 S。若每个元素出栈后立即进入队列 Q,且 7 个元素出队的顺序是 b,d,c,f,e,a,g,则栈 S 的容量至少是()。 
A.1         B.2         C.3         D.4 

参考答案:C
答案解析:考查栈的最大递归深度。 
时刻注意栈的特点是先进后出。下面是出入栈的详细过程: 

序号

说明

栈内

栈外

序号

说明

栈内

栈外

1

a 入栈

a

 

8

e入栈

ae

bdc

2

b 入栈

ab

 

9

f 入栈

aef

bdc

3

b 出栈

a

b

10

f 出栈

ae

bdcf

4

c 入栈

ac

b

11

e 出栈

a

bdcfe

5

d 入栈

acd

b

12

a 出栈

 

bdcfea

6

d 出栈

ac

bd

13

g 入栈

g

bdcfea

7

c 出栈

a

bdc

14

g 出栈

 

bdcfeag


登录后发布评论

暂无评论,来抢沙发