目录

1.栈

1.1概念与结构

1.2栈的实现

1.2.1定义一个栈的结构

1.2.2初始化栈 

1.2.3入栈

1.2.4出栈

1.2.5取栈顶元素

1.2.6获取栈中有效元素个数

1.2.7销毁栈

2.队列

2.1概念与结构

2.2队列的实现

2.2.1 定义队列结构和队列结点结构

2.2.2初始化队列

2.2.3入队列

2.2.4出队列，队头

2.2.5取队头数据

2.2.6取队尾数据

2.2.7队列有效数据个数

2.2.8销毁队列

1.栈

1.1概念与结构

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

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

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

我们可以理解为给手枪弹匣装子弹，先装进去的子弹最后面才射出去，后装进的子弹先射出去。

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

1.2栈的实现

#include #include #include #include //定义一个栈的结构 typedef int	STDatatype; typedef struct stack { 	STDatatype* data; //数组 	int capacity;    //栈的空间的大小 	int top;        //有效数据个数 }ST;  //初始化 void STInite(ST* ps);  //销毁 void STDestroy(ST* ps);  //入栈 void STPush(ST* ps, STDatatype x);  //出栈 void STPop(ST* ps);  //判断栈是否为空 bool STEmpty(ST* ps);  //取栈顶个数 STDatatype STTop(ST* ps);  //获取栈顶有效元素的个数 int STSize(ST* ps);  

1.2.1定义一个栈的结构

栈的结构的定义和顺序表结构定义一样，在栈中定义一个指针data用于操作数据，然后定义整型变量capacity用于表示栈的空间大小，最后定义一个整型变量top用于表示有效数据个数也就是我们的栈顶。

//定义一个栈的结构 typedef int	STDatatype; typedef struct stack { 	STDatatype* data; //数组 	int capacity;    //栈的空间的大小 	int top;        //有效数据个数 }ST; 

1.2.2初始化栈 

第二步，我们需要初始化栈将指针data置空，将capacity和top置成0，便于后面我们对于栈进行操作。

//初始化 void STInite(ST* ps) { 	assert(ps); 	ps->data = NULL; 	ps->capacity = ps->top = 0; } 

1.2.3入栈

我们需要定义一个STPush函数，将栈的结构体的地址和我们要入栈的元素传过去，然后我们需要判断一下栈的空间是否充足，如果不够我们就需要扩容，当栈的空间和栈顶一样大时，我们就需要扩容了我们需要用realloc函数来调整我们栈的空间大小。方法和之前的顺序表一样，就不过多解释了。扩完容之后我们就需要入栈了，和顺序表的尾插是一样的，栈顶就是我们要插入的位置，插入完成后之后栈顶要往后走一个。

//入栈 void STPush(ST* ps, STDatatype x) { 	assert(ps); 	//判断一下空间是否充足 	if (ps->capacity == ps->top) 	{ 		//扩容 		int newcapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity); 		STDatatype* tmp = (STDatatype*)realloc(ps->data, newcapacity * sizeof(STDatatype)); 		if (tmp == NULL) 		{ 			perror("realloc fail!"); 			exit(1); 		} 		ps->data = tmp; 		ps->capacity = newcapacity; 	} 	//插入数据 	ps->data[ps->top++] = x; }

1.2.4出栈

出栈相当于顺序表的尾删，我们需要定义一个STPop函数将栈结点的地址传过去，然后我们需要判断一下栈是否为空创建一个STEmpty函数，函数返回值为bool类型，当栈顶为0时栈为空。判断完之后，我们就要进行出栈也就是顺序表的尾删，将栈顶--就好了。

//判断栈是否为空 bool STEmpty(ST* ps) { 	assert(ps); 	return ps->top == 0; }  //出栈 void STPop(ST* ps) { 	assert(ps); 	//判断栈是否为空 	assert(!STEmpty(ps));  	--ps->top; }

1.2.5取栈顶元素

我们需要定义一个函数STDatatype STTop（ST* ps）；然后，要判断栈是否为空，最后我们将栈的最后一个元素返回就完成了。

//取栈顶元素 STDatatype STTop(ST* ps) { 	assert(ps); 	//判断栈是否为空 	assert(!STEmpty(ps)); 	return ps->data[ps->top - 1 ]; }

1.2.6获取栈中有效元素个数

直接返回top的值就行了。

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

1.2.7销毁栈

和销毁顺序表一样。

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

2.队列

2.1概念与结构

概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作，的特殊线性表，队列具有先进先出FIFO（First In First Out）。

入队列：进行插入操作的一端叫做队尾

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

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

