数据结构域算法设计DS第三章 栈和队列

第3章 栈和队列,3.1 考纲要求和分析 考纲要求（1）栈和队列的基本概念。 （2）栈和队列的顺序存储结构。 （3）栈和队列的链式存储结构。 （4）栈和队列的应用。,第3章 栈和队列,3.1 考纲要求和分析 考纲分析 本章是必考内容，出题形式主要以选择题为主。本章要求： （1）理解栈和队列的定义及其操作特性，掌握栈和队列对插入和删除的操作定义。 （2）对于栈和队列的存储结构，掌握顺序栈、链栈、共享栈、顺序队列、循环队列、链队列的存储方法，以及栈空、栈满、队空、队满的判定条件。 （3）掌握栈和队列的插入、删除、判空等基本操作的算法描述和时间性能。 （4）理解栈和队列的应用，例如，子程序调用、表达式求值、括号匹配等。,第3章 栈和队列,3.1 考纲要求和分析 考纲分析 对于栈，常考的一类题是考查栈的后进先出特性，例如给定一个入栈序列，判断某个出栈序列的合法性（或不合法性），共享栈也是一个常考点。对于队列，循环队列是一个常考点，注意队空、队满的判定条件、队列长度的计算。,第3章 栈和队列,3.1 考纲要求和分析 考纲分析 本章有一个难点是关于栈的证明题，主要采用反证法应用栈的操作特性来完成；有一个结合点是将栈、队列、链表和数组相结合，主要考查是否掌握栈和队列的操作特性，以及链表和数组的存储特点；有一个复杂的应用是递归，主要考查是否理解栈在递归调用过程中的作用，以及应用栈实现递归函数到非递归函数的转换。,第3章 栈和队列,3.1 考纲要求和分析 考纲分析 由于栈和队列的算法比较简单，通常不会单独以算法设计题的形式出题；在树和图的算法设计中，栈和队列通常作为辅助数据结构，因此，需要熟练掌握栈和队列的基本操作语句。,第3章 栈和队列,3.2 栈 考核知识点 1. 栈的定义() 操作受限的线性表、栈顶、栈底、空栈； 2. 栈的操作特性() 后进先出,第3章 栈和队列,3.2 栈 考核知识点 3. 栈的基本操作()栈初始化：StackInit()判栈空：StackEmpty(S)，栈为空返回1，否则为0入栈：Push(S，x)出栈：Pop(S)读栈顶元素：StackGetTop(S)销毁栈：StackDestroy (S) 清空栈： StackClear (S) 求栈长：StackLength(S),第3章 栈和队列,3.2 栈 考核知识点 4. 顺序栈及其实现() 1). 顺序栈的存储结构定义 利用一组地址连续的存储单元依次自栈底到栈顶存放栈的数据元素. 在数组上实现时，栈底位置可以设置在数组的任一个端点（通常是下标为0的一端），而栈顶是随着插入和删除而变化的，可以用一个整形变量top存放栈顶的指针，数据入栈或出栈时使整形变量 top分别加，或减1。,顺序栈的C表示,#define StackSize 1024 typedef structElemType dataStackSize; int top;SeqStack；,第3章 栈和队列,3.2 栈 考核知识点 4. 顺序栈及其实现() 2). 顺序栈基本操作的实现 顺序栈的基本操作本质上是顺序表基本操作的简化，插入和删除只在操作只在栈顶（即表尾）进行，栈空时栈顶指针top=-1;栈满时栈顶指针top=StackSize-1。入栈时，栈顶指针top加1；出栈时栈顶指针top减1。 顺序栈基本操作的算法都很简单，时间复杂度均为O(1)。,第3章 栈和队列,3.2 栈 考核知识点 5. 两栈共享空间() 1). 两栈共享空间的存储结构定义,两栈共享空间的存储结构的C表示,#define StackSize 100 typedef structElemType dataStackSize; int top1,top2;BothStack；,第3章 栈和队列,3.2 栈 考核知识点 5. 两栈共享空间() 2). 两栈共享空间上基本操作的实现设i表示整型数值，它只取1和2两个值，当i=1时，表示对栈1操作，当i=2时表示对栈2操作。当top1=-1时栈1为空；当top2=StackSize时栈2为空。当top1=top2-1时（或top2=top1+1时）栈为满。另外，当新元素压入栈2时，栈顶指针top2不是加1而是减1；当从栈2删除元素时，top2不是减1而是加1。,两栈共享空间入栈算法Push,void Push(BothStack S, int i, ElemType x)if (S.top1=S.top2-1) printf(“上溢“); exit(0); else if(i=1) S.data+S.top1=x;if(i=2) S.data-S.top2=x; ,两栈共享空间出栈算法Pop,ElemType Pop(BothStack S, int iif (i=1) /将栈1的栈顶元素出栈if(S.top1=-1) printf(“下溢“); exit(0); else return S.dataS.top1- ;/ifif (i=2) /将栈2的栈顶元素出栈if(S.top2=MaxSize) printf(“下溢“); exit(0); else return S.dataS.top2+ ;/if ,说明：对于两栈共享空间，只有当两个栈的空间需求有相反的关系时，两栈共享空间才会奏效，也就是说，最好一个栈增长时另外一个栈缩短。,第3章 栈和队列,3.2 栈 考核知识点 6. 链栈及其实现() 1). 链栈的存储结构定义 通常链栈用单链表表示。 【说明】：链栈不附设头结点 2). 链栈上基本操作的实现 链栈的插入和删除操作只需处理栈顶即第一个位置的情况。 链栈上基本操作的算法都很简单，时间复杂度均为O(1)。,栈典型题解析,1. 选择题 主要考查栈的基本操作（初始化、进栈、出栈、判空等）在不同存储结构（顺序栈和链栈）下的执行过程，对于顺序栈注意栈底的位置和栈顶指针的变化，对于栈链注意如何用链表实现栈以及插入和删除操作的位置。 栈最重要的考点是元素以同样顺序进栈后判断出栈的不同情况，两栈共享空间也是一个常见的考点，注意存储方法、栈底的位置和栈顶指针的变化。,选择题（1）：经过以下栈运算后，x的值是（ ）。 IniStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x); A. a B. b C. 1 D. 0 【解答】A 【分析】本题要求熟悉栈的基本操作，理解所给运算的含义。 IniStack(s)表示对栈s进行初始化；Push(s,a)表示将元素a压入栈s中； Pop(s,x) 表示将栈s的栈顶元素弹出并送入变量x中；GetTop(s,x)表示取栈顶元素并送入变量x中但不删除该元素。,选择题（2）：经过以下栈运算后，StackEmpty(s)的值是（ ）。 IniStack(s);Push(s,a);Push(s,b);Pop(s,x); Pop(s,y); A. a B. b C. 1 D. 0 【解答】C 【分析】注意IniStack(s)的返回值，如果栈s为空，则返回1，否则返回0.,选择题（3）： （ ）不是栈的基本运算。 A. 删除栈顶元素 B. 删除栈底元素 C. 判断栈是否为空 D. 将栈置为空栈 【解答】B 【分析】因为栈的操作满足后进先出，通常不能删除栈底元素。,选择题（4）：设有一个空栈，栈顶指针为1000H（十六进制，下同），每个元素需要1个单位的存储空间，则执行PUSH,PUSH,POP,PUSH,POP, PUSH,POP,PUSH操作后，栈顶指针的值是（ ）。 A. 1002H B. 1003H C. 1004H D. 1005H 【解答】A 【分析】栈顶指针的位置只与执行的操作有关，而与插入或删除的元素无关。执行PUSH操作后栈顶指针的值加1，执行POP操作后栈顶指针减1。,选择题（5）一个栈的入栈序列是（1,2,3,4,5）,则栈的不可能的输出序列是（ ）。 A. 5,4,3,2,1 B. 4,5,3,2,1 C. 4,3,5,1,2 D. 1,2,3,4,5 【解答】C 【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。,选择题（6）：若一个栈的输入序列是1,2,3,n，输出序列的第一个元素是n,则第i个输出元素是（ ）。 A. 不确定 B. n-i C. n-i-1 D. n-i+1 【解答】D 【分析】此时，输出序列一定是输入序列的逆序。,选择题（7）：若一个栈的输入序列是1,2,3,n，其输出序列是p1,p2, , pn ，若p1=3，则p2的值（ ）。 A. 一定是2 B. 一定是1 C. 不可能是1 D. 以上都不对 【解答】C 【分析】 由于p1=3，说明1,2,3均入栈后3出栈，此时可能将当前栈顶元素2出栈，也可以继续执行入栈操作，因此p2的值可能是2，但一定不能是1，因为1不是栈顶元素。,选择题（8）：若一个栈的输入序列是p1,p2, , pn ，其输出序列是1,2,3,n，若p3=1，则p1的值（ ）。 A. 可能是2 B. 一定是2 C. 不可能是2 D. 不可能是3 【解答】C 【分析】 由于p3=1，则入栈序列是p1,p2, , pn ，第一个出栈的元素是p3，即p1,p2, p3入栈后执行出栈操作，第二个出栈的元素是2，而此时p1不是栈顶元素，因此p1的值不可能是2。,选择题（9）：当字符序列t3_依次通过栈，输出长度为3且可用作C语言标识符的序列有（ ）。 A. 4个 B. 5个 C. 3个 D. 6个 【解答】C 【分析】 输出长度为3说明将字符序列全部出栈，可以作为C语言标识符的序列只能以字母t或下划线_开头，而栈的输出序列中以字母t或下划线_开头的有三个，分别是t3_、t_3和_3t。,选择题（10）：在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（ ）。 A. 不变 B. top=0 C. top=top-1 D. top=top+1 【解答】C 【分析】栈底固定在数组的低端，出栈时栈顶指针top需要减1；如果栈底固定在数组的高端，则出栈时栈顶指针top需要加1。,选择题（11）：向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（ ）。 A. h->next=s; B. s->next=h; C. s->next=h; h->next=s; D. s->next=h->next; h->next=s; 【解答】D 【分析】结点s应插在头结点的后面。,选择题（12）：从栈顶指针为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; 【解答】D 【分析】删除链中的第一个结点，即指针top指向的结点。备选答案A保存的是栈顶指针；备选答案B只保存了被删除结点的值，没有执行删除操作；备选答案C保存的是被删除结点的后继结点的值。,