数据结构期末复习总结.doc

第1章 绪论
1.数据(Data) ：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。
包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。
2.数据元素(Data Element) ：表示一个事物的一组数据称为一个数据元素（结点顶点、记录）；数据元素是数据的基本单位。
3.数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。
4.数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C ={A,B,C,…} 。
数据(Data) ：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。
包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。
数据元素(Data Element) ：表示一个事物的一组数据称为一个数据元素（结点、顶点、记录）；数据元素是数据的基本单位。
数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C ={A,B,C,…} 。

l 数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示。
l 四种逻辑结构：集合、线性结构、树型结构、图状结构。
l 数据结构的形式定义是一个二元组：
Data-Structure=(D，S)
其中：D是数据元素的有限集，S是D上关系的有限集。
例1：设数据逻辑结构 B=（K，R）
K={k1, k2, …, k9}
R={ <k1, k3>，<k1, k8>，<k2, k3>，<k2, k4>，<k2, k5>，<k3, k9>，<k5, k6>，<k8, k9>，<k9, k7>，<k4, k7>，<k4, k6>

有时候关系图不唯一（一般是无向图）
l 数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。
l 两种不同的存储结构：顺序存储结构和链式存储结构。
l 顺序结构：数据元素存放的地址是连续的；
l 链式结构：数据元素存放的地址是否连续没有要求，用该指针来表示数据元素之间的逻辑结构(关系)。
l 顺序存储—使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序体现它们的逻辑次序。通常使用程序设计语言中的数组来实现。

• 链式存储—使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。数据元素间的逻辑关系通过结点间的链接关系来体现。通常使用指针记载直接前驱元素或直接后继元素的存储地址。

数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作。
• 初始化。
• 判断是否空状态。
• 统计元素的个数。
• 遍历：按某种次序访问所有元素，每个元素只被访问一次。
• 取值：获取指定元素值。
• 置值：设置指定元素值。
• 插入：增加指定元素。
• 删除：移去指定元素。
• 查找：在数据结构中寻找满足给定条件的数据元素。
• 排序：将数据元素
• ...
数据操作定义在数据的逻辑结构上；
数据操作的实现依赖于数据的存储结构。
• 数据结构三方面的关系：
数据的逻辑结构、数据的存储结构及操作这三方面是一个整体
例6：线性表是一种逻辑结构，若采用顺序存储，可称其为顺序表；若采用链式存储，则可称其为链表；若采用散列存储，则可称为散列表。
• 在给定了数据的逻辑结构和存储结构之后，按定义的操作集合及其操作的性质不同，也可能导致完全不同的数据结构。
• 类型（type）是具有相同逻辑意义的一组值的集合。
• 数据类型是指一个类型和定义在这个类型上的操作集合。
数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作
例7： Java中整型类型int的值集是
[-231,…,-2,-1,0,1,2,…,231-1]
这个值集上的操作集合[+,-,*,/,%,=,==,!=,<,<=,>,>=]

l 抽象数据类型(Abstract Data Type ，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。
l ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。
l ADT的形式化定义是三元组：ADT=(D，S，P)
l 其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。
ADT的一般定义形式是：
ADT <抽象数据类型名>{
数据对象： <数据对象的定义>
数据关系： <数据关系的定义>
基本操作： <基本操作的定义>
} ADT <抽象数据类型名>
例8： 复数抽象数据类型描述如下：
ADT plex{
double real,imag;
plex(double real, double imag);
plex add(plex c);
plex sub(plex c);
}
1、算法定义：一个算法（algorithm）是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列（D.Knuth）。
算法的规则必须满足以下5个特性：
① 有穷性： 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
② 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。
③ 可行性： 一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
④ 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
⑤ 输出： 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
2、算法设计目标
– 正确性
– 健壮性
– 高时间效率
– 高空间效率
– 可读性
3、算法描述
l 自然语言描述
l 伪码描述
l 传统流程图描述
l 程序设计语言描述（本课程选Java）
4、算法与数据结构
• 算法建立在数据结构之上，对数据的操作需用算法来描述。
• 算法设计依赖数据的逻辑结构，算法实现依赖数据的存储结构。
• 实现一种抽象数据类型，需要选择合适的存储结构。
求解同一问题可能有许多不同的算法，如何去评价这些算法的优劣？主要考虑如下三点：
A. 执行算法所耗费的时间；
B. 执行算法所耗费的存储空间，其中主要考虑辅助存储空间；
C. 算法应易于理解，易于编码，易于调试等等。
1、时间代价分析

算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率,用大O表示法来记:

T(n)=O(f(n))
例1 void fun(){
++x;
s=0 ;
}
将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 。
如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。
一个简单语句的时间复杂度为Ｏ(1)。
例2 for(i=1; i<=n; ++i){
++x;
s+=x ;
}
语句频度为：2n，其时间复杂度为：Ｏ(n) ，即为线性阶。
一个循环的时间复杂度为Ｏ(n)。
例3 for(i=1; i<=n; ++i){
　　　　 for(j=1; j<=n; ++j){
++ x;
s += x;
}
}
语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。
定理：若A(n)=a m n m + a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)
例4 两个n阶方阵的乘法
for(i=1，i<=n; ++i){
for(j=1; j<=n; ++j){
c[i][j]=0 ;
for(k=1; k<=n; ++k){
c[i][j]+=a[i][k]*b[k][j] ;
}
}
}
由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3　时间复杂度为T(n)=Ｏ(n3)
例5 for(i=2;i<=n;++i){
for(j=2;j<=i-1;++j){
++x;
a[i,j]=x;
}
}
语句频度为： 1+2+3+…+n-2
=(1+n-2) ×(n-2)/2
=(n-1)(n-2)/2 =n2-3n+2
∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。
例6： int n=8, count=0;
for (int i=1; i<=n; i*=2)
for (int j=1; j<=n; j++)
count++;
循环次数为 。时间复杂度为O(nlog2n)。
例7：int n=8, count=0;
for (int i=1; i<=n; i*=2)
for (int j=1; j<=i; j++)
count++;
总的循环次数为 。时间复杂度为O(n)。
以下六种计算算法时间的多项式是最常用的。其关系为：
O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)
指数时间的关系为：
O(2n)<O(n!)<O(nn)
当n取得很大时，指数时间算法运算时间远远超过多项式时间算法。

