第三章：栈和队列

栈：

定义：仅在表尾进行插入或删除操作的线性表。

表尾==栈顶 表头==栈底

元素进出的特点：先进后出

存储方法：顺序栈 + 链栈

顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。通常,指针top指示栈顶元素在顺序栈的位置（top=0，意味着空栈）。

指针base指示栈底元素在顺序栈的位置。

0 顺序栈的存储结构：

#define MAXSIZE 100 //顺序栈存储空间的初始分配量

Typedef struct

{

Int *base； //栈底指针

Int *top； //栈顶指针

Int stacksize //栈可用的最大容量

}sqstack；

1 顺序栈的初始化：

void InitStack（sqtack &S）

{

S．base = new int [MAXSIZE];

If (S. base == NULL)

{

Exit (OVERFLOW);

}

S.top = S.base; //top初始化为base，空栈

S．stacksize = MAXSIZE；

}

2 入栈

Void push_stack (sqstack &S, int e)

{

If (S.top – S. base == S. stacksize)

{

Return ERROR; // 栈满

}

*(S.top) =e; //元素e压栈，栈顶指针加1

S.top++;

}

3 出栈

Void pop_stack（sqstack &S, int &e）

{

If(S.base==S.top) return ERROR; // 栈空

e = *(--S.top); //注意：top总是指向栈顶元素的上一个位置

}

4 取栈顶元素

Int get_top (sqstack &S)

{

If (S.top! = S. base)

{

Return *(S.top-1);

}

}

链栈：采用链式存储结构的栈，通常用单链表表示，其结点结构与单链表的结点结构相同，由于栈的主要操作时栈顶的插入和删除，故在单链表中，选取以链表头部作为栈顶最为方便，相对于单链表，不需要多加一个头结点。

0 链栈的存储结构

Typedef struct stackNode

{

Int Data;

struct stackNode *Next;

} StackNode, *pStackNode;

1 初始化

注：没有必要设置头结点

Void InitStack (pStackNode &S)

{

//构造一个空栈，栈顶指针置NULL；

S=NULL；

}

2 入栈

注：与顺序栈的入栈操作不同的是，链栈入栈前无需判断栈是否为满，只需要为入栈元素动态分配一个结点空间。

Void push（pstackNode &S, int e）

{

pstackNode p1 = new stackNode;

p1->Data = e;

p1->Next = S; //将新结点插入栈顶

s = p1; //修改栈顶指针为p1

}

3 出栈

Void pop (pstackNode &S, int &e)

{

If(s==NULL) return ERROR;

e=S->Data; //将栈顶元素赋值给e

p1 = S; //p1临时保存栈顶空间，以备释放

S = S->Next; //修改栈顶指针，指向下一个

Delete p1; //释放栈顶元素空间

}

4 取栈顶元素

Int get_top (pstackNode S)

{

If (S! = NULL)

{

Return S->Data;

}

}

栈与递归

递归定义：若在一个函数、过程或数据结构定义的内部又直接出现定义本身，这种情况就称为递归。

1 定义是递归的

比如fibonacci函数

long Fib (long n)

{

if(1 == n || 2 == n)

{ //递归终止条件

return 1;

}

else

{

return Fib(n-1) + Fib(n-2); //递归步骤

}

}

2 数据结构是递归的

比如：遍历输出链表中各个结点的递归算法

Void TraverseList (pNode p1)

{

If(p == NULL) return; //递归终止

else

{

cout << p1->Data << endl;

TraverseList(p1->Next); //继续递归下一个指针

}

}

3 问题的解法是递归的

比如：Hanoi问题

步骤1：用C作为过渡，将A柱上的（n-1）个

盘子移动到B柱上

步骤2：将A柱上的最后一个盘子放在C柱上；

步骤3：用A柱做过渡，将B柱上的（n-1）个

盘子移到C柱上。

图1

将搬动定义为move（A，n, C）,指将编号为n的圆

盘从A移动到C，同时设一个初值为0的变量m

Int m=0;

Void move (char A, int n, char C)

{

m++;

}

