第三章栈、队列、数组

3.1栈

3.1.1栈的基本概念

1.栈的定义

栈（Stack）是只允许在一端进行插入或删除操作的线性表。

栈顶（Top）。线性表允许进行插入删除的那一端。

栈底（Bottom）。固定的不允许删除的那一端。

空栈。不含任何元素的空栈。

栈的操作特性可以概括为后进后出（Last In First Out，LIFO）。

2.栈的基本操作

InitStack(&S):初始化一个空栈s。
StackEmpty(S):判断一个栈是否为空，若栈 s 为空则返回 true, 否则返回 false。
Push(&S,x):进栈，若栈s未满，则将x加入使之成为新栈顶。
Pop(&S,&x):出栈，若栈s非空，则弹出栈顶元素，并用 x 返回。
GetTop(S,&x):读栈顶元素，但不出栈，若栈 s 非空，则用 x 返回栈顶元素。
DestroyStack(&s):销毁栈，并释放栈 s 占用的存储空间(“＆”表示引用调用)。

在解答算法题时，若题干未做出限制，则也可直接使用这些基本的操作函数。

栈的数学性质：当 $n$ 个不同元素进栈时，出栈元素不同排列的个数为== $\frac1{n+1}C_{2n}^{n}$ ==。这个公式称为卡特兰数(Catalan)公式，可采用数学归纳法证明，有兴趣的读者可以参考组合数学教材。

3.1.2栈的顺序存储结构

栈是一种操作受限的线性表，类似于线性表，它也有对应的两种存储方式。

1.顺序栈的实现

采用顺序存储的栈称为顺序栈。它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

#define MaxSize 50//栈中元素的最大个数
typedef struct{
    Elemtype data[MaxSize];//存放栈中元素
    int top;//栈顶指针
}SqStack;

public class SeqStackiml<T> implements SeqStack<T>{
    public static int MAX_SIZE=50;
    private T[] data;
    private int top;

    public SeqStackiml() {
        this(MAX_SIZE);
    }

    public SeqStackiml(int size) {
        MAX_SIZE = size;
        data = (T[]) new Object[MAX_SIZE];
        top = -1;
    }
}

栈顶指针：S.top, 初始时设置 S.top=-1。

栈顶元素：S.data[S.top]。

进栈操作：栈不满时，栈顶指针先加 1,再送值到栈顶。

出栈操作：栈非空时，先取栈顶元素，再将栈顶指针减1。

栈空条件：S.top == -1。

栈满条件：s.top == MaxSize-1。

栈长：s.top+1。

另一种常见的方式是：初始设置栈顶指针 S.top=0;进栈时先将值送到栈顶，栈顶指针再加 1;出栈时，栈顶指针先减 1,再取栈顶元素；栈空条件是 S.top == 0;栈满条件是S.top == MaxSize。

顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。

2.顺序栈的基本操作

栈操作的示意图如图所示，(a)是空栈，(c)是 A、B、C、D、E共 5个元素依次入栈后的结果，(d)是在图 3.2(c)之后 E、D、C 的相继出栈，此时栈中还有 2 个元素，或许最近出栈的元素 C、D、E 仍在原先的单元存储着，但 top 指针已经指向了新的栈顶，元素 C、 D、E已不在栈中。

顺序栈上的基本操作（top定义为-1）：

初始化

void InitStack(SqStack &S){
	S.top=-1;
}

    public SeqStackiml() {
        this(MAX_SIZE);
    }

    public SeqStackiml(int size) {
        MAX_SIZE = size;
        data = (T[]) new Object[MAX_SIZE];
        top = -1;
    }

判栈空

bool StackEmpty(SqStack S){
	if(S.top==-1){
		return true;
	}
	else{
		return false;
	}
}

    @Override
    public boolean isEmpty() {
        return top == -1;
    }

进栈

bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1){
        return false;
    }
    //初始top值定义为-1，所以先加再入栈
    S.data[++S.top]=x;
    return true;
}

    @Override
    public boolean push(T data) {
        if (isFull()){
            return false;
        }else {
            this.data[++top] = data;
            return true;
        }
    }

出栈

bool Pop(SqStack &S,ElemType x){
    if(S.top==-1){
        return false;
    }
    //先出栈，再减
    x=S.data[S.top--];
    return true;
}

    @Override
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        return data[top--];
    }

读栈顶元素

bool GetTop(SqStack S,ElemType &x){
    if(S.top==-1){
        return false;
    }
    x=S.data[S.top];
    return true;
}

    @Override
    public T peek() {
        if (isEmpty()) {
            return null;
        }else {
            return data[top];
        }
    }

3.共享栈

利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈项向共享空间的中间延伸。

两个栈的栈顶指针都指向栈顶元素，top0=-1 时0号栈为空，top1=MaxSize时 1号栈为空；仅当两个栈顶指针相邻(top1-top0=1)时，判断为栈满。当 0号栈进栈时 top0 先加 1再赋值，1号栈进栈时 topl1先减 1 再赋值；出栈时则刚好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为 $O(1)$ ,所以对存取效率没有什么影响。

3.1.3栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead指向栈顶元素。

typedef struct LinkNode{
    ElemType data;
    struct LinkNode* next;
}LiStack;

public class LinkedStackiml <T> implements LinkedStack<T>{
    private Node<T> top;
    public static class Node<T>{
        private T data;
        private Node<T> next;
        Node(T data,Node<T> next){
            this.data=data;
            this.next=next;
        }
    }
    public LinkedStackiml(){
        top=null;
    }

    @Override
    public boolean clear() {
        top=null;
        return true;
    }

    @Override
    public boolean isEmpty() {
        return top == null;
    }

    @Override
    public T peek() {
        if(isEmpty()){
            return null;
        }else {
            return top.data;
        }
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            return null;
        }else {
            T temp=top.data;
            top=top.next;
            return temp;
        }
    }

    @Override
    public void printData() {
        System.out.print("栈中元素为：");
        Node<T> temp=top;
        while (temp!=null){
            System.out.print(temp.data+" ");
            temp=temp.next;
        }
        System.out.println();
    }

    @Override
    public boolean push(T data) {
        top= new Node<>(data, top);
        return true;
    }

    @Override
    public int getLength() {
        int length=0;
        Node<T> temp=top;
        while (temp!=null){
            length++;
            temp=temp.next;
        }
        return length;
    }

}

注意是否要带头结点

3.2队列

3.2.1队列的基本概念

1.队列的定义

队列(Queue)简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。这和我们日常生活中的排队是一致的，最早排队的也是最早离队的，其操作的特性是先进先出(First In First Out, FIFO)。

队头（Front）。允许删除的一端，又称队首。

队尾（Rear）。允许插入的一端。

空队列。不含任何元素的空表。

2.队列常见的基本操作

InitQueue(＆Q):初始化队列，构造一个空队列Q。

QueueEmpty(Q):判队列空，若队列Q为空返回 true,否则返回 false。

EnQueue(&Q,x):入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x):出队，若队列Q非空，删除队头元素，并用 x 返回。

GetHead(Q,&x):读队头元素，若队列Q非空，则将队头元素赋值给 x。

需要注意的是，栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

3.2.2队列的顺序存储结构

1.队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置(不同教材对 front 和 rear 的定义可能不同，例如，可以让 rear指向队尾元素、front 指向队头元素。对于不同的定义，出队入队的操作是不同的)。

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

public class SeqQueueiml<T> implements SeqQueue<T> {
    private T[] data;
    private int head,tail;
    public static int MAX_SIZE=50;
    public SeqQueueiml(){
        data= (T[]) new Object[MAX_SIZE];
        head=tail=0;
    }
    public SeqQueueiml(int size){
        data= (T[]) new Object[size];
        head=tail=0;
    }

