03_栈和队列

1 栈
- 1.1 顺序栈
define STACK_INIT_SIZE 150
define STACK_INCREMENT 20
define Status int
define OK 1
define ERROR 0
define ElementType int
- 1.2 链栈
define Status int
define OK 1
define ERROR 0
define ElementType int
- 2 队列
  - 2.1 循环队列
  - 2.2 链队列

栈和队列是基于线性表存储结构而实现的存取结构。

1 栈

栈是一种LIFO结构，后进先出，只能从线性结构的一端对数据进行操作。

1.1 顺序栈

存储结构定义 ```c // 定义初始大小和增量
define STACK_INIT_SIZE 150
define STACK_INCREMENT 20
// 定义返回状态及返回码
define Status int
define OK 1
define ERROR 0
// 定义存储的元素类型
define ElementType int

// 顺序栈的结构定义 typedef struct SqStack { // 存储元素的数组 ElementType* elem; // 栈顶元素的索引（这里称为栈顶指针） int top; // 栈容量 int stackSize; // 每次扩容的大小 int incrementSize; }SqStack;


- 常用操作
   - **初始化** -> 对一个栈类型的结构体变量，分配数据部分存储空间，给定结构维护部分变量的初始值。
```c
/* 01_顺序栈——初始化*/
Status initStack_Sq(SqStack& sS)
{
    sS.elem = (ElementType*)malloc(STACK_INIT_SIZE * sizeof(ElementType));
    if (!sS.elem)
    {
        return ERROR;
    }
    sS.top = -1;
    sS.stackSize = STACK_INIT_SIZE;
    sS.incrementSize = STACK_INCREMENT;
    return OK;
}

  - 栈顶指针**直接指向**当前栈顶的元素。

需要注意的是，栈为空时，栈顶指针top == -1。

获取栈顶元素 -> 获取栈顶元素的值，不出栈。

/* 02_顺序栈——取栈顶元素*/
Status getTop_Sq(SqStack sS, ElementType& e)
{
// 如果栈空，返回错误
if (stackEmpty_Sq(sS))
{
 return ERROR;
}
// 赋值
e = *(sS.elem + sS.top);
return OK;
}

注意栈为空的情况。

扩容

/* 08_顺序栈——扩容*/
Status incrementStack_Sq(SqStack& sS)
{
  ElementType* newElem;
  // 进行扩容操作，当前容量加上增量
  newElem = (ElementType*)realloc(sS.elem, (sS.stackSize + (size_t)sS.incrementSize) * sizeof(ElementType));
  // 扩容失败，返回错误
  if (!sS.elem)
  {
      return ERROR;
  }
  sS.elem = newElem;
  // 扩容不要忘记修改容量
  sS.stackSize += sS.incrementSize;
  return OK;
}

realloc函数第一个参数是待扩容的空间首地址。
扩容完成别忘记栈容量。

入栈

/* 03_顺序栈——入栈*/
Status push_Sq(SqStack& sS, ElementType e)
{
  // 达到栈大小，进行扩容
  if (sS.top + 1 == sS.stackSize)
  {
      // 扩容失败，返回失败
      if (!incrementStack_Sq(sS))
      {
          return ERROR;
      }
  }
  // 压入栈顶
  *(sS.elem + ++sS.top) = e;
  // 成功
  return OK;
}

出栈

/* 04_顺序栈——出栈*/
Status pop_Sq(SqStack& sS, ElementType& e)
{
  // 如果栈为空，返回结果
  if (stackEmpty_Sq(sS))
  {
      return ERROR;
  }
  // 赋值并移动栈顶索引
  e = *(sS.elem + sS.top--);
  return OK;
}

清空栈

/*  07_顺序栈——清空栈*/
Status clearStack_Sq(SqStack& sS)
{
  // 只需要改变栈顶索引，因为对元素的存取都只对栈顶操作，其他位置的值无法读到
  sS.top = -1;
  return OK;
}

只是清空数据，结构还在。

销毁栈

/* 05_顺序栈——销毁*/
Status destroyStack_Sq(SqStack& sS)
{
  // 不存在，则标识已经销毁过了
  if (!sS.elem)
  {
      return ERROR;
  }
  // 删除指针
  delete sS.elem;
  // 结构定义字段置默认值
  sS.top = -1;
  sS.stackSize = 0;
  sS.incrementSize = 0;
  return OK;
}

