栈

栈的概念

栈也是线性表的一种，但是栈只允许在固定的一端进行插入与删除数据，而进行插入与删除的一端同意称为栈顶，而另一端就称为栈底。简称：后进先出。

压栈（push）：将数据插入栈顶。

出栈（pop）：将栈顶的数据删除。

栈的实现

 栈的存储与删除数据的形式是：后进先出。所以这就很符合顺序表的实现模式，可以快速的找到最后一个元素。如果用单链表的话就需要遍历显得比较复杂，但是将单链表的栈顶与栈底换一下也显得比较容易了。

需要实现的函数

typedef struct stack
{int* arr;//指向动态开辟的空间int top;//指向栈顶数据的下一个空间（表示实际数据个数）int capacity;//开辟空间的容量大小}St;void Inite(St* ps);//初始化
void Push(St* ps,int x);//压栈
void Pop(St* ps);//出栈
void Destroy(St* ps);//释放空间
int Top(St* ps);//返回栈顶元素

void Inite(St* ps)
{ps->arr = NULL;ps->capacity = 0;//容量大小ps->top = 0;//栈中存储元素个数}void Push(St* ps,int x)
{if (ps->capacity == ps->top)//判断容量是否足够{ps->capacity = ps->capacity == 0 ? 3 : 2 * ps->capacity;int* new = (int*)realloc(ps->arr,ps->capacity*sizeof(int));当ps->arr为空时realloc就相当于mallocif (new == NULL){ perror("realloc false:");return;}ps->arr = new;}ps->arr[ps->top] = x;ps->top++;
}void Pop(St* ps)//删除数据要考虑是否存在数据
{assert(ps->top);//ps->top为假就跳出ps->top--;}int Top(St* ps)
{assert(ps->top);//无数据时就跳出return ps->arr[ps->top-1];//top-1是栈顶的元素
}void Destroy(St* ps)
{free(ps->arr);//free的对象是动态开辟的空间ps->capacity = ps->top = 0;ps->arr = NULL;
}

队列

队列的概念

队列同样也是线性表的一种，队列就像食堂打饭一样，前面的打好饭先走，新来的同学站在后面排队。即：只允许在一端进行插入数据，而另一端进行删除数据。

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

队列的实现 

队列是在对头删除数据，队尾插入数据，如果再用线性表来实现的话就会发生挪动数据的现象，效率会降低，所以我们选择更简便的方法，单链表实现队列。但是既然是尾入头删的模式，所以我们为了避免每次插入数据是找尾，所以我们每次插入数据的时候都记录上尾的位置就显得更容易了。

实现前的基本操作

typedef struct QueueNode//每个节点所具备的结构(多个节点)
{int val;struct Node* next;
}QNode;typedef struct Queue//(只有一个)可以避免使用二级指针
{QNode* head;//记录节点头QNode* tail;//记录节点尾int size;//记录节点个数
}Que;

这里创建两个结构体，一个是节点结构体，而我们既然又要记录尾的位置还要保存头的位置，所以我们又可以将这几个数据放在同一个结构体里，这里不仅仅在函数传参时方便了很多，而且不需要用到二级指针，所以我们每次传参时，传队列创建的变量地址就可以了。

函数的实现

void Init(Que* q);// 初始化队列void Push(Que* q, int data);// 队尾入队列void Pop(Que* q);// 队头出队列int GetFront(Que* q);// 获取队列头部元素int GetBack(Que* q);// 获取队列队尾元素int Size(Que* q);// 获取队列中有效元素个数void Destroy(Que* q);// 销毁队列

---

QNode* Malloc(int data)//创建节点
{QNode* new = (QNode*)malloc(sizeof(QNode));if (new == NULL){perror("malloc false");return;}new->val = data;new->next = NULL;
}void Init(Que* q)// 初始化队列
{q->head = NULL;q->size = 0;q->tail = NULL;}
void Push(Que* q, int data)// 队尾入队列
{QNode* new =Malloc(data);assert(new);if (q->head == NULL){q->head = q->tail = new;}else{q->tail->next = new;q->tail = new;//指向最后一个节点}q->size++;//勿忘
}void Pop(Que* q)// 队头出队列
{//删除数据之前一定要判断数据是否为空assert(q->head);QNode* next = q->head->next;if (q->size == 1)//只有一个有效数据时要判断，防止q->tail成为野指针{free(q->head);q->head = q->tail = NULL;}else{free(q->head);q->head = next;}q->size--;//勿忘}int GetFront(Que* q)// 获取队列头部元素
{return q->head->val;
}int GetBack(Que* q)// 获取队列队尾元素
{return q->tail->val;
}int Size(Que* q)// 获取队列中有效元素个数
{return q->size;
}void Destroy(Que* q)// 销毁队列
{QNode* cur = q->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->head = q->tail = NULL;q->size = 0;
}

---