栈与队列小总结

思维导图：

 

一 ，栈

栈，一种数据结构。具有后进先出的特点。有两种实现方式，第一种实现方式就是用数组结构来实现，第二种方式就是用链表的方式来实现。但是由于使用数组的方式来实现栈会更加的好，所以在这里我们用数组的方式来实现栈。

栈的实现：

 1.栈的结构定义

栈的结构中有三个元素，一个是数组指针，一个是整型的Top(来指向栈顶元素），一个是整型的Capacity（来显示栈的容量情况）。代码如下：

typedef int DataType;
typedef struct ST
{
	DataType* a;//数组指针
	int Top;//栈顶指针
	int capaCity;//容量
}ST;

2.栈的初始化

栈的初始化的作用就是让栈里的元素有一个初始值，要不然会报错。在这里我将指针的初始值设为NULL,容量设为0。在这里我还把Top值设为0，设为0以后Top指向的就相当于栈顶元素的下一位。代码如下：

 代码：

void STinit(ST* stack)
{
	assert(stack);
	assert(stack->a);
	stack->a = NULL;
	stack->Top = 0;
	stack->capaCity = 0;
}

 3.栈的插入

栈的插入只能插入一个位置，这个位置就是栈顶。栈只能从栈顶插入。代码如下：

 代码：

void STpush(ST* stack,int x)
{
	assert(stack);
	if (stack->capaCity == stack->Top)//扩容操作
	{
		int newCapacity = stack->capaCity == 0 ? 4 : 2 * stack->capaCity;
		stack->a = (DataType*)realloc(stack->a, newCapacity * sizeof(DataType));
		if (stack->a == NULL)
		{
			perror("realloc fail");
			return ;
		}
		stack->capaCity = newCapacity;
	}
		stack->a[stack->Top] = x;
		stack->Top++;
}

当a为NULL时，realloc的作用相当于malloc。

4.栈的删除

栈的删除操作也是一个较为简单的操作。不过要对栈是否为NULL进行判断，因为空栈不能删除。栈的删除操作代码如下：

bool STEmpty(ST* stack)//判断栈是否为NULL
{
	assert(stack);
	return stack->Top == 0;
}
void STPop(ST* stack)
{
	assert(stack);
	assert(!STEmpty(stack));
	stack->Top--;//栈的删除操作就是将下标--
}

5.获取栈顶元素

栈是一个数组，它的顶是在数组的最后面。获取一个数组的最后面的代码便是将下标为Top-1位置上的数组元素返回。代码如下：

DataType* STFront(ST* stack)
{
	assert(stack);
	assert(stack->a);
	DataType* front = stack->a[stack->Top - 1];
	return front;
}

 6.销毁栈

栈使用完了便要销毁栈，注意栈内有一个malloc出来的数组，所以就要free掉。

二，队列

队列，也是一种数据结构。队列的特点就是先进先出。队列的实现方式也有两种，那就是数组实现与单链表的方式实现。那种方式更好呢？答案是单链表的方式实现会更好。所以在此我会写一个以单链表的方式实现的队列。

队列的实现

1.队列的结构

队列的结构相比于栈会复杂一些，原因是因为队列的结构会有两层嵌套。定义队列结构的代码如下：

代码：

typedef int DataType;
typedef struct Qnode//队列中的一个节点
{
	DataType val;
	struct Qnode* next;
}Qnode;

typedef struct Queue//一整个队列
{
	Qnode* phead;
	Qnode* ptail;
	int size;
}Queue;

2.初始化 

 初始化就是一个老套路了，基本上每次写这些结构都要初始化。指针型的初始化为NULL,整型的初始化为0。代码如下：

 代码：

void QInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

3.队列中数据的插入

队列的插入不需要检查容量，但是需要生成新的队列节点。并且队列的插入是尾插。队列的插入还需要分两种情况——1.队列为空时，2.队列不为空时。所以队列的插入代码如下：

 代码：

void QPush(Queue* pq,DataType x)
{
	assert(pq);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	if (pq->ptail == NULL)//分两种情况
	{
		assert(!pq->phead);
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->ptail->val = x;
	pq->size++;
}

4.从队列中删除数据

队列中的删除操作也是头删的操作，所以根据链表的头删操作，队列的删除操作代码如下：

代码：

void QPop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//判断pq是否为空，空队列不能删
	Qnode* cur = pq->phead;
	Qnode* next = cur->next;//记录下一个节点
	free(cur);//释放掉cur
	pq->phead = next;
	pq->size--;
}

 5.获取头，尾节点的值

这个操作是十分简单的，不过就是将phead，ptail指向的节点的值返回。代码如下：

代码：

DataType QFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);//pq->phead不能为NULL
	return pq->phead->val;
}
DataType QBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);//pq->ptail不能为NULL
	return pq->ptail->val;
}

 4.队列的销毁

因为这篇博客里写的队列是按照链表的形式来写的，所以队列的销毁操作也就可以参照链表的销毁形式来写。代码如下：

void QDestory(Queue* pq)
{
	assert(pq);
	while (!QueueEmpty(pq))
	{
		Qnode* cur = pq->phead;
		Qnode* next = cur->next;
		free(cur);
		pq->phead = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}