2、空间代价分析
算法的空间效率（空间复杂度）指算法在执行时为解决问题所需要的额外存储空间，不包括输入数据和程序指令所占用的存储空间,用大O表示法来记:
S(n)=o(f(n))
该存储空间一般包括三个方面：
– 指令常数变量所占用的存储空间;
– 输入数据所占用的存储空间;
– 辅助(存储)空间。
• 一般地，算法的空间复杂度指的是辅助空间。
• 变量i：空间复杂度 O(1)
• 一维数组a[n]： 空间复杂度 O(n)
• 二维数组a[n][m]： 空间复杂度 O(n*m)
第2章 线性表
线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：
i. ① 存在一个唯一的被称为“第一个”的数据元素；
ii. ② 存在一个唯一的被称为“最后一个”的数据元素；
iii. ③ 除第一个元素外，每个元素均有唯一一个直接前驱；
iv. ④ 除最后一个元素外，每个元素均有唯一一个直接后继。
线性表(Linear List) ：是由n(n≧0)个数据元素(结点)a0，a1， …an-1组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。
b) 当n=0时，称为空表。
c) 当n>0时，将非空的线性表记作： (a0，a1，…an-1)
l 线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。
l 用顺序存储实现的线性表称之为顺序表。
l 线性表的逻辑顺序与物理顺序一致。
• 顺序表是一种随机存取结构。通常采用数组存储数据元素。
• 设线性表的每个元素需占用c个存储单元。

public boolean isEmpty(){ //时间复杂度O(1)
return this.len == 0;
}
public int length(){ //时间复杂度O(1)
return this.len;
}
public T get(int i){ //时间复杂度O(1)
if(i>=0 && i < this.len)
return (T)this.element[i];
return null;
}
public void set (int i, T x){ //时间复杂度O(1)
if (x==null)return;
if (i>=0 && i<this.len)
this.element[i] = x;
else throw newIndexOutOfBoundsException(i+“”)；
}
public String toString(){ //时间复杂度O(n)
String str = “(”;
if(this.len>0)
str += this.element[0].toString();
for(int i = 1; i < this.len; i ++)
str +=“，”+ this.element[i].toString();
return str + “)”;
}
}
• 两个线性表相等是指，它们长度相同并且各对应元素相等。
• 链式存储 ：用一组任意的存储单元存储线性表中的数据元素。存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
• 链表中结点的逻辑顺序和物理顺序不一定相同。
• 链表中的结点结构：数据域和地址域
n个结点构成的链表表示为 (a0, a1, ..., an-1)
• 链表中每个结点只含一个地址域，又称为线性链表或单链表。
• 每个结点有两个地址域的线性链表称为双链表。
• 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。

