产品特色

内容简介

本书汇集国内外众多著名IT企业近几年的数据结构面试笔试真题并予以解析，按知识点类型对常见的数据结构难点和疑点进行了系统归纳和透彻剖析，并提供了一定数量的自测题以便于读者自我检验。

　　全书逻辑清晰、通俗易懂，适合参加IT企业校园招聘和面试笔试环节的同学复习，也适合数据结构和算法设计编程爱好者以及在校学生阅读和提高。

作者简介

李春葆：武汉大学教授，主要研究方向为数据挖掘和算法设计，从事近30年计算机C/C++语言、数据结构和算法设计等课程的第一线本科教学工作，具备丰富的教学经验，曾参于深圳名企的笔试和面试题库建设。出版多本C/C++语言、数据结构、算法设计与分析及数据库开发方面的精品教材和教学辅导书。

李筱驰：

美国俄亥俄州立大学计算机科学专业硕士毕业，曾参加谷歌等名企面试，具备比较丰富的企业笔试和面试经验。目前在西雅图亚马*总部工作。

精彩书摘

·第5章·

栈

* 栈的特点。

* 栈的各种存储方法。

* 栈的基本运算算法设计。

* 栈的应用，例如求表达式值和迷宫问题等。

* 灵活运用栈解决一些较复杂的应用问题。

5.1 栈基本算法设计

5.1.1 要点归纳

1．栈的定义

　　栈是一种特殊的线性表，其元素的逻辑关系是线性关系，其特殊性体现在只能在一端插入和删除元素。栈表现出后进先出的特点。

　　栈的基本运算如下。

* InitStack(&s;)：初始化栈，构造一个空栈s。

* DestroyStack(&s;)：销毁栈，释放栈s占用的存储空间。

* StackEmpty(s)：判断栈是否为空，若栈s为空，返回真，否则返回假。

* Push(&s;,e)：进栈，将元素e插入到栈s中作为栈顶元素。

* Pop(&s;,&e;)：出栈，从栈s中删除栈顶元素，并将其值赋给e。

* GetTop(s,&e;)：取栈顶元素，返回当前的栈顶元素，并将其值赋给e。

　　【例5-1】设n个元素进栈序列是1、2、3、……、n，其输出序列是p1、p2、……、pn，若p1=3，则p2的值为（ ）。

　　A．一定是2 B．一定是1 C．不可能是1 D．以上都不对

　　答：当p1=3时，说明1、2、3先进栈，然后出栈3，此时可以让2出栈，也可能让4进栈后再出栈，也可以让4进栈、5进栈后再出栈，……，从中可以看到，p2可能是2，也可能是4、……、n，但一定不能是1，答案为C。

2．栈的实现

　　与线性表采用顺序表或者链表存储一样，栈可以采用顺序栈或者链栈来实现。

　　如果需要用到两个相同类型的栈，这时若为它们各自开辟一个数组空间，极有可能出现这样的情况：第1个栈已满，再进栈就溢出了，而另一个栈还有很多空闲存储空间。解决这个问题的方法是将两个栈合起来，用一个数组来实现这两个栈，这称为共享栈。

　　在设计共享栈时，由于一个数组（大小为MaxSize）有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，让另一个栈的栈底为数组的末端，即下标为MaxSize-1，这样在两个栈中进栈元素时栈顶向中间伸展。

　　 顺序栈

　　通常，顺序栈类型SqStack的声明如下：

typedef struct

{ T data[MaxSize]; //存放栈中的数据元素

int top; //存放栈顶指针,即栈顶元素在data数组中的下标

} SqStack; //顺序栈类型

　　对于顺序栈s，通常将s.data[0]一端作为栈顶，将s.data[MaxSize-1]一端作为栈底，初始时设置s.top=-1，对应的4个要素如下。

* 栈空的条件：s.top==-1。

* 栈满的条件：s.top==MaxSize-1（data数组的最大下标）。

* 元素e的进栈操作：先将栈顶指针top增1，然后将元素e放在栈顶指针处。

* 出栈操作：先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1。

　　【例5-2】若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进栈的操作正确的是（ ）。

　　A．top++; data[top]=x; B．data[top]=x; top++;

　　C．top--; data[top]=x; D．data[top]=x; top--;

　　答：初始栈顶指针top为n，说明data[n]端作为栈底，在进栈时top应递减，由于存在data[n]的元素，所以在进栈时应先将x放到top处，再将top递减。答案为D。

前言/序言

前 言

　　数据结构求解问题的思路是“数据逻辑结构→存储结构→基本算法实现→应用”，这一思路展示了计算逻辑思维，也就是用计算机求解问题的基本过程。

　　编程的第一步需要理解问题本身，提炼出数据逻辑结构和相关运算；然后实现数据的机内表示，也就是数据的存储结构设计，好的存储结构设计会达到事半功倍的效果；最后在存储结构上实现数据的运算，即算法实现。

　　常用的数据结构有线性表、栈、队列、串、树、二叉树和图等，除了围绕这些数据结构的基本运算算法设计外，还包含查找和排序算法设计。

　　在面试笔试中数据结构的考点主要包含两个方面：一是常用数据结构的基本知识点，包括各种数据结构的逻辑特点、存储方式和运算算法，如一个城市图的存储、在城市图中查找两个城市之间的最短路径等；二是常用数据结构的应用知识点，能够熟练地利用数据结构解决问题，如用栈或者队列求解迷宫问题，用栈求解皇后问题等。

　　很多数据结构都是递归数据结构，递归也是求解问题的基本方法，所以面试者必须具有递归算法设计能力，掌握从递归模型、递归算法执行过程到递归算法设计的一般方法，为二叉树、图等复杂数据结构算法设计打下坚实的基础。

　　本书系统归纳了数据结构常见的知识要点，汇集国内外众多著名IT企业近几年的数据结构面试笔试真题并予以解析，透彻地剖析了难点和疑点，每道面试题给出了难度标识，从一星到五星难度依次递增。

　　在本书的编写过程中参考了众多网站和博客，无法一一列出，在此编者表示衷心感谢。

　　限于编者水平，书中难免存在遗漏，恳请读者批评指正。

编 者

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2018年3月