1.2 链栈

存储结构定义 ```c // 定义返回状态及返回码
define Status int
define OK 1
define ERROR 0
// 定义存储的元素类型
define ElementType int

// 采用单链表的结点定义，由于操作简单，所以不带头结点即可 // 定义指向该单链栈结点的指针类型 typedef SL_Node S_Node, *LS;


   - 和单链表的结点结构一样，数据域 + 指针域。
```c
/* 定义单链表结点*/
typedef struct SL_Node
{
    // 存储的元素
    ElementType data;
    // 指向下一个结点的指针
    SL_Node* next;
}HNode, *SL;

由于栈只能在一端操作数据，结合单链表的特性，链表头指针一段即可以轻松对数据进行增加和删除。
- 常用操作
初始化 -> 不带头结点，只需将头指针赋值为NULL

取栈顶元素 -> 同顺序栈，不出栈。

/* 02_单链栈——取栈顶*/
Status getTop_LS(LS& Ls, ElementType& elem)
{
if (stackEmpty_LS(Ls))
{
   return ERROR;
}
elem = Ls->data;
return OK;
}

入栈

/* 03_单链栈——入栈*/
Status push_LS(LS& Ls, ElementType elem)
{
// 类似于单链表的头插法
// 指针p用于新创建结点
LS p = (LS)malloc(sizeof(S_Node));
// 指针q用来保存
LS q = Ls;
// 创建结点失败，返回
if (!p)
{
   return ERROR;
}
p->data = elem;
// 进行头插
p->next = q;
Ls = p;
return OK;
}

和链表头插法一样，需要用一个指针来保存上一个结点，才能将新结点作为它的前驱。

出栈

/* 04_单链栈——出栈*/
Status pop_LS(LS& Ls, ElementType& elem)
{
// 栈为空，返回错误
if (stackEmpty_LS(Ls))
{
   return ERROR;
}
LS p = Ls;
// 赋值
elem = p->data;
// 指针后移
Ls = Ls->next;
// 销毁出栈结点
delete p;
return OK;
}

出栈，可以顺着出栈元素的next域，找到新的栈顶元素，所以不需要额外指针。

栈长度

/* 05_单链栈——栈长度*/
int stackLength_LS(LS Ls)
{
int length = 0;
// 直接用s做迭代，所以不能取引用类型
while (Ls)
{
   length++;
   Ls = Ls->next;
}
return length;
}

由于没有设置维护结点，这里直接用遍历方式来求长度。

判空

/* 06_单链栈——判空*/
Status stackEmpty_LS(LS Ls)
{
// 为空返回非0，否则返回0
return Ls == NULL ? OK : ERROR;
}

不带头结点，直接判断头指针是否为空

清空

/* 07_单链栈——清空*/
Status clearStack_LS(LS& Ls)
{
// 指针p，保存栈顶元素
LS p;
while (Ls)
{
   // 保存栈顶元素
   p = Ls;
   // 栈顶指针后移
   Ls = Ls->next;
   // 销毁栈顶元素
   delete p;
}
delete Ls;
return OK;
}

与单链表清空一致。

2 队列

队列是一种FIFO结构，先进先出，从线性表的两端对数据进行操作。队头：允许删除的一端；队尾：允许插入的一端。

队列操作从两端操作数据，如果以顺序表的方式实现，那么不可能每次入队和出队都移动元素，这将极大影响性能。
通过队头索引front和队尾索引rear之间即是队列的所有数据，入队和出队时，除了操作数据，只需要修改这两个值，即可维护顺序队列的结构。
顺序队列存在的最大问题是入队过程需要扩容，而出队过程中空出来的小地址空间却无法得到利用。于是，优化后的顺序队列——循环队列产生。

2.1 循环队列

存储结构定义
```
// 循环队列的存储结构
typedef struct CircularQueue
{
  // 存储数据的数组
  ElementType* elem;
  // 队列的当前元素个数
  int count;
  // 队头的索引
  int front;
  // 队尾索引，需要注意rear始终指向队尾元素的下一个位置
  int rear;
  // 队列容量,需要注意【实际容量】是比这个值小1的，为了区别队满和队空的情况
  int queueSize;
  // 循环队列扩容的增量
  int incrementSize;
}CQueue;
```
- 与顺序队列的定义没有不同，只是实现的时候对队首及队尾的处理不同。
- 顺序存储的方式，队列的数据在这个结构的数组elem中。
- 用一个变量count记录当前队列的元素个数，避免遍历方式获取元素个数。
- 队列容量queueSize用于记录当前数组的大小，但实际容量比这个值小1，为了区分队满和队空的情况。
- 队头索引front直接指向队头元素，而队尾索引rear指向的是队尾元素的下一个位置。

