三、栈、队列和数组
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; //指针先加1S.data[S.top]=x; //新元素入栈 把x存到top指针所在的位置return true;
}S.top = S.top+1; //指针先加1S.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; //指针再减1top指针减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保存数据元素es->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;
}
