数据结构初阶---栈和队列

一、栈Stack

1.栈的概念

栈是一种特殊的线性表，只允许在固定的一端进行插入与删除操作。进行插入与删除操作的一端被称之为栈顶，另一端称之为栈底。栈中的数据元素遵循先进后出(FILO)或者说后进先出(LIFO)原则

栈的插入操作称之为压栈/入栈/进栈；

栈的删除操作称之为出栈。

栈的插入与删除操作均在栈顶进行。

注：先进后出FILO---Fisrt In Last Out ；后进先出LIFO---Last In First Out。

对于栈而言，规定只能从栈顶开始读取数据并删除数据。

对于栈而言，入栈顺序与出栈顺序是一对多。

关于栈的图解：

2.栈的实现

对于栈的实现，分为数组栈ArrayStack，链式栈LinkStack。链式栈的实现又可以分为双向链表与单链表栈的实现。

那么我们具体应该选择何种方式进行栈的实现呢？

其实三种都可以选择，但是考虑到缓存效率，数组栈是最优的，物理上连续给予了数组栈较高的缓存效率。我们也可以实现链式栈。

使用链式结构主要是在结构的构建上比较复杂，在后续的接口实现上比起数组要相对简单，但是数组结构的构建要简单一些，因此其实难度大差不差。

那么我们以数组栈为例：

3.数组栈AStack

结构如下：

#define AStackDataType int
typedef struct ArrayStack//数组栈
{
	AStackDataType* a;
	int top;//栈顶
	int capacity;//空间容量
}AS;

接口函数

①初始化AStackInit

void AStackInit(AS* pas); 

对于栈而言，初始化依然可以选择开辟空间或者不开辟空间，如果这里不开辟空间，而是置空以及0，那么在插入前的容量检查接口中，我们就得判断空间然后扩容。

//初始化
void AStackInit(AS* pas)
{
	assert(pas);
	//还是先不开辟空间
	pas->capacity = 0;
	pas->top = 0;//top如果初始化0--->top最后指向栈顶后一个位置，类似数组长度size
	//pas->top = -1;//top初始化-1--->top最终指向栈顶、类似下标了
	pas->a = NULL;
}

注意top初始化的值：

[i] 如果top初始化为0，第一个数据插入则top为1，那么top作为下标而言，就是栈顶的下一个位置；作为值而言，就是栈的数据个数。栈顶元素下标为 top-1。

[ii] 如果top初始化为-1，第一个数据插入则top为0，那么top作为下标就是栈顶元素下标。

②容量检查AStackCheckMemory

只在插入接口中用得上，也可以直接写到插入接口内。  

void AStackCheckMemory(AS* pas); 

top初始化为0时，代表了top的值就是栈中数据的个数 ，那么如果top == capacity，说明了空间不够了，需要扩容，扩容又需要考虑第一次capacity为0的情况，那么使用一个三目操作符即可，其实与前面顺序表的扩容操作是一样的。