头结点的作用是，使所有链表（包括空表）的头指针非空，则对单链表的插入、删除操作不需要区分操作位置。
头结点中不存储数据。
头插入和头删除操作不会改变head指针
总结----顺序表和链表的比较
（1）直接访问元素的性能
n 顺序表能够直接访问数据元素，即只要给出顺序表底层数组element的下标就可以访问数组中的任何一个数据元素。（随机存取）
n 而链表中不能随机地直接访问大多数元素，只能从链表的第一个结点开始，沿着链的方向，依次查找后续结点，直至到达所需访问的结点。（顺序存取）
（2）存储空间的利用
n 由于需要估计顺序表底层数组element的大小（顺序表的容量），因此顺序表存在存储空间的浪费问题。
n 顺序表在进行插入操作时，要判断顺序表是否为满。如果满，则需要扩充容量。
n 而链表每插入一个结点，就向系统申请一个存储单元，只要系统资源足够，系统就会为该结点分配存储空间。
（3）存储密度
n 存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即：
（结点数据本身所占的存储量）
（整个结点所占的存储总量）
n 顺序表的全部空间都用来存放数据元素，因此存储密度=1；
n 而链表中每个结点都要包含其后继结点或者前驱结点的链，因此存储密度 < 1。
（4）插入和删除操作
n 顺序表的插入、删除操作很不方便，插入和删除操作有时需要移动大量元素；
n 而链表的插入、删除操作很容易进行，只要简单地改动相关结点的链即可，不需要移动数据元素。