    @Override
    public boolean clear() {
        head=tail=0;
        return true;
    }

    @Override
    public int getLength() {
        return tail-head;
    }

    @Override
    public boolean isEmpty() {
        return head==tail;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return data[head];
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        return data[head++];
    }

    @Override
    public void printData() {
        System.out.print("队列中的元素为：");
        int i=head;
        while (i!=tail){
            System.out.print(data[i]+" ");
            i++;
        }
        System.out.println();
    }

    @Override
    public boolean push(T data) {
        if(tail!=MAX_SIZE){
            this.data[tail++]=data;
            return true;
        }else{
            System.out.println("队列已满，无法添加元素");
            return false;
        }

    }
}

初始时：Q.front=Q.rear=0。

进队操作：队不满时，先送值到队尾元素，再将队尾指针加 1。

出队操作：队不空时，先取队头元素值，再将队头指针加 1。

图所示为队列的初始状态，有Q.front == Q.rear == 0成立，该条件可以作为队列判空的条件。不能用Q.rear == MaxSize作为队列满的条件,(d)中，队列中仅有一个元素，但仍满足该条件。这时入队出现“上溢出”,但这种溢出并不是真正的溢出，在data 数组中依然存在可以存放元素的空位置，所以是一种“假溢出”。

2.循环队列

上面指出了顺序队列“假溢出”的问题，这里引出循环队列的概念。将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针 Q.front= MaxSize-1 后，再前进一个位置就自动到0，这可以利用除法取余运算(%)来实现。

特定条件下循环队列队头/队尾指针的初值

初始时：Q.front=Q.rear=0。

队首指针进 1: Q.front=(Q.front+1)%MaxSize。

队尾指针进 1: Q.rear=(Q.rear+1)%MaxSize。

队列长度：(Q.rear+MaxSize-Q.front)%MaxSize。

出队入队时：指针都按顺时针方向进 1(如图 3.7 所示)。

特定条件下循环队列队空队满的判断条件

那么，循环队列队空和队满的判断条件是什么呢？显然，队空的条件是Q.front == Q.rear。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如图 3.7(d1)所示，此时可以看出队满时也有 Q.front == Q.rear。循环队列出入队示意图如图 3.7 所示。为了区分是队空还是队满的情况，有三种处理方式：

牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”,如图 3.7(d2)所示。

队满条件：(Q.rear+1)%MaxSize=Q.front。

队空条件：Q.front == Q.rear。

队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize。
类型中增设 size 数据成员，表示元素个数。删除成功 size 减1，插入成功 size 加 1。队空时 Q.size == 0; 队满时 Q.size == MaxSize,两种情况都有 Q.front == Q.rear。
类型中增设 tag 数据成员，以区分是队满还是队空。删除成功置tag=0,若导致Q.front == Q.rear,则为队空：插入成置tag=1,若导致 Q.front == Q.rear,则为队满。

3.循环队列的操作

初始化

void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;
}

判断空

bool isEmpty(SqQueue Q){
    if(Q.rear==Q.front){
        return true;
    }else{
        return false;
    }
}

入队

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

出队

bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front){
        return false;
    }
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

java实现

public class CircularQueueiml <T> implements CircularQueue<T>{

    public static int MAX_SIZE=50;
    private int head;
    private int tail;
    private T[] data;
    CircularQueueiml(){
        this(MAX_SIZE);
    }
    CircularQueueiml(int size) {
        MAX_SIZE=size;
        data=(T[]) new Object[MAX_SIZE];
        head=tail=0;
        size=0;
    }


    @Override
    public boolean clear() {
        head=tail=0;
        return true;
    }

    @Override
    public int getLength() {
        return (tail-head+MAX_SIZE)%MAX_SIZE;
    }

    @Override
    public boolean isEmpty() {
        return head==tail;
    }

    @Override
    public T peek() {
        if (isEmpty()){
            System.out.println("队列为空");
            return null;
        }
        return data[head];
    }