void AStackCheckMemory(AS* pas)
{
	if (pas->capacity == pas->top)
	{
		int NewCapacity = pas->capacity == 0 ? 4 : pas->capacity * 2;
		AStackDataType* tmp = (AStackDataType*)realloc(pas->a, sizeof(AStackDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		pas->a = tmp;
		pas->capacity = NewCapacity;
	}
}

③销毁栈AStackDestroy

void AStackDestroy(AS* pas); 

对于栈的销毁，直接释放数组a的空间即可，然后top、capacity置0，a置空。 

//销毁栈
void AStackDestroy(AS* pas)
{
	assert(pas);
	free(pas->a);
	pas->a = NULL;
	pas->capacity = 0;
	pas->top = 0;
}

④栈顶插入AStackPush

void AStackPush(AS* pas, AStackDataType x); 

对于数组栈而言，栈顶插入数据，其实就是尾插，数组的尾插就非常简单了，直接访问尾部(栈顶)然后在top位置插入数据，注意top如果初始化0，那么top始终指向栈顶的下一个位置，所以插入后别忘记top自增1。

//插入
void AStackPush(AS* pas, AStackDataType x)
{
	assert(pas);
	AStackCheckMemory(pas);
	pas->a[pas->top] = x;
	pas->top++;
}

⑤栈顶删除AStackPop

void AStackPop(AS* pas); 

栈中有效元素是从栈底(数组首元素)开始，到栈顶(top-1)，那么我们只需要将top自减1，那么对于栈顶而言，就向前移了一步，即完成了栈顶的删除，也不需要对原来栈顶的数据进行修改。

唯一需要注意的就是栈内没有数据时需要进行断言，不能进行删除操作，只有一个数据没有问题。

//删除
void AStackPop(AS* pas)
{
	assert(pas);
	assert(pas->top > 0);//栈内无数据不能删除
	pas->top--;
}

⑥获取栈顶元素AStackTop

AStackDataType AStackTop(AS* pas); 

我们使用数组实现栈，好处其一就是下标的随机访问很方便，获取栈顶元素，那么直接访问top-1处的元素即可，同时我们要对-1这些字眼很敏感，当top为0时栈内无数据啊a[top-1]越界，需要断言，top为1时没有问题。

//获取栈顶元素
AStackDataType AStackTop(AS* pas)
{
	assert(pas);
	assert(pas->top > 0);//栈内无数据不能获取
	return pas->a[pas->top-1];
}

⑦获取栈有效元素个数AStackSize

int AStackSize(AS* pas); 

 我们将top初始化为0的好处在这个接口上也体现出来了，那么有效元素个数就是top的值。

//获取栈中有效元素个数
int AStackSize(AS* pas)
{
	assert(pas);
	return pas->top;
}

⑧检测栈是否为空AStackEmpty

bool AStackEmpty(AS* pas);

检测栈是否为空，为空返回true、不为空返回false。

top为0代表栈为空，top不为0代表栈不为空：

//检测栈是否为空，为空返回true，不为空返回false
bool AStackEmpty(AS* pas)
{
	assert(pas);
	return pas->top == 0;
	//if (pas->top == 0)
	//	return true;
	//else
	//	return false;
}

4.Extra---数据结构与操作系统的栈

数据结构的栈与操作系统(OS)的栈不是一个栈，数据结构的栈是一种数据的存储形式；操作系统中的栈是内存中的一块区域，里面存放临时变量以及函数的形式参数等。

栈溢出中的栈指的是内存(操作系统)中的栈，栈溢出指的是因为某些情况如函数递归返回条件出现问题导致栈的使用空间一直增加且无法回收，那么就会导致栈溢出。

二、队列Queue

1.队列的概念

只允许在一端进行数据的插入，在另一端进行数据的删除操作的特殊线性表，具有先进先出(FIFO)的原则。

入队--->在队尾插入数据

出队--->在队头删除数据

数据从队尾进入，最先进入的数据就会处于队头，最先出队(删除)。

对于队列而言，只能在队头读取数据并且删除。

对于队列而言，入队顺序与出队顺序始终是一对一。

如入队12345678---出队12345678。

2.队列的实现

同栈一样，可以使用数组、链表来实现队列：

数组实现队列，如果我们头插，那么会面临着数据的挪位，如果我们尾插，那么尾插虽然方便，但是就会面临到头删的问题，同样也会面临挪位的问题，但是也可以解决，比如说不通过挪位，而是挪动队头下标front和队尾下标back来解决。

链表实现队列，单链表头插就得尾删，尾插就得头删，也不是很方便，但是同样可以解决，如我们再定义一个尾指针tail，由于尾插不需要尾删，因此一个尾指针就能够满足尾插(如果尾删还需要尾结点前一个结点)。这样的话我们选择尾插和头删。

由于栈我们使用了数组实现，那么队列我们就选择单链表实现。

3.链式队列LinkQueue

结构：

#define QueueDataType int 
typedef struct QueueNode
{
	QueueDataType val;
	struct QueueNode* next;
}QNode;

为了便于后面函数传参的简洁，我们再定义一个结构体，成员为头尾指针phead与ptail，同时定义一个size用于记录队列数据个数：

typedef struct Queue
{
	QNode* phead;//头
	QNode* ptail;//尾
	int size;//记录队列数据个数
}Queue;

接口函数

①初始化QueueInit

void QueueInit(Queue* pq); 

pq指针调用成员头指针、尾指针和数据个数，将头指针phead与尾指针ptail置空，数据个数size置为0。

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

②销毁QueueDestroy

void QueueDestroy(Queue* pq); 

在插入接口中，我们对链表进行了空间的开辟，那么需要释放开辟的空间，定义一个QNode*的指针cur，遍历释放空间，注意记录下一个结点的位置。释放完对phead、ptail置NULL，size置0。

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		//pq->phead = pq->phead->next;//不直观
		free(cur);
		cur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

与前面的链表的销毁相同。 

③队尾插入QueuePush

void QueuePush(Queue* pq, QueueDataType x); 

在队尾插入，就是在尾结点ptail后插入，分为两步，首先我们创建一个结点newnode，将结点newnode的next指向NULL，x值赋给newnode的val。然后将ptail->next指向该结点，同时将ptail往后移。但是，队列中没有结点时，就不能ptail->next了，要直接将newnode赋给phead与ptail。

//插入
void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	//创建插入的结点newnode
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;

	//插入
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

最后由于插入了一个数据，不要忘记将size自增1。 

④队头删除QueuePop

void QueuePop(Queue* pq); 

空队列的时候进行断言，不能进行删除。

删除队头结点，将phead指向后一个结点，释放原来的队头结点。当队列只有一个数据，也就是链表只有一个结点时，我们不仅需要将phead指向下一个结点(其实就是NULL)，同时要将ptail指向NULL，不然就会导致ptail野指针，指向了一块释放掉了的空间。

//删除
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);//无结点
	QNode* cur = pq->phead;
	QNode* next = cur->next;
	free(cur);
	cur = NULL;
	pq->phead = next;
	if (pq->phead == NULL)
		pq->ptail = NULL;

	pq->size--;
}

最后不要忘记size自减1。

⑤获取队头元素QueueFront

QueueDataType QueueFront(Queue* pq); 

队头元素，phead指向的结点的val值即是队头元素。同时队列不能为空，进行断言。

//获取队列头部元素
QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);//队列不为空

	return pq->phead->val;
}

⑥获取队尾元素QueueBack

QueueDataType QueueBack(Queue* pq); 

队尾元素，ptail指向的结点中的val值即为队尾元素。同样队列不能为空，断言。

//获取队列尾部元素
QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead);//断言pq->phead或者pq->ptail都是一样的

	return pq->ptail->val;
}

⑦获取队列有效元素个数QueueSize

int QueueSize(Queue* pq); 

前面Queue结构体中我们创建了一个成员变量size记录了数据个数，这里直接返回。可以是空队列。

//获取队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

⑧检测队列是否为空QueueEmpty

bool QueueEmpty(Queue* pq);

为空返回true，不为空返回false。 

这个可以用phead或者ptail或者size判断，phead或者ptail为空、size为0，那么就是空队列，反之不是空队列。

//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->phead == NULL;
}

 有关栈与队列的三个选择题：