第4章 栈和队列
• 栈的定义：
– 栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。通常称允许插入、删除操作的这一端为栈顶(Top)，不允许操作的一端称为栈底(Bottom)。当表中没有元素时称为空栈。
– 假设栈S=(a0，a1，a2，a3，…an-1)，则a0称为栈底元素，an-1为栈顶元素，标识栈顶位置的指针称为栈顶指针。栈中元素按a0， a1，a2，a3，… an-1的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。
• 栈的操作：
– 习惯上将每次删除（也称为退栈）操作又称为出栈或弹出（POP）操作。删除的元素总是当前栈中“最新”的元素（栈顶元素）。
– 每次插入（称为进栈）操作称为入栈或压入（PUSH）操作，入栈的元素总是当前栈中“最新”的元素。
– 在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。
• 栈的数据元素：
– 栈的数据元素和线性表的数据元素完全相同，即栈的数据元素是n（n>=0）个相同类型的数据元素a0，a1，。。。an-1组成的有限序列，记为：{a0,a1,…an-1}。
– 其中，n为数据元素的个数，称为栈的长度。n=0时，为空栈。
• 栈的溢出：
– 当栈满时进栈运算称为“上溢”。
– 当栈空时退栈运算称为“下溢”。
– 栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通常下溢用来作为程序控制转移的条件。
• 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。
• 栈的顺序存储结构简称为顺序栈（Sequential Stack），它是运算受限的线性表。因此，可用数组来实现顺序栈。
• 因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，一般需用一个整型变量top。
栈的顺序存储结构及操作实现
public class SeqStack<T> implements Stack<T> //顺序栈类，实现栈接口
{
Object element[]; //存储栈数据元素的数组
int top; //栈顶元素下标
}
n 注意：element数组存储栈的数据元素；top表示当前栈顶元素的下标。
n 经典实现：
（1）栈的初始化
public SeqStack(int size) //构造容量为size的空栈
{
this.element = new Object[Math.abs(size)];
this.top= -1;
}
public SeqStack() //构造默认容量的空栈
{
this(64);
}
（2）判读栈是否为空
public boolean isEmpty() //判断栈是否空，若空返回true
{
return this.top==-1;
}
• 判读栈是否为满？？？
本实现采用与顺序表同样的处理：当容量不够时，则将数组容量扩充一倍。
（3）入栈
public void push(T x) { //元素x入栈，空对象不能入栈
if (x==null) return; //空对象不能入栈
if (this.top==element.length-1) {//若栈满，则扩充栈容量
Object [] temp = this.element;
//重新申请一个容量更大的数组
this.element = new Object[temp.length*2];
for (int i=0; i<temp.length; i++) //复制数组元素，O(n)
this.element[i] = temp[i];
}
this.top++;
this.element[this.top] = x;
}
（4）出栈
栈不空时，取走top位置处栈顶元素，top减1，下一位置数据元素作为新的栈顶元素
public T pop() //出栈，返回栈顶元素，若栈空返回null
{
return this.top== -1 ? null : (T) this.element[this.top --];
}
（5）获得栈顶数据元素
栈不空时，获取top位置处栈顶元素，此时数据元素未出栈，top值不变
public T get() //取栈顶元素，未出栈，若栈空返回null
{
return this.top==-1 ? null : (T)this.element[this.top];
}
//顺序栈类，最终类，实现栈接口，T表示元素类型
public final class SeqStack<T> implements Stack<T>
{
private SeqList<T> list; //顺序表
public SeqStack(int capacity) //构造栈
public SeqStack() //构造空栈
public boolean isEmpty() //判空
public void push(T x) //x入栈
public T peek() //返回栈顶（未出栈）
public T pop() //出栈，返回栈顶元素
}
• 栈的链式存储，称为链栈。
• 链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的简单化（因为它只是对链表的头部操作）。
• 可用单链表实现链栈。
• 它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点（head），因为其中惟一的已知条件是栈顶指针top，它是指向链式栈的第一个结点（相当于头指针）。
• 栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是栈的各种运算只能在栈的一端操作，栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除（栈顶）
• 而线性表除此之外（不限定一端插入删除），还需要考虑另外一端结点以及中间的结点的插入、删除、查询等操作，理解时，我们可以把栈的入出栈运算当作线性表的一端进行插入删除的特例即可。
链式栈实现（经典实现）
• 栈的链式存储结构及操作实现
public class LinkedStack<T> implements Stack<T>
{
private Node<T> top;
}
（1）栈的初始化
public LinkedStack() //构造空栈
{
this.top=null;
}
（2）判读栈是否为空
public boolean isEmpty()
//判断栈是否空，若空返回true
{
return this.top==null;
}
（3）入栈
public void push(T x)
//元素x入栈，空对象不能入栈
{
if (x!=null)
this.top = new Node(x, this.top);
//头插入，x结点作为新的栈顶结点
}
（4）出栈
public T pop() //出栈，返回栈顶元素，若栈空返回null
{
if (this.top==null)
return null;
T temp = this.top.data; //取栈顶结点元素
this.top = this.top.next; //删除栈顶结点
return temp;
}
（5）获得栈顶元素
public T get()
//取栈顶元素，未出栈，若栈空返回null
{
return this.top==null ? null : this.top.data;
}
链式栈实现（基于单链表）
//链式栈类，最终类，实现栈接口，T表示数据元素的数据类型
public final class LinkedStack<T> implements Stack<T>
{
private SinglyList<T> list;
//使用单链表（第2章）存储栈元素
public LinkedStack() //构造空栈
{
this.list = new SinglyList<T>(); //构造空单链表
}
public boolean isEmpty() //判断栈是否空，若空返回true
{
return this.list.isEmpty();
}
public void push(T x) //元素x入栈，空对象不能入栈
{
this.list.insert(0, x); //单链表头插入元素x
}

public T peek() //返回栈顶元素（未出栈）；若栈空返回null
{
return this.list.get(0);
}
public T pop() //出栈，返回栈顶元素；若栈空返回null
{
return this.list.remove(0);
//若栈不空，单链表头删除，返回删除元素
}

public String toString()
//返回栈所有元素的描述字符串，形式为“(,)”
{
return this.getClass().getName()+" "+this.list.toString();
}
}
顺序栈和链式栈的比较
• 实现链式栈和顺序栈的操作，都是需要常数时间，即时间复杂度为O（1）。主要两者从空间和时间两个方面考虑：
– 初始时，顺序栈必须说明一个固定的长度，当栈不够满时，造成一些空间的浪费，而链式栈的长度可变则是长度不需要预先设定，相对比较节省空间，但是在每个结点中，设置了一个指针域，从而产生了结构开销。
– 当需要多个栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个栈，使每个栈从各自的端点向中间延伸，这样浪费的空间就会减少。但这种情况只有当两个栈的空间需求有相反的需求时，这种方法才有效。也就是说，最好一个栈增长，一个栈缩短。反之，如果两个栈同时增长，则可能比较容易造成栈的溢出。如果多个顺序栈共享空间，则可能需要大量的数据移动，造成时间的开销增大。而链式栈由于存储的不连续性，一般不存在栈满的问题，所以一般不需要栈的共享。
• 【例 3】 使用栈计算算术表达式值
算术表达式有三种表示方法：
⑴<操作数> <操作符> <操作数>，如A+B，称为中缀(infix)表示；
⑵<操作符> <操作数> <操作数>，如+AB称为前缀(prefix)表示；
⑶<操作数> <操作数> <操作符>，如AB+，称为后缀(postfix)表示。
中缀表达式：1+2*(3-4)+5 其对应的后缀表达式为 1234-*+5+
习题 中缀表达式如下， 写出后缀表达式。
A+B*(C-D*(E+F)/G+H)-(I+J)*K
【习题解答】ABCDEF+*G/-H+*+IJ+K*
• 队列的定义：
– 队列(Queue)也是一种运算受限的特殊线性表。其插入和删除操作分别在线性表的两端进行（只允许在表的一端进行插入，而在另一端进行删除）。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。
– 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的，例如：排队购物。
– 先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。
队列的操作：
– 一般情况下，入队(enqueue)操作又称为队列的插入。
– 出队(dequeue)操作又称为队列的删除。　
队列的数据元素：
– 队列的数据元素和线性表的数据元素完全相同，即队列的数据元素是n（n>=0）个相同类型的数据元素a0，a1，。。。an-1组成的有限序列，记为：{a0,a1,…an-1}。
– 其中，n为数据元素的个数，称为队列的长度。n=0时，为空队列 。
– 队列的溢出：
– 队列在顺序存储时，经常出现“假溢出”现象，解决“假溢出”现象的方法有很多种，但通常采用循环队列方式存储。
– 使用顺序表，出队效率低。因此不使用顺序表作为队列的成员变量。

