北京考试学院网站首页企业网站优化

一  栈的概念

        栈是一种特殊的线性表，栈内数据遵循先进后出(LIFO)的原则，对于栈，只能在同一侧进行入栈和出栈操作。

入栈操作和出栈操作是在栈的同一侧进行的，如图示：

对于栈这种数据类型，我们可以采用链表或者数组来实现，但是我们一般采取数组的形式进行实现。

 二  栈的实现

1.栈的声明

对于一个用数组形式来实现的栈来说，我们需要声明:

指向栈的有效地址指针，栈顶(栈的有效空间)top,  栈的最大容量capacity

typedef int TypeData;
typedef struct Stack {TypeData* a;int top;      //有效个数int capacity;  //最大空间
}ST;

这里top为什么时栈的有效个数呢？因为我们让top指向了当前数组存在有效数据的最大下标+1的位置，这样top更加直观的表达当前栈内的元素

 2.栈的初始化

在一个栈创建后，需要对栈进行初始化后才能进行使用，对于栈的初始状态：

指向数组首元素地址的指针为NULL

栈初始的最大容量为0

栈顶top的指向为数组为0的下标，也就是当前栈的有效数据个数为0

void STInit(ST* ps)
{	assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}

初始化后栈的图示如下： 

 

3.栈的入栈

        当我们往栈中入数据时，我们不能一昧的往里面入数据，在每次入数据前需要考虑当前栈的容量是否已经满了，如果当前栈的容量已满，我们需要先将栈的最大容量扩充后再进行入栈操作。

在扩充最大容量操作时，我们应当使用realloc函数，因为我们需要保留原本栈中存放的数据

在空栈时入栈，那么第一次扩充的栈的大小是4个数据类型空间（也可以是8个，10个等）

如果栈中本来就有数据，那么当栈满时，新栈的最大容量为旧栈的两倍（或整数倍）

void STPush(ST* ps, TypeData x)
{assert(ps);//检查空间是否足够if (ps->capacity == ps->top) {int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//创建newcapacity个空间ST* tmp = (ST*)realloc(ps->a, sizeof(TypeData) * newcapacity);//如果开辟空间失败if (tmp == NULL) {perror("realloc");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}//空间足够ps->a[ps->top++] = x;
}

 

 

 4.栈的出栈前提

当进行出栈操作时，需要判定栈是否为空，如果栈为空（也就是没有数据），则无法出栈。

        当栈顶为0时，说明当前栈中无数据，返回true，否则返回false 

bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

 

 

5.栈的出栈

在栈的出栈操作前需要判断当前栈中是否存有数据，否则不能进行出栈操作

通过栈顶指针-1即可完成出栈操作

//出栈
void STPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}

 

 

6.取栈顶元素

    取栈顶元素前和出栈操作一样，需要判断当前栈是否为空，否则无法取栈顶元素

    取栈顶元素返回的是top-1位置的数据，并非top位置

TypeData STTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素return ps->a[ps->top - 1];
}

 

 

 

7.获取栈的有效个数

    直接返回top即可，因为top不仅代表了栈顶，还代表了当前栈中的有效个数

//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

8.栈的销毁

栈的销毁和顺序表基本一致：

