第三章 栈和队列【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 不合法