常用操作

初始化

/* 01_循环队列——初始化*/
Status initQueue_Cq(CQueue& cQ)
{
// 数据部分的存储空间申请
cQ.elem = (ElementType*)malloc((Queue_INIT_SIZE) * sizeof(ElementType));
// 空间分配失败，返回错误
if (!cQ.elem)
{
   return ERROR;
}
// 初始状态，队首和队尾重合
// 有元素时候，需要注意rear始终指向队尾元素的下一个位置
cQ.front = 0;
cQ.rear = 0;
cQ.count = 0;
// 容量和增量初始化
cQ.queueSize = Queue_INIT_SIZE;
cQ.incrementSize = Queue_INCREMENT;
return OK;
}

初始为空，队首和队尾指针重合。（区分于队满的情况，队尾下一个元素是队首）

获取队首元素

/* 08_循环队列——获取队首元素*/
Status getFront_Cq(CQueue cQ, ElementType& elem)
{
// 如果为空，返回NULL
if (queueEmpty_Cq(cQ))
{
   elem = NULL;
   return ERROR;
}
elem = *(cQ.elem + cQ.front);
return OK;
}

注意队列为空的情况

队列长度

/* 02_循环队列——队列长度*/
int queueLength_Cq(CQueue cQ)
{
int length;
// 1. 方法1，通过front和rear
length = cQ.front > cQ.rear ? cQ.rear - cQ.front + cQ.queueSize : cQ.rear - cQ.front;
// 2. 方法2，直接通过的元素个数计数变量
length = cQ.count;
return length;
}

可通过count变量直接获取；
若通过队首front和队尾rear指针方式来获取的话注意两种情况。
- 若 front > rear，则队列经规了循环，采用了出队列后的小地址空间。
- 若 front < rear，则可以直接求差得出长度。

队空
```
/* 07_循环队列——队空*/
Status queueEmpty_Cq(CQueue cQ)
{
  // 队首指针与队尾指针重合即表示队列为空
  return cQ.front == cQ.rear;
}
```
- 队满
```
/* 06_循环队列——队满*/
Status queueFull_Cq(CQueue cQ)
{
// 判断队满条件是循环【队首元素】和【队尾】中间隔一个，由于rear指向队尾的下一个，所以rear相邻的下一个是front
if ((cQ.rear + 1) % cQ.queueSize == cQ.front)
{
   return OK;
}
else
{
   return ERROR;
}
}
```
- 扩容
  - 如果队列满时候 rear > front，即满队状态没有进行循环。则realloc可以直接使用。
  - 如果队列满时候 rear < front，即满队状态有元素越过 size - 1的索引，从0再存，
    - 那么此时直接使用realloc会导致获取队列元素，队列中会有很多空的位置。
    - 这种情况是需要处理的。
      - a. 先进行realloc重新分配，再进行元素移动。本函数采用该方法实现。
      - b. 创建新数组，依次出队列，入队到新数组，毁原数组。