void STDestroy(ST* ps)
{assert(ps);if (ps->a)free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

 

 9.栈的全码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int TypeData;
typedef struct Stack {TypeData* a;int top;      //有效个数int capacity;  //最大空间
}ST;//初始化
void STInit(ST* ps)
{	assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);if (ps->a)free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//入栈
void STPush(ST* ps, TypeData x)
{assert(ps);//检查空间是否足够if (ps->capacity == ps->top) {int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//创建newcapacity个空间ST* tmp = (ST*)realloc(ps->a, sizeof(TypeData) * newcapacity);//如果开辟空间失败if (tmp == NULL) {perror("realloc");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}//空间足够ps->a[ps->top++] = x;
}//检查是否为空栈
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
void STPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
TypeData STTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素return ps->a[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
int main(){return 0;}

三  队列的概念

队列是一种只允许在一侧入数据操作，另一侧出数据操作的线性表，具有先进先出的的原则

在入数据操作的一端称作队尾，在出数据的一端称作队头

而对于队列的底层，我们可以选择数组或者链表来实现，在这里我们使用链表来实现，因为采用数组来实现是，在出队操作后数组需要相继往前移动一位，这样才能使后面的的数据接着出队，因此采用数组的话在出队操作时效率会比链表低

队列的内部数据用链表来表示：

 

1.队列的声明

在 上面队列的概念中我们了解到，队列的底层由链表来实现，而队列有队头和队尾，因此队列的结构体声明有些许不同，可以理解为队列由两部分组成：链表和队列本身，因此我们需要声明两个结构体：

//队列的在链表的基础上实现，所以结构体有两个，一个是链表结点(头删尾插)
typedef int TypeData;//链表结点结构声明
typedef struct QueueNode {TypeData data;struct QueueNode* next;
}Node;
//队列本身的声明
typedef struct Queue {struct QueueNode* phead;//队头struct QueueNode* ptail;//队尾int size;//记录队列的元素个数，每次入队+1，出队-1
}Queue;

2.队列的初始化

当我们创建一个队列时，队列中是不存在数据的，也就是不存在链表结点，因此我们在初始化时不需要初始化链表结点结构体：

//队列初始化
void QueueInit(Queue* ps) {assert(ps);ps->phead = ps->ptail = NULL;ps->size = 0;
}

初始化时，队尾指针和队头指针应当为空，因为此时队列中还不存在数据（结点）

初始化后图示：

 

3.队列的入队 

在队列的入队操作中，其实是对队列中链表的尾插操作

入队步骤：

1）创建新结点

2）在结点插入时需要判断当前队列是否为空（也就是链表是否为空），如果队列为空，那么新创建的结点就是链表的头结点，此时队尾指针和队头指针都指向头结点

3）如果当前队列不为空，那么直接在原队列上进行尾插，即在链表进行尾插，原链表最后一个结点被尾指针指向，所以原最后一个结点的指针指向新结点，原尾指针更新指向新结点

4）记录队列元素个数的size +1

//队列的入队，尾插
void QueuePush(Queue* ps, TypeData x) {//申请新结点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {perror("malloc");exit(1);}newNode->data = x;newNode->next = NULL;//两种情况，队列为空与不为空if (ps->phead == NULL) {ps->phead = ps->ptail = newNode;}else {//队列不为空ps->ptail->next = newNode;ps->ptail = newNode;}ps->size++;
}

4.队列的出队前提

队列的出队与栈一样，在出队前对队列判断当前队列是否为空，只有队列非空的时候才能进行出队操作

//判断队列是否为空
bool QueueEmpty(Queue* ps) {//头节点为空证明队列为空return ps->phead == NULL;
}

 5.队列的出队

对于队列的出队操作，其实就是链表的头删

       先记录下队头结点的下一个结点Next，再释放队头结点并将队头结点指向队头结点的下一个结点Next,最后再将记录队列元素size成员-1

//队列出队，头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;ps->size--;
}

但是这样子其实考虑的并不完全，如果队列中只有一个结点，队尾指针和队头 指针都指向该结点，那么 Next的指向为NULL，当结点释放后，队头指针指向Next达到了置空的作用，但是队尾指针却没有置空，那么此时队尾指针就成为了野指针，这是不被允许的！

因此我们需要分两种情况进行讨论：队列只有一个结点和队列有多个结点

怎样判断队列是否只有一个结点：当队头指针和队尾指针的指向相同时

//队列出队，头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));//如果队列只有一个结点if (ps->phead == ps->ptail) {free(ps->phead);ps->phead = ps->ptail = NULL;}else {//队列有多个结点Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;}ps->size--;
}

6.取队头元素

    无需多言，队头指针指向的数据就是队头元素，直接返回即可

//取队头元素
TypeData QueueFront(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->phead->data;
}

7.取队尾元素

    无需多言，队尾指针指向的元素就是队尾元素，直接返回即可

//取队尾元素
TypeData QueueBack(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->ptail->data;
}

 8.队列的销毁

利用指针del指向要删除的结点，指针Next记录删除结点的下一个结点，当del为空时证明队列已经销毁，再将队列所有的指针置空，队列有效个数置0

//队列的销毁
void DestoryQueue(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Node* del = ps->phead;while (del) {Queue* Next = del->next;free(del);del = Next;}ps->phead = ps->ptail = del = NULL;ps->size = 0;
}

9.获取队列的有效元素个数

    直接返回结构体成员变量size即可

TypeData QueueNums(Queue* ps) {return ps->size;
}

10.队列的全码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//队列的在链表的基础上实现，所以结构体有两个，一个是链表结点(头删尾插)
typedef int TypeData;//链表结点结构声明
typedef struct QueueNode {TypeData data;struct QueueNode* next;
}Node;typedef struct Queue {struct QueueNode* phead;struct QueueNode* ptail;int size;
}Queue;//队列初始化
void QueueInit(Queue* ps) {assert(ps);ps->phead = ps->ptail = NULL;ps->size = 0;
}//队列的入队，尾插
void QueuePush(Queue* ps, TypeData x) {//申请新结点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {perror("malloc");exit(1);}newNode->data = x;newNode->next = NULL;//两种情况，队列为空与不为空if (ps->phead == NULL) {ps->phead = ps->ptail = newNode;}else {//队列不为空ps->ptail->next = newNode;ps->ptail = newNode;}ps->size++;
}//判断队列是否为空
bool QueueEmpty(Queue* ps) {//头节点为空证明队列为空return ps->phead == NULL;
}//队列出队，头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));//如果队列只有一个结点if (ps->phead == ps->ptail) {free(ps->phead);ps->phead = ps->ptail = NULL;}else {//队列有多个结点Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;}ps->size--;
}//取队头元素
TypeData QueueFront(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->phead->data;
}//取队尾元素
TypeData QueueBack(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->ptail->data;
}//队列的销毁
void DestoryQueue(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Node* del = ps->phead;while (del) {Queue* Next = del->next;free(del);del = Next;}ps->phead = ps->ptail = del = NULL;ps->size = 0;
}TypeData QueueNums(Queue* ps) {return ps->size;
}