1.栈
1.1 栈的基本概念
- 只允许在一端(栈顶top)进行插入或删除操作的受限的线性表。
- 后进先出（Last In First Out）LIFO。或者说先进后出FILO。
进栈顺序：a1 > a2 > a3 > a4 > a5
出栈顺序：a5 > a4 > a3 > a2 > a1
1.2 栈的基本操作
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。
1.2.1 栈的顺序存储实现
【顺序栈的定义】
#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;
// 初始化栈顶为-1，栈顶指针指向栈顶
void InitStack(SqStack &S){
S.top = -1; //初始化栈顶指针
}
// 判断栈是否为空
bool StackEmpty(SqStack S){
if(S.top == -1)
return true;
else
return false;
}
// 初始化栈顶为0，栈顶指针指向栈顶的下一个空位
void InitStack(SqStack &S){
S.top = 0; //初始化栈顶指针
}
// 判断栈是否为空
bool StackEmpty(SqStack S){
if(S.top == 0)
return true;
else
return false;
}【顺序栈的入栈出栈】
初始化为-1时
// 新元素进栈
bool Push(SqStack &S, ElemType x){
if(S.top == MaxSize - 1) // 判断栈是否已满
return false;
S.data[++S.top] = x;
return true;
}
// 出栈
bool Pop(SqStack &x, ElemType &x){
if(S.top == -1) // 判断栈是否为空
return false;
x = S.data[S.top--];
return true;
}
初始化为0时
// 新元素进栈
bool Push(SqStack &S, ElemType x){
if(S.top == MaxSize) // 判断栈是否已满
return false;
S.data[S.top++] = x;
return true;
}
// 出栈
bool Pop(SqStack &x, ElemType &x){
if(S.top == 0) // 判断栈是否为空
return false;
x = S.data[--S.top];
return true;
}【读取栈顶元素】
// 读栈顶元素
初始化为-1时
bool GetTop(SqStack S, ElemType &x){
if(S.top == -1) 先判空，非空读取才有意义
return false;
x = S.data[S.top];
return true;
}
初始化为-1时
bool GetTop(SqStack S, ElemType &x){
if(S.top == 0)
return false;
x = S.data[S.top-1];
return true;
}【读取栈的长度】
// 获取当前栈长
当初始化为-1
int GetSize(SqStack S){
return S.top + 1;
}
当初始化为0
int GetSize(SqStack S){
return S.top;
}共享栈(两个栈共享同一片空间)】
- 共享栈--特殊的顺序栈
- 将栈底设计在共享空间的两端，栈顶向中间靠拢
#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;
}1.2.2 栈的链式存储
【链栈的定义】
- 定义：采用链式存储的栈称为链栈。
- 优点：链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
- 特点：进栈和出栈都只能在栈顶一端进行(链头作为栈顶)
链表的头部作为栈顶，意味着：
- 1. 在实现数据"入栈"操作时，需要将数据从链表的头部插入；
- 2. 在实现数据"出栈"操作时，需要删除链表头部的首元节点；
因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表;
栈的链式存储结构可描述为：
【链栈的定义】
typedef struct Linknode{
ElemType data; //数据域
Linknode *next; //指针域
}Linknode,*LiStack;
void testStack(){
LiStack L; //声明一个链栈
}【链栈的初始化】
typedef struct Linknode{
ElemType data;
Linknode *next;
}Linknode,*LiStack;
// 初始化栈
bool InitStack(LiStack &L){ // 生成虚拟头节点，并将其next指针置空
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 x){
Linknode *s = (Linknode *)malloc(sizeof(Linknode));
if(s == NULL)
return false;
s->data = x;
// 头插法
s->next = L->next;
L->next = s;
return true;
}
// 出栈
bool popStack(LiStack &L, int &x){
// 栈空不能出栈
if(L->next == NULL)
return false;
Linknode *s = L->next;
x = s->data;
L->next = s->next;
free(s);
s = NULL;
return true;
}2. 队列
2.1 队列的基本概念
- 只允许在表的一端(队尾)插入，表的另一端(队头)进行删除操作的受限的线性表。
- 特点：先进先出（先入队的元素先出队）、FIFO（First In First Out）,后入后出LILO。
2.2 队列的基本操作
InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Qx)：入队，若队列Q未满，则将x加入使之成为新的队尾。
DeQueue(&Q&x)：出队，若队列Q非空，则删除队头元素，并用x返回。
GetHead(Q&x)：读队头元素，若队列Q非空则用x返回队头元素。
ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。
【队列的顺序存储实现 】
队头指针：指向队头元素
队尾指针：指向队尾元素或者队尾的下一个位置
【顺序队列的定义】
#define MaxSize 10; //定义队列中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //用静态数组存放队列元素
int front, rear; //队头指针和队尾指针
}SqQueue;
void test{
SqQueue Q; //声明一个队列
}【顺序队列的初始化】
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
// 初始化时，队头、队尾指针指向0
// 队尾指针指向的是即将插入数据的数组下标
// 队头指针指向的是队头元素的数组下标
Q.rear = Q.front = 0;
}
// 判断队列是否为空
bool QueueEmpty(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;
}- 循环队列不能直接使用Q.rear == Q.front作为判空的条件，因为当队列已满时也符合该条件，会与判空发生冲突！
解决方法一：牺牲一个单元来区分队空和队满，即将(Q.rear+1)%MaxSize == Q.front作为判断队列是否已满的条件。（主流方法）
解决方法二：设置 size 变量记录队列长度。
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
int size;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
Q.rear = Q.front = 0;
Q.size = 0;
}
// 判断队列是否为空
bool QueueEmpty(SqQueue 0){
if(Q.size == 0)
return true;
else
return false;
}
// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){
if(Q.size == MaxSize)
return false;
Q.size++;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.size == 0)
return false;
Q.size--;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
return true;
}解决方法三：设置 tag 变量记录队列最近的操作。（tag=0：最近进行的是删除操作；tag=1 ：最近进行的是插入操作）
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
int tag;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
Q.rear = Q.front = 0;
Q.tag = 0;
}
// 判断队列是否为空，只有tag==0即初始化或者出队后才可能为空
bool QueueEmpty(SqQueue 0){
if(Q.front == Q.rear && Q.tag == 0)
return true;
else
return false;
}
// 新元素入队 判断队列是否满，只有tag==1即入队后才可能满
bool EnQueue(SqQueue &Q, ElemType x){
if(Q.rear == Q.front && tag == 1)
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
Q.tag = 1;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.rear == Q.front && tag == 0)
return false;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
Q.tag = 0;
return true;
}【获得队头元素】
// 获取队头元素并存入x
bool GetHead(SqQueue &Q, ElemType &x){
if(Q.rear == Q.front)
return false;
x = Q.data[Q.front];
return true;
}队列的链式存储实现
【链队列的定义】
// 链式队列结点
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}
// 链式队列
typedef struct{
// 头指针和尾指针
LinkNode *front, *rear;
}LinkQueue;【 链队列的初始化（带头结点）】
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue &Q){
// 初始化时，front、rear都指向头结点
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
Q.front -> next = NULL;
}
// 判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front == Q.rear)
return true;
else
return false;
}【入队出队（带头结点）】
// 新元素入队
void EnQueue(LinkQueue &Q, ElemType x){ // 不存在满的情况
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
}
// 队头元素出队
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;
// 如果p是最后一个结点，此时Q.rear已经要被删除了，则将队尾指针也指向队首指针
if(Q.rear == p)
Q.rear = Q.front;
free(p);
p = NULL;
return true;
}【不带头结点的链队列操作】
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue &Q){
// 不带头结点的链队列初始化，头指针和尾指针都指向NULL
Q.front = NULL;
Q.rear = NULL;
}
// 判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front == NULL)
return true;
else
return false;
}
// 新元素入队
void EnQueue(LinkQueue &Q, ElemType x){
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
// 第一个元素入队时需要特别处理
if(Q.front == NULL){
Q.front = s;
Q.rear = s;
}else{
Q.rear->next = s;
Q.rear = s;
}
}
//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
if(Q.front == NULL)
return false;
LinkNode *s = Q.front;
x = s->data;
if(Q.front == Q.rear){
Q.front = Q.rear = NULL;
}else{
Q.front = Q.front->next;
}
free(s);
return true;
}双端队列
双端队列定义
- 双端队列是允许从两端插入、两端删除的线性表。
- 如果只使用其中一端的插入、删除操作，则等同于栈。
- 输入受限的双端队列：允许一端插入，两端删除的线性表。
- 输出受限的双端队列：允许两端插入，一端删除的线性表。
双端队列考点：判断输出序列的合法化
- 例：数据元素输入序列为 1，2，3，4，判断 4! = 24 个输出序列的合法性
输入受限的双端队列：只有 4213 和 4231 不合法
输出受限的双端队列：只有 4132 和 4231 不合法