Status incrementQueue_Cq(CQueue& cQ)
{
    ElementType* newElem;
    newElem = (ElementType*)realloc(cQ.elem, (cQ.queueSize + (size_t)cQ.incrementSize) * sizeof(ElementType));
    // 扩容失败返回错误
    if (!newElem)
    {
        return ERROR;
    }
    cQ.elem = newElem;
    cQ.queueSize += cQ.incrementSize;
    printf("\n扩容后，移动前\n");
    testTraverse(cQ);
  // 当有用到循环，从数组0处再入队时候，需要对元素的位置进行操作，设置rear索引
    if (cQ.rear < cQ.front)
    {
        // 当数组索引 rear 之前元素个数小于等于扩容的大小
        if (cQ.rear <= cQ.incrementSize)
        {
            // 队头的元素移动部分或全部到队尾
          for (int i = 0; i < cQ.rear; i++)
            {
              *(cQ.elem + cQ.queueSize - cQ.incrementSize + i) = *(cQ.elem + i);
            }
            // 设置rear索引
            cQ.rear += cQ.queueSize - cQ.incrementSize;
        }
        else
        {
            for (int i = 0; i < cQ.rear; i++)
            {
                // 前increment个元素全部移到后面
                if (i < cQ.incrementSize)
                {
                    *(cQ.elem + cQ.queueSize - cQ.incrementSize + i) = *(cQ.elem + i);
                }
                // 多出的放队列数组首部
                else
                {
                    *(cQ.elem + i - cQ.incrementSize) = *(cQ.elem + i);
                }
            }
            // 设置rear索引
          cQ.rear -= cQ.incrementSize;
        }
    }
    return OK;
}

  - 注意**queueSize变量**在何时进行的操作，是**扩容前**的容量还是**扩容后**的容量。
  - 扩容**不仅仅是数组的扩容**，难点主要是要**维护循环队列的结构**，当进行入队和出队时，每个元素都是有效的。
     - 当 rear之前的小地址空间中的元素个数 **小于等于扩容容量**，直接将这些元素放到队列的尾部。
     - 当 rear之前的小地址空间元素个数 **大于扩容容量**
        - 将rear之前**等于扩容容量个数**的元素放到尾部
        - 将**剩余小地址空间的元素**按顺序放到头部。

入队列

/* 03_循环队列——入队列*/
Status enqueue_Cq(CQueue& cQ, ElementType elem)
{
// 如果队列满了进行扩容
if (queueFull_Cq(cQ))
{
   // 如果扩容失败，返回
   if (!incrementQueue_Cq(cQ)) {
       return ERROR;
   }
}
// 入队列操作
*(cQ.elem + cQ.rear) = elem;
cQ.rear = (cQ.rear + 1) % cQ.queueSize;
// 别忘记队列长度
cQ.count++;
return OK;
}

队满需要扩容，扩容失败要返回错误。
入队是对队尾rear进行操作，队尾指针后移，但是需注意取模以保证循环。
别忘记维护队列长度变量。

出队列

/* 04_循环队列——出队列*/
Status dequeue_Cq(CQueue& cQ, ElementType& elem)
{
// 如果队列为空，返回失败
if (queueEmpty_Cq(cQ))
{
   elem = NULL;
   return ERROR;
}
// 进行出队列操作
elem = *(cQ.elem + cQ.front);
*(cQ.elem + cQ.front) = NULL;
cQ.front = (cQ.front + 1) % cQ.queueSize;
// 别忘记队列元素个数
cQ.count--;
return OK;
}

注意队空情况。
出队是对队头front操作，也是通过取模运算实现后移。
别忘记队列元素个数

2.2 链队列

存储结构定义 ```c // 引用单链表结点 typedef SL_Node QueueNode, *Queue;

// 定义维护链队列的结构 typedef struct LinkedQueueNode { // 队首结点指针 QueueNode front; // 队尾结点指针 QueueNode rear; // 队列元素个数计数 int count; }*LinkedQueue;


   - 队首结点指针可以指向队首元素（不带头结点），也可以指向头结点
   - count是对元素计数的变量，避免每次获取个数都需要遍历。
- 常用操作
   - 初始化
      - 带头结点
         - 需要创建链队列结点
         - 需要创建头结点并且判断创建的结果
         - front和rear都指向头结点
```c
/* 01_链队列——初始化_带头结点*/
Status initQueue_Lqh(LinkedQueue& linkedQH)
{
    // 分配队列结构维护结点的空间
    linkedQH = (LinkedQueue)malloc(sizeof(LinkedQueueNode));
    // 分配失败返回错误
    if (!linkedQH)
    {
        return ERROR;
    }
    // 创建头结点
    Queue head = (Queue)malloc(sizeof(QueueNode));
    // 创建失败返回错误
    if (!head)
    {
        return ERROR;
    }
    // 将头结点设置到队列维护结点中
    linkedQH->front = head;
    linkedQH->rear = head;
    linkedQH->count = 0;
    return OK;
}

  - 不带头结点
     - 创建链队列结点，判断创建结果
     - front和rear均指向NULL。

/* 02_链队列——初始化_不带头结点*/
Status initQueue_Lq(LinkedQueue& linkedQ)
{
    // 分配队列维护结点空间
    linkedQ = (LinkedQueue)malloc(sizeof(QueueNode));
    if (!linkedQ)
    {
        return ERROR;
    }
    // 无头结点，则两个指向为NULL
    linkedQ->front = NULL;
    linkedQ->rear = NULL;
    linkedQ->count = 0;
    return OK;
}

