一、栈

栈是什么

  栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈遵循先进后出原则

栈的实现

  栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

栈的基本操作

栈类型的定义

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;   // 栈顶int capacity;  // 容量 int size;}Stack;

初始化栈

 void StackInit(Stack* ps)
{assert(ps);ps->a=(STDataType*)malloc(sizeof(STDataType)*5); if(NULL==ps->a){assert(0);return;}ps->capacity=5;ps->size=0;
}

检查栈是否为满

void CheckStack(Stack* ps)
{assert(ps);if(ps->capacity==ps->size){//1.申请空间int newcapacity=ps->capacity*2;STDataType *temp=(STDataType*)malloc(sizeof(STDataType)*newcapacity);if(temp==NULL){assert(0);return;}//2.拷贝元素memcpy(temp,ps->a,sizeof(STDataType)*ps->size);//3.释放旧空间free(ps->a);//4.使用新空间 ps->a=temp;ps->capacity=newcapacity;}
}

入栈

 void StackPush(Stack* ps, STDataType data)
{assert(ps);CheckStack(ps);ps->a[ps->size]=data;ps->size++;
}

出栈

 void StackPop(Stack* ps)
{assert(ps);if(!StackEmpty(ps)){ps->size--;}return;
}

获取栈顶元素

 STDataType StackTop(Stack* ps)
{assert(ps);return ps->a[ps->size-1];
}// 获取栈中有效元素个数 int StackSize(Stack* ps)
{assert(ps);return ps->size;
}

检测栈是否为空

 int StackEmpty(Stack* ps)
{assert(ps);return 0==ps->size;
}// 销毁栈 void StackDestroy(Stack* ps)
{assert(ps);if(ps->a){free(ps->a);ps->a=NULL;ps->capacity=0;ps->size=0;}
}

测试函数

void TestStack()
{Stack s;StackInit(&s);StackPush(&s,1);StackPush(&s,2);StackPush(&s,3);StackPush(&s,4);StackPush(&s,5);StackPush(&s,6);StackPush(&s,7);printf("%d\n",StackTop(&s));printf("%d\n",StackSize(&s));StackPop(&s);StackPop(&s);StackPop(&s);printf("%d\n",StackTop(&s));printf("%d\n",StackSize(&s));StackDestroy(&s);
}

完整代码

Stack.h

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;   // 栈顶int capacity;  // 容量 int size;}Stack;
// 初始化栈 void StackInit(Stack* ps); //检查栈是否为慢void CheckStack(Stack* ps);// 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);void TestStack();

Stack.c

#include "Stack.h"#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<string.h>// 初始化栈 void StackInit(Stack* ps)
{assert(ps);ps->a=(STDataType*)malloc(sizeof(STDataType)*5); if(NULL==ps->a){assert(0);return;}ps->capacity=5;ps->size=0;
}// 检查栈是否满void CheckStack(Stack* ps)
{assert(ps);if(ps->capacity==ps->size){//1.申请空间int newcapacity=ps->capacity*2;STDataType *temp=(STDataType*)malloc(sizeof(STDataType)*newcapacity);if(temp==NULL){assert(0);return;}//2.拷贝元素memcpy(temp,ps->a,sizeof(STDataType)*ps->size);//3.释放旧空间free(ps->a);//4.使用新空间 ps->a=temp;ps->capacity=newcapacity;}
}// 入栈 void StackPush(Stack* ps, STDataType data)
{assert(ps);CheckStack(ps);ps->a[ps->size]=data;ps->size++;
}// 出栈 void StackPop(Stack* ps)
{assert(ps);if(!StackEmpty(ps)){ps->size--;}return;
}// 获取栈顶元素 STDataType StackTop(Stack* ps)
{assert(ps);return ps->a[ps->size-1];
}// 获取栈中有效元素个数 int StackSize(Stack* ps)
{assert(ps);return ps->size;
}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps)
{assert(ps);return 0==ps->size;
}// 销毁栈 void StackDestroy(Stack* ps)
{assert(ps);if(ps->a){free(ps->a);ps->a=NULL;ps->capacity=0;ps->size=0;}
}

void TestStack()
{Stack s;StackInit(&s);StackPush(&s,1);StackPush(&s,2);StackPush(&s,3);StackPush(&s,4);StackPush(&s,5);StackPush(&s,6);StackPush(&s,7);printf("%d\n",StackTop(&s));printf("%d\n",StackSize(&s));StackPop(&s);StackPop(&s);StackPop(&s);printf("%d\n",StackTop(&s));printf("%d\n",StackSize(&s));StackDestroy(&s);
}

main.c

#include "Stack.h"int main()
{TestStack();return 0;
}

二、队列

队列是什么

  队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。

队列的实现

  队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

队列类型的定义

 typedef int QDataType;typedef struct QNode { struct QNode* next; QDataType data; }QNode; // 队列的结构 typedef struct Queue { QNode* front; QNode* rear; int size;}Queue; 

申请一个节点

QNode* buyQNode(QDataType data)
{QNode *newnode=(QNode*)malloc(sizeof(QNode));if(NULL==newnode){assert(0);return NULL;}newnode->data=data;newnode->next=NULL;return newnode;
}

初始化队列

void QueueInit(Queue* q)
{assert(q);q->front=q->rear=NULL;q->size=0;}

队尾入队列

void QueuePush(Queue* q, QDataType data)
{assert(q);QNode *newnode=buyQNode(data);if(NULL==q->front){q->front=newnode; }else{q->rear->next=newnode; }q->rear=newnode;q->size++;
}

队头出队列

void QueuePop(Queue* q)
{assert(q);if(QueueEmpty(q)){return;}else{QNode *delndoe=q->front;q->front=delndoe->next;free(delndoe);if(NULL==q->front){q->rear=NULL;}}q->size--;
}

获取队列头部元素

 
QDataType QueueFront(Queue* q)
{assert(!QueueEmpty(q));return q->front->data;
}

获取队列队尾元素

QDataType QueueBack(Queue* q)
{assert(!QueueEmpty(q));return q->rear->data;
}

获取队列中有效元素个数

int QueueSize(Queue* q)
{assert(!QueueEmpty(q));return q->size;
}

检测队列是否为空

int QueueEmpty(Queue* q)
{assert(q);return NULL==q->front;
}

销毁队列

void QueueDestroy(Queue* q)
{assert(q);QNode *cur=q->front;while(cur){q->front=cur->next;free(cur);cur=q->front;}q->rear=NULL;q->size=0;
}

测试函数

void TestQueue()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);printf("%d\n", QueueFront(&q));printf("%d\n", QueueBack(&q));printf("%d\n", QueueSize(&q));QueuePop(&q);QueuePop(&q);QueuePop(&q);printf("%d\n", QueueFront(&q));printf("%d\n", QueueBack(&q));printf("%d\n", QueueSize(&q));QueuePop(&q);QueuePop(&q);QueuePop(&q);if(QueueEmpty(&q)){printf("队列已经为空\n");}else{printf("队列不为空\n");}QueueDestroy(&q);
}