顺序循环队列：
• 现在解决“假溢出”比较好的解决方案是使用循环向量，存储在循环向量中的队列称为循环队列（Circular Quene）。
• 将顺序队列设计成在逻辑上首尾相接的循环结构，则可循环使用顺序队列的连续存储单元。
• 循环队列的操作：
• 假设数组的空间是m，只要在入、出队列时，将队首和队尾的指针对m做求模运算即可实现队首和队为指针的循环，即队首和队尾指针的取值范围是 0 到 m-1 之间。
l 队空：front = rear
l 队满：front = (rear + 1) % maxSize或另外设一个标志以区别队空、队满
l 入队: rear = (rear + 1) % maxSize
l 出队: front = (front + 1) % maxSize;
l 求队长: (rear - front + maxSize)%maxSize
链式队列的基本概念：
– 定义链队列的存储结构基本和线性表的定义相同，它是对链表实现的简单化。
– 队列的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是队列的各种运算只能在队列的两端操作。
• 队列是特殊的线性表，我们只要考虑对线性表的两端操作的情况，并且只能一端插入（队首），另一端删除（队尾）。
• 而线性表除此之外（不限定一端插入、一端删除），还需要考虑中间的结点的插入、删除、查询等操作。
• 理解时，我们可以把队列的入、出队运算当作线性表两端进行插入删除的特例即可。
• 于是，一个链队列由头指针和尾指针唯一确定。
• 使用单链表，入队效率低。
• 单链表设计，增加尾指针。
• 以不带头结点的单链表实现链式队列。
• 队列的应用
– （一）合并两个队列
• 假设有两个队列，要求将两个队列合并到一起，合并时交替使用两个队列中的元素，并把剩余的队列中的元素添加在最后，将产生的新队列返回。
– （二）模拟客户服务系统
– （三）主机与外部设备之间速度不匹配的问题
• 以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。
第5章 数组和广义表
• 数组是数据结构的基本结构形式，它是一种顺序式的结构，数组是存储同一类型数据的数据结构。
• 数组是顺序存储的随机存取结构，数组是其他数据结构实现顺序存储的基础。
• 使用数组时需要定义数组的大小和存储数据的数据类型。
• 数组分为一维数组和多维数组。数组的维数是由数组下标的个数确定的：
• 一个下标称为一维数组
• 一个下标以上的数组称为多维数组
• 从这个意义上讲，确定了对于数组的一个下标总有一个相应的数值与之对应的关系；或者说数组是有限个同类型数据元素组成的序列
• 数组是二元组<下标，值>的一个集合。
• 一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作。
• 声明的格式一般是：
<数据类型> <变量名称> [ ]= new <数据类型> [<数组大小>]；
如：int element[] = new int[5];
} 一维数组的存储
– 一维数组的数据存储按照顺序存储，