专升本数据结构笔记 第三章：栈和队列
阿洛学长笔记 love ttz
栈和队列
任务一 栈的定义、存储结构和基本操作 （阿洛学长）
一、栈的定义及其基本操作
二、栈的顺序存储结构
三、栈的链式存储结构
四、栈在递归中的应用
一、栈的定义及其基本操作
1．栈的定义
栈是一种只允许在表的一端进行插入和删除操作的线性表。 （应许表的一端进行插入和删除的线性表）
2．栈的基本操作
二、栈的顺序存储结构
1．顺序栈的结构特点
顺序栈是指采用顺序存储结构的栈，即在内存中用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置一个指针top指示栈顶元素的当前位置。
类型定义如下：
define MAXSIZE 100 //定义栈的最大容量
typedef struct
{
ElemType elem[MAXSIZE]; //存放栈中元素的一维数组空间
int top; //栈顶指针变量
}SeqStack;
top用于指示某一时刻栈顶元素的位置
elem[0]用于存放栈中第一个元素
2．顺序栈的基本操作
（1）初始化
void InitStack (SeqStack *S)
{ //构造一个空栈S
S -> top = 0;
}
（2）判断栈是否为空
int StackEmpty (SeqStack S)
{ //判断S是否为空栈，为空时返回TRUE，否则返回FALSE
return (S.top == 0 ? TRUE : FALSE);
}
（3）进栈
int Push (SeqStack *S, ElemType e)
{ //将数据元素e压入栈顶
if (S -> top == MAXSIZE) return FALSE;//栈已满，进栈失败
S -> elem[S -> top] = e; //将e插入栈顶
S -> top ++; //修改栈顶指针
return TRUE;
}
（4）出栈
int Pop (SeqStack *S, ElemType *e)
{ //若栈不空，将栈顶元素弹出，并用e返回其值
if (S -> top == 0) return FALSE;
else
{
S -> top --; //修改栈顶指针
*e = S -> elem[S -> top]; //保存栈顶元素
return TRUE; }
}
（5）取栈顶元素
int GetTop (SeqStack S, ElemType *e)
{ //若栈不空，则用e返回栈顶元素
if (S.top == 0) return FALSE;
*e = S.elem[S.top - 1]; //保存栈顶元素
return TRUE;
}
3．多栈共享空间
当元素进栈时，两个栈都是从两端向中间伸展。通过两个栈顶指针（top1和top2）的动态变化，使其存储空间相互补充。
栈满的条件是：top1＝top2＋1
栈空的条件是：top1＝0或top2＝M－1
1.两栈共享空间的数据结构定义：
define M 100 //两栈共享的存储空间大小
typedef struct
{
ElemType Stack[M]; //两栈共享的一维数组空间
int top[2]; //两栈的栈顶指针
}DSeqStack;
2.两栈共享空间的一些基本操作：
（1）初始化
void InitStack (DSeqStack *S)
{ //初始化两个空栈
S -> top[0] = 0;
S -> top[1] = M-1;
}
（2）进栈
int Push (DSeqStack *S, ElemType e, int i)
{//将数据元素e压入第i个栈的栈顶
if (S -> top[0] == S -> top[1] + 1) return FALSE;//栈已满，进栈失败
switch (i)
{case 0 : //将e压入第1个栈
S -> Stack[S -> top[0]] = e;
S -> top[0] ++;
break;
case 1 : //将e压入第2个栈
S -> Stack[S -> top[1]] = e;
S -> top[1] --;
break;
default : //参数错误
return FALSE; }
return TRUE; }
（3）出栈
int Pop (DSeqStack *S, ElemType *e, int i)
{//从第i个栈中弹出栈顶元素，并用e返回其值
switch (i)
{case 0 : //从第1个栈弹出
if (S -> top[0] == 0) return FALSE;
*e = S -> Stack[S -> top[0] - 1];
S -> top[0] --;
break;
case 1 : //从第2个栈弹出
if (S -> top[1] == M - 1) return FALSE;
*e = S -> Stack[S -> top[1] + 1];
S -> top[1] ++;
break;
default : //参数错误
return FALSE; }
return TRUE; }
三、栈的链式存储结构
1．链栈的结构特点
链栈是指利用一个单链表结构来实现的栈，即栈中的每一个数据元素用一个结点来表示，同时设置一个指针top指示栈顶元素的当前位置。
链栈的类型定义如下：
typedef struct SNode
{
ElemType data; //数据域
struct SNode *next; //指针域
}SNode;
typedef struct
{
struct SNode *top; //栈顶指针
}LinkStack;
2．链栈的基本操作
（1）初始化
void InitStack (LinkStack *S)
{ //将栈S初始化为空栈
S -> top = NULL; //栈顶指针为空
}
（2）进栈
int Push (LinkStack *S, ElemType e)
{//将数据元素e压入链栈
LinkStack *temp;
temp = (LinkStack) malloc (sizeof (struct Node));//生成新结点
if (temp == NULL) return FALSE; //分配空间失败
temp -> data = e; //为新结点数据域赋值
temp -> next = S -> top; //将新结点插入栈顶
S -> top = temp; //修改栈顶指针
return TRUE;
}
（3）出栈
int Pop (LinkStack *S, ElemType *e)
{ //将栈顶元素弹出，并用e返回其值
LinkStack *temp;
if (S -> top == NULL) return FALSE; //栈为空，出栈失败
temp = S -> top;
S -> top = S -> top-> next; //修改栈顶指针
*e = temp -> data; //保存栈顶元素的值
free (temp); //释放出栈结点
return TRUE;
}
四、栈在递归中的应用
指一个函数在定义自身的同时又直接或间接地调用自身
int fib (int n)
{
A1: if (n == 0) return 0;
A2: else if (n == 1) return 1;
A3: else return fib (n - 1) + fib (n - 2);
A4: }
Fib (3)递归栈的存储空间变化情况：
任务二 队列的定义、存储结构和基本操作 （阿洛学长）
一、队列的定义及其基本操作
二、队列的顺序存储结构
三、队列的链式存储结构
一、队列的定义及其基本操作
1．队列的定义
队列是另一种操作受限的线性表，它只允许在表的一端进行插入操作，而在另一端进行删除操作。
2．队列的基本操作
二、队列的顺序存储结构
1．顺序队列
在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素，同时设置两个指针front和rear分别指示队头元素和队尾元素的位置。
顺序队列的类型定义如下：
define MAXSIZE 100 //队列的最大长度
typedef struct
{
ElemType elem[MAXSIZE];//存放队列中元素的一维数组空间
int front; //头指针
int rear; //尾指针
}SeqQueue;
2．循环队列的结构特点
将队列的存储空间看成一个环状的空间，即将队列的首、尾的位置连接起来形成的结构称为循环队列。
3．循环队列的基本操作
（1）初始化
void InitQueue (SeqQueue *Q)
{ //将 Q初始化为一个空的循环队列
Q -> front = Q -> rear = 0;
}
（2）判断队列是否为空
int QueueEmpty (SeqQueue Q)
{ //判断Q是否为空队列，为空时返回TRUE，否则返回FALSE
if (Q.front == Q.rear) return TRUE;
else return FALSE;
}
（3）进队
int EnQueue (SeqQueue *Q, ElemType e)
{//将数据元素e插入到队列中
if ((Q -> rear + 1) % MAXSIZE == Q -> front)//队列已满，插入失败
return FALSE;
Q -> elem[Q -> rear] = e; //将e插入队尾
Q -> rear = (Q -> rear + 1) % MAXSIZE;//重新设置尾指针
return TRUE;
}
（4）出队
int DeQueue (SeqQueue *Q, ElemType *e)
{ //若队列不空，则删除Q的队头元素，并用e返回其值
if (Q -> front == Q -> rear) //队列空，删除失败
return FALSE;
*e = Q -> elem[Q -> front]; //用e返回队头元素
Q -> front = (Q -> front + 1) % MAXSIZE;//重新设置头指针
return TRUE;
}
（5）取队头元素
int GetFront (SeqQueue Q, ElemType *e)
{ //若队列不空，则用e返回队头元素
if (Q.front == Q.rear)
return FALSE;
*e = Q.elem[Q.front]; //保存队头元素
return TRUE;
}
}
三、队列的链式存储结构
1．链队列的结构特点
采用链表形式表示的队列称为链队列，队列中每一个元素对应链表中的一个结点，并设置两个分别指示队头和队尾的指针。
链队列的类型定义如下：
typedef struct Node
{
ElemType data; //数据域
struct Node *next; //指针域
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front; //队头指针
LinkQueueNode *rear; //队尾指针
}LinkQueue;
2．链队列的基本操作
（1）初始化
void InitQueue (LinkQueue *Q)
{//将 Q初始化为一个空的链队列
Q -> front = (LinkQueueNode *) malloc (sizeof (LinkQueueNode));
//生成头结点
if (Q -> front == NULL) return FALSE;//存储空间分配失败
Q -> rear = Q -> front; //队头指针和队尾指针都指向头结点
Q -> front -> next = NULL;
return TRUE;
}
（2）进队
int EnQueue (LinkQueue *Q, ElemType e)
{//将数据元素e插入到队列中
LinkQueueNode *NewNode;
NewNode = (LinkQueueNode *) malloc (sizeof (LinkQueueNode));
//生成新结点
if (NewNode == NULL) return FALSE;//存储空间分配失败
NewNode -> data = e; //为新结点的数据域赋值
NewNode -> next = NULL;
Q -> rear ->next = NewNode; //将新结点插入队尾
Q -> rear = NewNode; //使队尾指针指向新结点
return TRUE; }
（3）出队
int DeQueue (LinkQueue *Q, ElemType *e)
{ //若队列不空，则删除Q的队头元素，并用e返回其值
LinkQueueNode *p;
if (Q -> front == Q -> rear) //队列空，删除失败
return FALSE;
p = Q -> front -> next; //从队头取出第一个结点
*e = p -> data; //用e返回结点p的值
Q -> front -> next = p -> next; //结点p出队
if (Q -> rear == p)//如果队列中只有一个结点p，则p出队后成为空队列
Q -> rear = Q -> front;
free (p); //释放存储空间
return TRUE; }