2.2队列的实现

#include #include #include #include  //链式结构表示队列 typedef int	QDatetype; typedef struct QueueNode { 	QDatetype data; 	struct QueueNode* next;  }QNode;  //队列结构 typedef struct Queue { 	struct QueueNode* phead; 	struct QueueNode* ptail; 	int size;//计数器 }Queue;  // 初始化队列  void QueueInit(Queue* pq);  //销毁 void QueueDestory(Queue* pq);  //入队列，队尾 void QueuePush(Queue* pq, QDatetype x);  //出队列,队头 void QueuePop(Queue* pq);  //取队头数据 QDatetype QueueFront(Queue* pq);  //取队尾数据 QDatetype QueueBack(Queue* pq);  //队列有效数据个数 int Queue

2.2.1 定义队列结构和队列结点结构

队列的结点结构就是单链表结点结构，队列结构phead指向头结点和ptail指向尾结点，还有一个size用同统计结点个数。

//链式结构表示队列 typedef int	QDatetype; typedef struct QueueNode { 	QDatetype data; 	struct QueueNode* next;  }QNode;  //队列结构 typedef struct Queue { 	struct QueueNode* phead; 	struct QueueNode* ptail; 	int size;//计数器 }Queue;

2.2.2初始化队列

我们需要将头结点和尾结点的指针置为空指针，然后将size置为0.

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

2.2.3入队列

由于队列的特性我们不能遍历队列，因此我们需要从尾部插入数据，和我们的单链表尾插一样。我们需要先创建一个新的结点，然后将原来的尾结点的next指向新插入的结点然后将ptail指向新的尾结点。结点个数加一个。

void QueuePush(Queue* pq, QDatetype x) { 	assert(pq); 	//申请新的结点 	QNode* newnode = (QNode*)malloc(sizeof(QNode)); 	if (newnode == NULL) 	{ 		perror("malloc fail!"); 		exit(1); 	} 	//申请成功，开始赋值 	newnode->data = x; 	newnode->next = NULL; 	//队列为空 	if (pq->phead==NULL) 	{ 		pq->phead = pq->ptail = newnode; 	} 	else 	{ 		//队列不为空 		pq->ptail->next = newnode; 		pq->ptail = newnode; 	} 	//入队列成功 	pq->size++; } 

2.2.4出队列，队头

出队列我们需要从队头出，也就是删除头结点。我们需要先判断一下队列是否为空，当队列的头结点和尾结点都为NULL时队列为空，然后我们需要先记录下当前头结点的下一个结点的位置，然后将头结点的空间释放掉，最后将头结点指向我们记录的下一个结点的位置。结点个数减一个。

bool QueueEmpty(Queue* pq) { 	assert(pq); 	return pq->phead == NULL && pq->ptail == NULL; }  //出队列,队头 void QueuePop(Queue* pq) { 	assert(pq); 	//判断队列是否为空 	assert(!QueueEmpty(pq));  	//只有一个结点，避免ptail成为野指针 	if (pq->phead == pq->ptail) 	{ 		free(pq->phead); 		pq->phead = pq->ptail = NULL; 	} 	else 	{ 		//删除队头元素 		QNode* Next = pq->phead->next; 		free(pq->phead); 		pq->phead = Next; 	} 	--pq->size; } 

2.2.5取队头数据

这个很简单，我们需要先判断一下队列是否为空，然后把头结点的data返回就行了。

//取队头数据 QDatetype QueueFront(Queue* pq) { 	assert(pq); 	//判断一下队列是否为空 	assert(!QueueEmpty(pq)); 	return pq->phead->data; }

2.2.6取队尾数据

和上面的取队头数据差不多，先判断队列是否为空，然后将尾结点的data返回。

//取队尾数据 QDatetype QueueBack(Queue* pq) { 	assert(pq); 	//判断一下队列是否为空 	assert(!QueueEmpty(pq)); 	return pq->ptail->data; }

2.2.7队列有效数据个数

直接返回队列结构体的size就好了。这就是我们定义size最大的用途，相当于计数器。

//队列有效数据个数 int QueueSize(Queue* pq) { 	assert(pq); 	return pq->size; }

2.2.8销毁队列

和销毁单链表一样。直接上代码。

//销毁 void QueueDestory(Queue* pq) { 	assert(pq); 	//判断一下队列是否为空 	assert(!QueueEmpty(pq)); 	QNode* pcur = pq->phead; 	while (pcur) 	{ 		QNode* Next = pcur->next; 		free(pcur); 		pcur = Next; 	} 	pq->size = 0; 	pq->phead = pq->ptail = NULL; }