Void Hanoi (int n, char A, char B, char C)

{

If (n ==1) move (A,1, C);

else

{

Hanoi(n-1,A,C,B); //将A上编号为1至n-1的圆盘移动到B

Move(A, n, C); //将编号为n的圆盘从A移动到C

Hanoi(n-1,B,A,C); //将B上编号为1到n-1的圆盘移到C

}

}

队列：

定义：只允许在表的一端进行插入，另一端删除元素，是一种先进先出的线性表，在线性表中，允许插入的一端为队尾（rear），允许删除的一端则称为队头（front），与栈的不同之处在于，删除是在表的头部进行。

存储形式 = 顺序表示+链式表示

循环队列：由于最大地址处分配的空间被占用，当再插入新的队尾元素时，会出现溢出现象，此时前面的数据可能全部出队了，出现了一种“假溢出“。使用循环队列可以解决。

注：而为了解决（Q.front==Q.rear）无法判断队列是否满的问题，可以少用一个元素空间，此时队空和队满的条件已经变化

队空：Q. front == Q. rear

队满：（Q.rear+1）% MAXQSIZE ==Q.front

图2

0 队列的顺序存储结构：

#define MAXQSIZE 100

Typedef struct queue

{

Int *base //存储空间的基地址

Int front; //头指针

Int rear; //尾指针

}

1 初始化

Void InitQueue (SqQueue &Q)

{

Q. base = new int [MAXQSIZE];

If (! Q. base) exit (OVERFLOW);

Q.front = Q.rear =0; //头指针和尾指针置为零，队列为空

}

2 求队列长度

Int QueueLength (SqQueue &S)

{

Return (Q. rear-Q. front+MAXQSIZE) % MAXQSIZE;

}

3 循环队列入队

Void In_Queue (SqQueue &Q, int e)

{

If ((Q. rear+1) %MAXQSIZE==Q.front) return ERROR;

Q.base[Q.rear] = e; //新元素插入队尾

Q.rear = (Q.rear+1)%MAXQSIZE; //队尾指针加1

}

4 出队

Void out_queue (SqQueue &Q, Int &e)

{

If (Q. front==Q.rear) return ERROR;

e=Q.base[Q.front]; //e存放队头元素

Q.front = (Q.front+1)%MAXQSIZE; //队头指针加1

}

5 取队头元素

Int get_head (SqQueue Q)

{

If (Q. front! = Q. rear)

{

Return Q. base [Q. front]

}

}

链队—队列的链式表示和实现

使用单链表来表示链队，与线性表的单链表一样，为了操作方便，给链队添加一个头结点。

0 队列的链式存储结构

Typedef struct QNode{

Int Data;

Struct QNode *Next;

} QNode, *pQNode;

Typedef struct {

pQNode front;

pQNode rear;

} LinkQueue;

1 链队的初始化

Void Init_Queue（LinkQueue &Q）

{

Q. front = Q. rear = new QNode;

//生成新结点作为头结点，队头和队尾指向此节点

Q.front->Next = NULL: //头结点指针域置空

}

2 入队

Void in_queue (LinkQueue &Q, int e)

{

pQNode p1 = new QNode; //为入队元素分配结点空间，用p1指向

p1->Data = e; //将新结点数据域置e

p1->Next = NULL; //将新结点插入到队尾

Q. rear->Next = p1;

Q.rear = p1; //修改队尾指针

}

3 出队

Void out_queue(LinkQueue &Q，int &e)

{

If (Q. front == Q. rear) return ERROR;

pQNode p1=Q.front->Next; //p1指向队头元素

e=p1->Data; //e保存队头元素的值

Q. front->Next=p1->Next;

//修改头结点的指针域,使其指向队头下一个元素

If (Q. rear ==p) Q. rear = Q. front;

//最后一个元素被删除，队尾指针指向头结点

Delete p1; //释放原头结点的空间

}

4 取队头元素

Int get_head (LinkQueue Q)

{

If (Q. front! = Q. rear)

Return Q.front->Next->Data; //返回队头元素的值，队头指针不变

}