初阶数据结构：栈与队列

1. 简述：栈

1. 栈为一种特殊的线性表，它只允许在指定的一端进行数据的插入和删除操作。被指定进行插入和删除操作的一端被称为栈顶，另一端，被称为栈底，其遵循着数据的先进后出原则。
2. 压栈：栈插入数据的操作被称为进栈，压栈等
3. 出栈：栈的删除操作被称为出栈。

2. 栈的功能分析与实现

2.1 功能分析

1. 栈的创建与初始化：stackinit
2. 栈的插入与删除操作：stackpush，stackpop
3. 获取栈顶元素与检测栈中的有效元素个数：stacktop，stacksize
4. 栈的判空与销毁：stackempty，stackdestroy

2.2 栈的实现

2.2.1 栈的结构创建与初始化

静态栈与动态栈：

1. 静态栈：在定义初始化就指定了栈的大小，容量不可根据所需动态增长
2. 动态栈：会根据存储数据的增多不断扩大自身的容量

注：动态栈更具有学习与应用意义，以下内容都默认为动态栈

栈的结构：

补充：栈的数据结构只对逻辑上有要求，必须满足元素的先进后出与栈顶，栈底的逻辑结构。因此，具体实现时使用数组或链表都可，数组的结构方便实现与适合栈。（数组栈）

//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;

栈的扩容与初始化：

//扩容
void CheckCapacity(Stack* ps)
{if (ps->_capacity == ps->_top){int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* data = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));if (data == NULL){perror("realloc failed");exit(-1);}ps->_a = data;ps->_capacity = newcapacity;}
}//初始化
void StackInit(Stack* ps)
{ps->_capacity = 0;ps->_top = 0;ps->_a = NULL;CheckCapacity(ps);
}

2.2.2 压栈，出栈与判空：

//压栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);CheckCapacity(ps);ps->_a[ps->_top] = data;ps->_top++;
}//判空
int StackEmpty(Stack* ps)
{assert(ps);return ps->_top == 0;
}//出栈
void StackPop(Stack* ps)
{assert(!StackEmpty(ps));ps->_top--;
}

2.2.3 获取栈顶元素，检索栈的长度与栈的销毁

//获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->_a[ps->_top - 1];
}//检索栈的长度
int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}//销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->_a);ps->_capacity = ps->_top = 0;
}

3. 简述：队列

队列为一种只允许在一端插入数据，在另一端删除数据的特殊线性表，其遵循着先进先出的原则。进行插入操作的一侧被称为队尾，进行删除操作的一侧被称为队首。

4. 队列的功能分析与实现

4.1 队列的功能分析

1. 队列的结构与初始化：queueinit
2. 队列的插入与删除操作：queuepush，queuepop
3. 获取队尾与队头元素：queuefront，qeueuback
4. 获取队列中有效元素个数：queuesize
5. 队列判空与销毁：queueempty，queuedestroy

4.2 队列的实现

4.2.1 队列的结构与初始化

注：因为队列的删除操作为头删，所以此处采用头删更为方便的链式结构：链表。

队列的结构：

typedef int QDataType;//队列结点
typedef struct QListNode
{struct QListNode* _pNext;QDataType _data;
}QNode;// 队列的结构（队列的头尾）
typedef struct Queue
{QNode* _front;QNode* _rear;
}Queue;

队列的初始化：

void QueueInit(Queue* q)
{assert(q);q->_front = q->_rear = NULL;
}

4.2.2 队列的插入和删除操作

创建新结点与插入操作：

//结点申请
QNode* BuyNewNode2(QDataType data)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->_data = data;newnode->_pNext = NULL;return newnode;
}//插入
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = BuyNewNode2(data);if (q->_front == NULL){q->_front = q->_rear = newnode;}else{q->_rear->_pNext = newnode;q->_rear = q->_rear->_pNext;}
}

判空与删除操作：

//判空
int QueueEmpty(Queue* q)
{assert(q);return q->_front == NULL;
}//删除
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QNode* cur = q->_front->_pNext;free(q->_front);q->_front = cur;if (q->_front == NULL){q->_rear = NULL;}
}

4.2.3 返回队首与队尾元素，计算队列有效元素长度

//返回队头元素
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->_front->_data;
}//返回队尾元素
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->_rear->_data;
}//返回队列有效长度
int QueueSize(Queue* q)
{assert(q);int count = 0;QNode* cur = q->_front;while (cur){cur = cur->_pNext;count++;}return count;
}

4.2.4 队列的销毁

void QueueDestroy(Queue* q)
{assert(q);while (q->_front){QueuePop(q);}
}