【数据结构】栈和队列（vs）
前言：
栈和队列是两种重要的线性结构。本章讨论栈和队列的定义、表示方法。这里栈和队列分别用数组实现和链表实现（这里所说是实现的底层逻辑分别是数组结构和链表结构）
一、栈
1.1概念与结构
栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作，进行数据插入和删除的一端称为栈顶和栈底。（可得出，栈是先进后出LIFO）
压栈：栈的插入操作，入数据在栈顶
出栈：栈的删除操作，出数据也在栈顶
1.2用数组的结构实现栈（vs）：
头文件：stack.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDatatype;
typedef struct Stack
{STDatatype* arr;int top;//元素个数int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);//判空
bool STEmpty(ST*ps);//入栈&出栈
void STPush(ST* ps, STDatatype x);
void STpop(ST* ps);//取栈顶元素
STDatatype StackTop(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);
实现栈的基本功能：初始化栈、入栈和出栈、获取栈的元素、销毁栈等：
- 初始化：创建一个空栈，设置栈顶指针为初始化状态。
void STInit(ST* ps)
{assert(ps);ps-> arr = NULL;ps->top = ps->capacity = 0;
}
- 栈的销毁：将栈顶指针恢复到初始状态，释放栈中所有元素占用的空间。
void STDestroy(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = ps->capacity = 0;
}
- 入栈和出栈：
void STPush(ST* ps, STDatatype x)
{assert(ps);//看空间是否足够，不够就申请if (ps->capacity == ps->top){int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;STDatatype* tmp = (STDatatype*)realloc(ps->arr, sizeof(STDatatype) * newCapacity);if (tmp == NULL){perror("reallloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;}
//这里是判空操作
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));--ps->top;
}- 获取栈顶的元素：可在不删除栈顶元素的情况下，返回栈顶元素的值。获取元素个数，直接取ps->top。
//获取栈顶元素
STDatatype StackTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}
//获取元素个数
int STSize(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->top;
}
二、队列
2.1概念与结构
概念：只允许在一端进行插入数据操作，在另一端进行删除操作的特殊线性表，具有先进先出特点。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
队列的底层结构
2.2用链表结构实现队列（vs）：
头文件：Queue.h
//定义队列节点的结构.
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{struct QueueNode* phead;struct QueueNode* ptail;int size;//保存队列有效数据个数..
}Queue;//初始化.
void QueueInit(Queue* pq);//入队列，从队尾
void QueuePush(Queue* pq, QDataType x);//队列判空.
bool QueueEmpty(Queue* pq);//出队列，从队头
void QueuePop(Queue* pq);//取对头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);
实现队列的基本操作：初始化、出入队列操作、获取队列的长度、销毁队列。
- 初始化队列，创建一个空的队列、设置队头指针和队尾指针为初始状态。
//初始化.
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
- 入队列：将元素插到队尾，若队列为空，则将插入的数据作为初始的队头队尾指针元素，若不为空，则将队尾指针更新指向新插入的元素。
//入队列，队尾.
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//申请一个新节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}- 出队列：首先先判空，若队列为空，无法进行出队操作，通常会返回一个特定的错误值或进行错误处理；若队列中只有一个元素，删除该元素后，队头指针和队尾指针都恢复到初始状态；若有多个元素，删除队头元素后，队头指针指向下一个指针。
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}//出队列，队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;
}
- 取队头队尾数据：首先判空，若队列为空，则不再执行下面的代码。
//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾元素
QDataType QUeueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
- 获取队列有效元素个数：这里用的是链表结构实现队列，所以直接取元素个数就可以了。
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
- 销毁队列：将队头队尾指针恢复到初始状态，释放队列中所有元素占用的内存。
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