    @Override
    public T pop() {
        if (tail==head){
            System.out.println("队列为空");
            return null;
        }
        T temp=data[head];
        head=(head+1)%MAX_SIZE;
        return temp;
    }

    @Override
    public void printData() {
        int i=head;
        System.out.print("队列元素为：");
        while (i!=tail){
            System.out.print(data[i]+" ");
            i=(i+1)%MAX_SIZE;
        }
        System.out.println();
    }

    @Override
    public boolean push(T data) {
        if ((tail+1)%MAX_SIZE==head){
            System.out.println("队列已满");
            return false;
        }
        this.data[tail]=data;
        tail=(tail+1)%MAX_SIZE;
        return true;
    }
}

3.2.3队列的链式存储结构

1.队列的链式结构

队列的链式表示称为链队列，他实际上是一个同时有队头指针和队尾指针的单列表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

public class LinkedQueueiml <T> implements LinkedQueue<T>{

    private Node<T> head;
    private Node<T> tail;

    public static class Node<T>{
        T data;
        Node<T> next;
        Node(T data){
            this.data=data;
            next=null;;
        }
        Node(T data, Node<T> node){
            this.data=data;
            next=node;
        }
    }
}

不带头结点时，当Q.front == NULL且Q.rear == NULL时，链式队列为空。

入队时，建立一个新结点，将新结点插入到链表的尾部，并让Q.rear 指向这个新插入的结点(若原队列为空队，则令 Q.front 也指向该结点)。出队时，首先判断队是否为空，若不空，则取出队头元素，将其从链表中摘除，并让 Q.front 指向下一个结点(若该结点为最后一个结点，则置Q.front 和Q.rear 都为 NULL)。

不难看出，不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。

用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满目产生溢出的问题。另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和“溢出”的问题。

2.链式队列的基本操作

初始化

void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=new [LinkNode*];
    Q.front->next=NULL;
}

//带头结点
LinkedQueueiml(){
    head=new Node<>(null);
    tail=head;
}

判队空

bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}

   @Override
    public boolean isEmpty() {
        return head == tail;
    }

入队

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=new [LinkNode*];
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

    @Override
    public boolean push(T data) {
        tail.next=new Node<>(data);
        tail=tail.next;
        return true;
    }

出队

bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear)
        return false;
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return true;
}

    @Override
    public T pop() {
        if(isEmpty()){
            return null;
        }
        Node<T> p=head.next;
        head.next=p.next;
        if(tail==p){
            tail=head;
        }
        return p.data;
    }

3.2.4双端队列

双端队列是允许两端进行插入和删除操作的线性表。

在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。

3.3栈和队列的应用