完整代码

Queue.h

//链式结构：表示队列 typedef int QDataType;typedef struct QNode { struct QNode* next; QDataType data; }QNode; // 队列的结构 typedef struct Queue { QNode* front; QNode* rear; int size;}Queue; // 初始化队列 void QueueInit(Queue* q); // 队尾入队列 void QueuePush(Queue* q, QDataType data); // 队头出队列 void QueuePop(Queue* q); // 获取队列头部元素 QDataType QueueFront(Queue* q); // 获取队列队尾元素 QDataType QueueBack(Queue* q); // 获取队列中有效元素个数 int QueueSize(Queue* q); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q); // 销毁队列 void QueueDestroy(Queue* q);///void TestQueue();

Queue.c

#include"Queue.h"#include<stdio.h>
#include<assert.h>
#include<malloc.h>//申请一个节点
QNode* buyQNode(QDataType data)
{QNode *newnode=(QNode*)malloc(sizeof(QNode));if(NULL==newnode){assert(0);return NULL;}newnode->data=data;newnode->next=NULL;return newnode;
}//初始化队列 
void QueueInit(Queue* q)
{assert(q);q->front=q->rear=NULL;q->size=0;}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode *newnode=buyQNode(data);if(NULL==q->front){q->front=newnode; }else{q->rear->next=newnode; }q->rear=newnode;q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{assert(q);if(QueueEmpty(q)){return;}else{QNode *delndoe=q->front;q->front=delndoe->next;free(delndoe);if(NULL==q->front){q->rear=NULL;}}q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(!QueueEmpty(q));return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(!QueueEmpty(q));return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(!QueueEmpty(q));return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{assert(q);return NULL==q->front;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);QNode *cur=q->front;while(cur){q->front=cur->next;free(cur);cur=q->front;}q->rear=NULL;q->size=0;
}/
void TestQueue()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);printf("%d\n", QueueFront(&q));printf("%d\n", QueueBack(&q));printf("%d\n", QueueSize(&q));QueuePop(&q);QueuePop(&q);QueuePop(&q);printf("%d\n", QueueFront(&q));printf("%d\n", QueueBack(&q));printf("%d\n", QueueSize(&q));QueuePop(&q);QueuePop(&q);QueuePop(&q);if(QueueEmpty(&q)){printf("队列已经为空\n");}else{printf("队列不为空\n");}QueueDestroy(&q);
}

main.c

#include"Queue.h"int main()
{TestQueue();return 0;
}

三、环形队列

假溢出问题

  正常顺序队列若进行插入和删除，会使前部分的空间浪费，从而造成假溢出的情况。

  未解决假溢出的问题，大佬们提出了一种叫做环形队列的结构，环形队列可以使用数组实现，也可以使用循环链表实现。

  判断循环队列是否为空或者满的问题，通常用（rear-front+N）%N的方法判断是否为满或空。