第三章 栈和队列【24王道数据结构笔记】
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){ // 不带头结点的链队列初始化，头指针和尾指针都指向NULLQ.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 不合法