3.3.1栈在括号匹配中的应用

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序任意即([] ())或[([][])]等均为正确的格式，[(])或([())或(()]均为不正确的格式。

考虑下列括号序列：

\begin{array}{}[&(&[&]&[&]&)&]\\1&2&3&4&5&6&7&8\end{array}

分析如下：

计算机接收第 1 个括号“[”后，期待与之匹配的第 8 个括号“]”出现。
获得了第 2 个括号“(”,此时第 1 个括号“[”暂时放在一边，而急迫期待与之匹配的7个括号“)”出现。
获得了第 3 个括号“[”,此时第 2 个括号“(”暂时放在一边，而急迫期待与之匹配的第4 个括号“]”出现。第 3 个括号的期待得到满足，消解之后，第 2 个括号的期待匹配又成为当前最急迫的任务。
以此类推，可见该处理过程与栈的思想吻合。

算法的思想如下：

初始设置一个空栈，顺序读入括号。
若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的栈中所有未消解的期待的急迫性降了一级。
若是右括号，则或使置于栈顶的最急迫期待得以消解，或是不合法的情况(括号序列不匹配，退出程序)。算法结束时，栈为空，否则括号序列不匹配。

3.3.2栈在表达式求值中的应用

1.算数表达式

中缀表达式(如 3+4)是人们常用的算术表达式，操作符以中缀形式处于操作数的中间。与前缀表达式(如+34)或后缀表达式(如 34+)相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它更符合人们的思维习惯。

与前缀表达式或后缀表达式不同的是，中缀表达式中的括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。后缀表达式的运算符在操作数后面，后缀表达式中考虑了运算符的优先级，没有括号，只有操作数和运算符。

中缀表达式 A+B*(C-D)-E/F 对应的后缀表达式为 ABCD- *+EF/-（加括号法）,将后缀表达式与原表达式对应的表达式树后序遍历序列进行比较，可发现它们有异曲同工之妙。

2.中级表达式转后缀表达式

下面先给出一种由中缀表达式转后缀表达式的==手算方法==。

按照运算符的运算顺序对所有运算单位加括号。
将运算符移至对应括号的后面，相当于按“左操作数右操作数运算符”重新组合。

去除所有括号。

例如，中缀表达式 A+B*(C-D)-E/F 转后缀表达的过程如下(下标表示运算符的运算顺序):

加括号：((A+(B*(C-D)))-(E/F))。
运算符后移：((A(B(CD)-)*)+(EF)/)-。
去除括号后，得到后缀表达式：ABCD-*+EF/-。

中缀表达式转后缀表达式的过程

在计算机中，中缀表达式转后缀表达式时需要借助一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右依次扫描中缀表达式中的每一项，具体转化过程如下：

遇到操作数。直接加入后缀表达式。
遇到界限符。若为“(”,则直接入栈；若为“)”,则依次弹出栈中的运算符，并加入后缀表达式，直到弹出“(”为止。注意，“(”直接删除，不加入后缀表达式。
遇到运算符。若其优先级高于除“(”外的栈顶运算符，则直接入栈。否则，从栈顶开始，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，直到遇到一个优先级低于它的运算符或遇到“(”时为止，之后将当前运算符入栈。

按上述方法扫描所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。例如，中缀表达式 A+B*(C-D)-E/F 转后缀表达式的过程如表所示。

栈的深度分析

所谓栈的深度，是指栈中的元素个数，通常是给出进栈和出栈序列，求最大深度(栈的容量应大于或等于最大深度)。有时会间接给出进栈和出栈序列，例如以中缀表达式和后缀表达式的形式给出进栈和出栈序列。掌握栈的先进后出的特点进行手工模拟是解决这类问题的有效方法。

3.后缀表达式求值

用栈实现表达式求值的分析

通过后缀表示计算表达式值的过程：从左往右依次扫描表达式的每一项，若该项是操作数，则将其压入栈中；若该项是操作符< op >,则从栈中退出两个操作数Y和X，形成运算指令 X< op >Y.并将计算结果压入栈中。当所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。
例如，后缀表达式 ABCD- *+EF/-求值的过程需要 12 步，见表。

3.3.3栈在递归中的应用

递归是一种重要的程序设计方法。简单地说，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。

它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。但在通常情况下，它的效率并不是太高。

以斐波那契数列为例，其定义为

F(n)=\begin{cases}F(n-1)+F(n-2),&n>1\\1,&n=1\\0,&n=0\end{cases}

这就是递归的一个典型例子，用程序实现时如下：

int F(int n){
    if(n==0)
        return 0;
    if(n==1)
        return 1;
    return F(n-1)+F(n-2);
}

必须注意递归模型不能是循环定义的，其必须满足下面的两个条件：

递归表达式（递归体）。
边界条件（递归出口）。

递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。

栈在函数调用中的作用和工作原理

在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出等。而其效率不高的原因是递归调用过程中包含很多重复的计算。下面以n=5为例，列出递归调用执行过程，如图所示。

显然，在递归调用的过程中，F(3)被计算2次，F(2)被计算3次。F(1)被调用5次，E(0) 被调用 3 次。所以，递归的效率低下，但优点是代码简单，容易理解。在第 5 章的树中利用了递归的思想，代码变得十分简单。通常情况下，初学者很难理解递归的调用过程，若读者想具体了解递归是如何实现的，可以参阅编译原理教材中的相关内容。

可以将递归算法转换为非递归算法，通常需要借助栈来实现这种转换。

3.3.4队列在层次遍历中的应用

在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。下面用二叉树(见图3.17) 层次遍历的例子，说明队列的应用。表 3.3 显示了层次遍历二叉树的过程。

该过程的简单描述如下：

根节点入队。
若队空（所有的结点处理完毕），则结束遍历；否则重复3操作。
队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若有右孩子，则将右孩子入队，返回2。

3.3.5队列在计算机系统中的应用

队列在计算机系统中的应用非常广泛，以下仅从两个方面来阐述：第一个方面是解决主机与外部设备之间速度不匹配的问题，第二个方面是解决由多用户引起的资源竞争问题。

缓冲区的逻辑结构

对于第一个方面，仅以主机和打印机之间速度不匹配的问题为例做简要说明。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，因为速度不匹配，若直接把输出的数据送给打印机打印，则显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后冉同主机发出请求。主机接到请求后再问缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。

多队列出队/入队操作的应用

对于第二个方面，CPU(即中央处理器，它包括运算器和控制器)资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要 CPU 各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用 CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把 CPU 分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把 CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU 能够正常运行。

3.4数组和特殊矩阵

矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最小的内存空间来存储同样的一组数据。所以，我们不研究矩阵及其运算等，而把精力放在如何将矩阵更有效地存储在内存中，并能方便地提取矩阵中的元素。

3.4.1数组的定义

数组是由 $n$ ( $n\geqslant1$ )个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在 $n$ 个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素是定长数组的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

3.4.2数组的存储结构

大多数计算机语言都提供了数组数据类型，逻辑意义上的数组可采用计算机语言中的数组数据类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间。

以一维数组 A[0...n-1]为例，其存储结构关系式为

\mathrm{LOC}(a_i)=\mathrm{LOC}(a_0)+i\times L(0\leqslant i<n)

其中， $L$ 是每个数组元素所占的存储单元。

二维数组按行优先存储的下标对应关系

对于多维数组，有两种映射方法：按行优先和按列优先。以二维数组为例，按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。设二维数组的行下标与列下标的范围分别为 $[0,h_1]$ 与 $[0,h_2]$ ,则存储结构关系式为

\mathrm{LOC}(a_{i,j})=\mathrm{LOC}(a_{0,0})+[i\times(h_2+1)+j]\times L

h2+1是一行元素的个数

例如，对于数组 $A_{[2][3]}$ ,它按行优先方式在内存中的存储形式如图所示。

当以列优先方式存储时,得出存储结构关系式为

\mathrm{LOC}(a_{ij})=\mathrm{LOC}(a_{0,0})+[j\times(h_{1}+1)+i]\times L

h1+1是一列元素的个数

例如，对于数组 $A_{[2][3]}$ ,它按列优先方式在内存中的存储形式如图所示。

3.4.3特殊矩阵的压缩存储

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。

特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

1.对称矩阵

对称矩阵压缩存储的下表对应关系

若对一个 $n$ 阶矩阵 $A$ 中的任意一个元素 $a_i$ ,都有 $a_{ij}= a_{j, i}( 1\leqslant i, j\leqslant n)$ ,则称其为对称矩阵。其中的元素可以划分为3 个部分。即上三角区、主对角线和下三角区。

对于 $n$ 阶对称矩阵，上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存放，则会浪费几乎一半的空间，为此将 $n$ 阶对称矩阵 $A$ 存放在一维数组 B[n(n+1)/2]中，即元素 $a_{i,j}$ 存放在 $b_k$ 中。比如只存放下三角部分(含主对角)的元素。

在数组 B中，位于元素 $a_{ij}(i\geqslant j)$ 前面的元素个数刚好满足数组从0开始的下标要求为

第1行：1个元素( $a_{1,1})$ 。

第2行：2个元素( $a_{2,1},a_{2,2})$ 。

......

第 $i-1$ 行 $:i-1$ 个元素 $(a_{i-1,1},a_{i-1,2},\cdots,a_{i-1,i-1})$ 。

第 $i$ 行： $j-1$ 个元素( $a_{i,1},a_{i,2},\cdots,a_{i,j-1})$ 。在i行，从第1个元素到第j个元素共有j个元素，j-1即为i行到第j个元素之前的元素个数。

因此，元素 $a_{i,j}$ 在数组 B 中的下标 $k=1+2+\cdots+(i-1)+j-1=i(i-1)/2+j-1$ (数组下标从 0开始)。因此，元素下标之间的对应关系如下：

$k=\begin{cases}\dfrac{i(i-1)}{2}+j-1,&i\geqslant j(\text{下三角区和主对角线元素})\\\dfrac{j(j-1)}{2}+i-1,&i<j(\text{上三角区元素}a_{i,j}=a_{j,j})\end{cases}$

当数组下标从 1 开始时，可以采用同样的推导方法

==二维数组A[n] [n]和A[0...n-1] [0...n-1]的写法是等价的。若数组写为A[1...n] [1...n], 则说明指定了从下标 1 开始存储元素。二维数组元素写为 a[i] [j],注意数组元素下标 i 和广通常是从 0开始的。矩阵元素通常写为 $a_{i,j}$ 或 $a_{(i)(j)}$ ,注意行号i和列号j是从1开始的。==

2.三角矩阵

下三角矩阵中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次，所以可以将 n 阶下三角矩阵 $A$ 压缩存储在 B[n(n+1)/2+1]中。

元素下标之间的对应关系为

i=\begin{cases}\frac{i(i-1)}{2}+j-1,&i\geqslant j\left(\text{下三角区和主对角线元素}\right)\\\\\frac{n(n+1)}{2},&i<j\left(\text{上三角区元素}\right)\end{cases}

下三角矩阵的压缩存储

若上三角矩阵采用行优先存储

上三角矩阵中，下三角区的所有元素均为同一常量。只需存储主对角线、上三角区上的元素和下三角区的常量一次，可将其压缩存储在 B[n(n+1)/2+1]中。

在数组 B 中，位于元素 $a_{ij}$ ( $i\leqslant j$ )前面的元素个数为

第1行： $n$ 个元素

第 2行 $n- 1$ 个元素

......

第 $i-1$ 行： $n-i+2$ 个元素

第 $i$ 行： $j-i$ 个元素第一行第一个元素前面的元素数量为0，第二行为1，以此类推，第i行为i-1，故j-(i-1)-1=j-i。

因此，元素 $a_{i,j}$ 在数组B中的下标

k=n+(n-1)+\cdots+(n-i+2)+(j-i+1)-1=(i-1)(2n-i+2)/2+(j-i)

因此，元素下标之间的对应关系如下：

k=\begin{cases}\dfrac{(i-1)(2n-i+2)}{2}+(j-i),&\quad i\leqslant j\text{(上三角区和主对角线元素)}\\\dfrac{n(n+1)}{2},&\quad i>j\text{(下三角区元素)}\end{cases}

上三角矩阵在内存中的压缩存储形式如图所示。

3.三对角矩阵

对角矩阵也称带状矩阵。对 $n$ 阶矩阵 $A$ 中的任意一个元素 $a_i$ ,当 $|i-j|>1$ 时，若有 $a_{i,j}=0$ (1 $\leqslant i,j\leqslant n$ ),则称为三对角矩阵，如图所示。在三对角矩阵中，所有非零元素都集中在以主对角线为中心的 3 条对角线的区域，其他区域的元素都为零。

三对角矩阵 $A$ 也可以采用压缩存储，将 3 条对角线上的元素按行优先方式存放在一维数组 B中，且 $a_{1,1}$ 存放于B[0]中，其存储形式如图所示。

三对角矩阵压缩存储的下标对应关系

第1行：2

第2行：3

......

第i-1行：3

第i行：j-i+1，(i!=1)k=2+3+...+j-i+1=3*(i-1)+j-i=2i+j-3。按理说i=1时j-i+1=j是不符合的，应为j-1。但是当i=1时，k=j-1，刚好满足，所以可以把i=1的情况合并到式子k中

由此可以计算矩阵 $A$ 中 3 条对角线上的元素 $a_{i,j}$ (1 $\leqslant i,j\leqslant n,|i-j|\leqslant1$ )在一维数组 B 中存放的下标为 $k=2i+j-3$ 。

反之，若已知三对角矩阵中的某个元素 $a_{i,j}$ 存放在一维数组 B 的第 $k$ 个位置，则有 $i=\lfloor(k+1)/3+1\rfloor$ , $j=k-2i+3$ 。例如，当 $k=0$ 时， $i=\lfloor(0+1)/3+1\rfloor=1,j=0-2\times1+3=1$ ,存放的是 $a_1,1;$ 当 $k=$ 2时， $i=\lfloor(2+1)/3+1\rfloor=2,j=2-2\times2+3=1$ ,存放的是 $a_2,1;$ 当 $k=4$ 时， $i=\lfloor(4+1)/3+1\rfloor=2$ , $j=4-2\times2+3=3$ ,存放的是 $a_{2,3}$ 。

3.4.4稀疏矩阵

矩阵中非零元素的个数 $t$ ,相对矩阵元素的个数 $s$ 来说非常少，即 $s\gg t$ 的矩阵称为稀疏矩阵。例如，一个矩阵的阶为 100×100,该矩阵中只有少于 100 个非零元素。

存储稀疏矩阵需要保存的信息

若采用常规的方法存储稀疏矩阵，则相当浪费存储空间，因此仅存储非零元素。但通常非零元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储它所在的行和列。因此，将非零元素及其相应的行和列构成一个三元组(行标 $i$ ,列标 $j$ ,值 $a_{i,j}$ ),如图所示。然后按照某种规律存储这些三元组线性表。稀疏矩阵压缩存储后便失去了随机存取特性。

适合稀疏矩阵压缩存储的存储结构

稀疏矩阵的三元组表既可以采用数组存储，又可以采用十字链表存储(见 6.2 节)。当存储稀疏矩阵时，不仅要保存三元组表，而且要保存稀疏矩阵的行数、列数和非零元素的个数。

第三章 栈、队列、数组

3.1栈

3.1.1栈的基本概念

1.栈的定义

2.栈的基本操作

3.1.2栈的顺序存储结构

1.顺序栈的实现

2.顺序栈的基本操作

3.共享栈

3.1.3栈的链式存储结构

3.2队列

3.2.1队列的基本概念

1.队列的定义

2.队列常见的基本操作

3.2.2队列的顺序存储结构

1.队列的顺序存储

2.循环队列

3.循环队列的操作

3.2.3队列的链式存储结构

1.队列的链式结构

2.链式队列的基本操作

3.2.4双端队列

3.3栈和队列的应用

3.3.1栈在括号匹配中的应用

3.3.2栈在表达式求值中的应用

1.算数表达式

2.中级表达式转后缀表达式

3.后缀表达式求值

3.3.3栈在递归中的应用

3.3.4队列在层次遍历中的应用

3.3.5队列在计算机系统中的应用

3.4数组和特殊矩阵

3.4.1数组的定义

3.4.2数组的存储结构

3.4.3特殊矩阵的压缩存储

1.对称矩阵

2.三角矩阵

3.三对角矩阵

3.4.4稀疏矩阵

第四章串

第二章线性表

Administrator

第三章栈、队列、数组