求队列长度

减少遍历直接用一个变量维护。

/* 03_链队列——队列长度_头结点/不带头结点*/
int queueLength_Lq(LinkedQueue linkedQ)
{
// 由于链队列的统计信息需要遍历，所以将长度等信息记录到队列的维护结点中
return linkedQ->count;
}

判断队列为空

带头结点

/* 04_链队列——队空_带头结点*/
Status queueEmpty_Lqh(LinkedQueue linkedQH)
{
// 同时指向头结点，则为空
return (linkedQH->front == linkedQH->rear) ? OK : ERROR;
}

不带头结点

/* 05_链队列——队空_不带头结点*/
Status queueEmpty_Lq(LinkedQueue linkedQ)
{
// 都为空，则队列为空
return (linkedQ->front == NULL && linkedQ->rear == NULL) ? OK : ERROR;
}

入队列

带头结点 ```c / 06链队列——入队列带头结点/ Status enqueue_Lqh(LinkedQueue& linkedQH, ElementType elem) { // 对rear的修改需要取引用 Queue& rear = linkedQH->rear; // 建立结点 Queue newRear = (Queue)malloc(sizeof(QueueNode)); if (!newRear) { return ERROR; } newRear->data = elem; newRear->next = NULL;

// 设置队尾结点 rear->next = newRear; rear = rear->next; // 别忘记队列元素个数 linkedQH->count++; return OK; }


    - 入队是对rear进行操作，操作的结果要维护到链队列结点， 所以rear取引用。
    - 同**尾插法**
 - 不带头结点
```c
/* 07_链队列——入队列_不带头结点*/
Status enqueue_Lq(LinkedQueue& linkedQ, ElementType elem)
{
// 先建立结点
Queue enQueue = (Queue)malloc(sizeof(QueueNode));
if (!enQueue)
{
   return ERROR;
}
// 不带头结点的链队列，队空的时候队首和队尾都为NULL
if (queueEmpty_Lq(linkedQ))
{
   // 同时指向新入队结点
   linkedQ->front = enQueue;
   linkedQ->rear = enQueue;
}
else
{
   // 先连接队尾，再修改维护结点的队尾指针
   linkedQ->rear->next = enQueue;
   linkedQ->rear = linkedQ->rear->next;
}
// 别忘记队列元素个数
linkedQ->count++;
return OK;
}

- 不带头结点需要判断队列是否为空。
   - 如果为空，则**front和rear指针**同时指向**新入队结点**
   - 否则插入元素只需要维护**rear指针**。

出队列

带头结点

需要判断是否为空
front指针后移

如果出队列前只有一个元素，出队列后队空，队尾指针也需要修改，指向头结点

/* 08_链队列——出队列——带头结点*/
Status dequeue_Lqh(LinkedQueue& linkedQH, ElementType& elem)
{
// 队列为空，报错
if (queueEmpty_Lqh(linkedQH))
{
return ERROR;
}
// 保存待出队列的结点数据
Queue& head = linkedQH->front;
elem = head->next->data;
head->next = head->next->next;
// 如果只有一个元素，则涉及修改队尾指针
if (linkedQH->count == 1)
{
linkedQH->rear = head;
}
// 别忘了队列元素个数
linkedQH->count--;
return OK;
}

不带头结点

同理判断0个元素和1个元素的特殊情况

/* 09_链队列——出队列_不带头结点*/
Status dequeue_Lq(LinkedQueue& linkedQ, ElementType& elem)
{
// 队列为空，报错
if (queueEmpty_Lqh(linkedQ))
{
return ERROR;
}
// 保存待出队列的结点数据
elem = linkedQ->front->data;
// 出队列，front结点后移
linkedQ->front = linkedQ->front->next;
// 如果只有一个元素，则涉及修改队尾指针
if (linkedQ->count == 1)
{
linkedQ->rear = NULL;
}
// 别忘了队列元素个数
linkedQ->count--;
return OK;
}

1 栈

1.1 顺序栈

define STACK_INIT_SIZE 150

define STACK_INCREMENT 20

define Status int

define OK 1

define ERROR 0

define ElementType int