三、栈、队列和数组
3.1 栈
3.1.1 栈的基本概念
线性表是具有相同数据类型的n（n≥0）个数据元素的有限 序列，其中n为表长，当n = 0时线 性表是一个空表。若用L命名线性表，则其一般表示为 L = (a1, a2, … , ai , ai+1, … , an)
栈（Stack）是只允许在一端进行插入或删除操作的线性表
逻辑结构：与普通线性表相同 数据的运算：插入、删除操作有区别
重要术语：栈顶、栈底、空栈
栈顶：允许插入 和删除的一端 (最后进的即最上面的为栈顶元素)
栈底：不允许插 入和删除的一端(最先进的即最下面的为栈底元素)
空栈：不含任何元素的栈
特点：后进先出(后进栈的元素先出栈) 记为LIFO (Last In First Out)
栈的基本操作
- InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
- DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
- Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
- Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
- GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素
其他常用操作
- StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false
栈的常考题型
进栈顺序为： a à b à c à d à e 有哪些合法的出栈顺序？
3.1.2 栈的顺序存储实现
顺序栈的定义：
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针 用于指向此时栈中的栈顶元素 一般用来记录数组的下标
}SqStack;
void testStack(){
SqStack S; //声明一个顺序栈(分配空间)
}
顺序存储：给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)
初始化操作
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
// 初始化栈
void InitStack(SqStack &S){
S.top = -1; //初始化栈顶指针
}
void testStack(){
SqStack S; //声明一个顺序栈(分配空间)
InitStack(S);
//...后续操作...
}
// 判断栈是否为空
bool StackEmpty(SqStack S){
if(S.top == -1) //栈空
return true;
else //不空
return false;
}
进栈操作
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
// 新元素进栈
bool Push(SqStack &S, ElemType x){ // 判断栈是否已满 满了报错
if(S.top == MaxSize - 1)
return false;
S.top = S.top+1; //指针先加1
S.data[S.top]=x; //新元素入栈 把x存到top指针所在的位置
return true;
}
S.top = S.top+1; //指针先加1
S.data[S.top]=x; //新元素入栈 把x存到top指针所在的位置
上面两句代码等价于
S.data[++S.top]=x; //++top表示，先让top的值加1 再来使用top出栈操作
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
// 出栈
bool Pop(SqStack &x, ElemType &x){ // 判断栈是否为空
if(S.top == -1) //栈空报错
return false;
x = S.data[S.top--];
return true;
}
x = S.data[S.top--];
等价于
x=S.data[S.top]; //栈顶元素先出栈
S.top=S.top-1; //指针再减1
top指针减1 数据还残留在内存中，指示逻辑上被删除了栈顶指针：S.top,初始化时设置S.top=-1;栈顶元素：S.data[S.top]
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶
出栈操作：栈非空时，先取栈顶元素，再将栈顶指针减1
栈空条件：S.top==-1,栈满条件：S.top==MaxSize-1；栈长：S.top+1
读取栈顶元素
// 读栈顶元素
bool GetTop(SqStack S, ElemType &x){
if(S.top == -1) //栈空 报错
return false;
x = S.data[S.top]; //x记录栈顶元素 和出栈操作基本一样，唯一区别是这里top不需要--
return true;
}
仅为读取栈顶元素，并没有出栈操作，因此原栈顶元素依然保留在栈中
共享栈（利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间）：
将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top0; //0号栈栈顶指针
int top1; //1号栈栈顶指针
}ShStack;
// 初始化栈
void InitSqStack(ShStack &S){
S.top0 = -1; //初始化栈顶指针
S.top1 = MaxSize;
}
/*仅当两个栈顶指针相邻(top1-top0=1)时，判断为栈满
0号栈进栈时top0先加1再赋值
1号栈进栈时top1先减1再赋值
出栈时则相反*/栈满的条件：top0 + 1 == top1
共享栈是为了更有效地利用存储空间，两个栈的空间相互调剂，只有在整个存储空间被占满时才发生上溢，其存取数据的时间复杂度为O(1)，所以对存取效率没有什么影响
3.1.3 栈的链式存储实现
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况，通常采用单链表实现，并规定所有操作都是在单链表的表头进行的
链栈的定义 和单链表的定义几乎没差别
typedef struct Linknode{
ElemType data; //数据域
Linknode *next; //指针域
}*LiStack;
void testStack(){
LiStack L; //声明一个链栈
}
采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体的实现会有所不同。
链栈的初始化
typedef struct Linknode{
ElemType data;
Linknode *next;
}*LiStack;
// 初始化栈
bool InitStack(LiStack &L){
L = (Linknode *)malloc(sizeof(Linknode));
if(L == NULL)
return false;
L->next = NULL;
return true;
}
// 判断栈是否为空
bool isEmpty(LiStack &L){
if(L->next == NULL)
return true;
else
return false;
}
入栈出栈
// 新元素入栈
bool pushStack(LiStack &L,ElemType e){
Linknode *s = (Linknode *)malloc(sizeof(Linknode));
if(s == NULL) //内存分配失败
return false;
s->data = e; //用结点s保存数据元素e
s->next = L->next; //头插法
L->next = s; //把s结点连到L后
return true;
}
// 出栈
bool popStack(LiStack &L, int &e){
if(L->next == NULL) // 栈空不能出栈
return false;
Linknode *s = L->next;
x = s->data;
L->next = s->next;
free(s);
return true;
}
