栈
栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据的插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的元素遵循后进先出的原则。
压栈:栈的插入操作叫做进栈/入栈/压栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈,出数据也在栈顶。
栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些,因为数组在尾上插入数据的代价比较小。
结构如下:
typedef int STDataType;//栈中存储的元素类型（这里用整型举例） typedef struct Stack { STDataType* a;//栈 int top;//栈顶 int capacity;//容量，方便增容 }Stack;
栈的初始化
首先，我们需要用结构体创建一个栈，这个结构体需要包括栈的基本内容（栈，栈顶，栈的容量）。
//初始化栈 void StackInit(Stack* pst) { assert(pst); pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素 pst->top = 0;//初始时栈中无元素，栈顶为0 pst->capacity = 4;//容量为4 }
销毁栈
因为栈的内存空间是动态开辟出来的，当我们使用完后必须释放其内存空间，避免内存泄漏。
//销毁栈 void StackDestroy(Stack* pst) { assert(pst); free(pst->a);//释放栈 pst->a = NULL;//及时置空 pst->top = 0;//栈顶置0 pst->capacity = 0;//容量置0 }
入栈
进行入栈操作前，我们需要检测栈的当前状态，若已满，则需要先对其进行增容，然后才能进行入栈操作。
//入栈 void StackPush(Stack* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity)//栈已满，需扩容 { STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pst->a = tmp; pst->capacity *= 2;//栈容量扩大为原来的两倍 } pst->a[pst->top] = x;//栈顶位置存放元素x pst->top++;//栈顶上移 }
出栈
出栈操作比较简单，即让栈顶的位置向下移动一位即可。但需检测栈是否为空，若为空，则不能进行出栈操作。
//出栈 void StackPop(Stack* pst) { assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 pst->top--;//栈顶下移 }
获取栈顶元素
获取栈顶元素，即获取栈的最上方的元素。若栈为空，则不能获取。
//获取栈顶元素 STDataType StackTop(Stack* pst) { assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 return pst->a[pst->top - 1];//返回栈顶元素 }
检测栈是否为空
检测栈是否为空，即判断栈顶的位置是否是0即可。若栈顶是0，则栈为空。
//检测栈是否为空 bool StackEmpty(Stack* pst) { assert(pst); return pst->top == 0; }
获取栈中有效元素个数
因为top记录的是栈顶，使用top的值便代表栈中有效元素的个数。
//获取栈中有效元素个数 int StackSize(Stack* pst) { assert(pst); return pst->top;//top的值便是栈中有效元素的个数 }
队列
队列的概念和结构
队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO入队列:进行插入操作的一端称为队尾，出队列:进行删除操作的一端称为对头。
队列的结构，我们选取单链表来实现，秩序进行头删和为插的不足即可。如果选数组，那么每一次删头我们都要挪动一遍数据，这种方式不优，所以我们还是选取用单链表来实现。
定义的结构如下
typedef int QDataType;//队列中存储的元素类型（这里用整型举例） typedef struct QListNode { struct QListNode* next;//指针域 QDataType data;//数据域 }QListNode; typedef struct Queue { QListNode* head;//队头 QListNode* tail;//队尾 }Queue;
队列的实现
队列的初始化
//初始化队列 void QueueInit(Queue* pq) { assert(pq); //起始时队列为空 pq->head = NULL; pq->tail = NULL; }
销毁队列
队列中的每一个结点所占用的内存空间都是动态开辟的，当我们使用完队列后需要及时释放队列中的每一个结点。
//销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QListNode* cur = pq->head;//接收队头 //遍历链表，逐个释放结点 while (cur) { QListNode* next = cur->next; free(cur); cur = next; } pq->head = NULL;//队头置空 pq->tail = NULL;//队尾置空 }
入队
入队列，即申请一个新结点并将其链接到队尾，然后改变队尾的指针指向即可。需要注意的是：若队列中原本无数据，那么我们只需让队头和队尾均指向这个新申请的结点即可。
//队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));//申请新结点 if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x;//新结点赋值 newnode->next = NULL;//新结点指针域置空 if (pq->head == NULL)//队列中原本无结点 { pq->head = pq->tail = newnode;//队头、队尾直接指向新结点 } else//队列中原本有结点 { pq->tail->next = newnode;//最后一个结点指向新结点 pq->tail = newnode;//改变队尾指针指向 } }
出队
出队列，即释放队头指针指向的结点并改变队头指针的指向即可。若队列中只有一个结点，那么直接将该结点释放，然后将队头和队尾置空即可。
//队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//检测队列是否为空 if (pq->head->next == NULL)//队列中只有一个结点 { free(pq->head); pq->head = NULL; pq->tail = NULL; } else//队列中有多个结点 { QListNode* next = pq->head->next; free(pq->head); pq->head = next;//改变队头指针指向 } }
获取对头元素
获取队列头部元素，即返回队头指针指向的数据即可。
//获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//检测队列是否为空 return pq->head->data;//返回队头指针指向的数据 }
获取队尾元素
获取队列尾部元素，即返回队尾指针指向的数据即可。
//获取队列尾部元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//检测队列是否为空 return pq->tail->data;//返回队尾指针指向的数据 }
判断队列是否为空
检测队列是否为空，即判断队头指针指向的内容是否为空。
//检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
获取队列中元素个数
队列中有效元素个数，即队列中的结点个数。我们只需遍历队列，统计队列中的结点数并返回即可。
//获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); QListNode* cur = pq->head;//接收队头 int count = 0;//记录结点个数 while (cur)//遍历队列 { count++; cur = cur->next; } return count;//返回队列中的结点数 }
