目录

1.栈

1.1栈的选型

1.2 实现代码

2.队列

2.1整体思路

2.2初始化和销毁

2.3出入队列

2.4取队列元素

2.5判断队列是否为空

2.6返回队列中元素个数 

2.7 Test 

---

1.栈

1.1栈的选型

1.2 实现代码

初始化如下

typedef int STDataType;
typedef struct Stack {
	STDataType* arr;
	int capacity;
	int top;
}ST;

stackpush是唯一的放入数据的操作

top等于零时每插入一个元素就top++,指向栈顶元素的下一个

top指向栈顶元素的话必须让top=-1，如果还让top=0，那top=0时就不能区分此时是否有元素。

其余接口的实现（几乎等同于顺序表）：

void STInit(ST* pst) {
	assert(pst);
	pst->top = 0;//初始状态可以是0也可以是-1
	pst->capacity = 0;
	pst->arr = NULL;
}

void STPush(ST* pst,STDataType x) {
	assert(pst);
	if (pst->top == pst->capacity) {
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->arr, sizeof(STDataType) * newcapacity);
		if (!tmp) {
			perror("realloc failed!");
			exit(1);
		}
		pst->arr = tmp;
		pst->capacity = newcapacity;
	}
	pst->arr[pst->top++] = x;
}

void STPop(ST* pst) {
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}

STDataType STTop(ST* pst) {
	assert(pst);
	assert(!STEmpty(pst));
	return pst->arr[pst->top - 1];
}

//删除或者取栈顶数据时都需要判断栈是否为空
bool STEmpty(ST* pst) {
	assert(pst);
	return pst->top == 0;
}

int STSize(ST* pst) {
	assert(pst);
	return pst->top;
}

void STDestroy(ST* pst) {
	assert(pst);
	free(pst->arr);
	pst->arr = NULL;
	pst->capacity = 0;
	pst->top = 0;
}

 应用时，注意函数声明的顺序

栈的出入顺序不一定是固定的

答案是C

链式栈（单链表）建议将头作为栈顶，因为栈尾不方便进行删除操作。

2.队列

  队列：

    恰好与栈不同。

2.1整体思路

     用链表实现（单链表就足够了）更为合适，因为当数据的出和入不在同一边，若使用数组，势必有一段需要O(n)的复杂度来整体移动数组。

                  

       对于涉及链表尾部的操作，为了不遍历链表，我们加入一个ptail变量。

       因为涉及改变phead（队头）和ptail（队尾）的值，所以我们首先考虑使用phead和ptail的二级指针来维护头尾指针

struct Queue{
    QNode** pphead;
    QNode** pptail; 
};

单纯的链表不需要结构体来包含整个链表，但是队列需要结构体。我们可以类比的来看，顺序表中间有很多个值需要配合使用，所以不仅每个元素是结构体，整个顺序表也是个结构体。队列需要同时有头指针和尾指针（实现尾差和头删的功能），单独放两个有关队列的指针不合适，所以将两个指针放在一起构成一个新的结构体

（链表相对于队列，类似数组相对于顺序表）

    同时，将phead和ptail放进一个结构体时，上文所讲的二级指针问题也不存在了，可以直接通过结构体指针去更改phead和ptail

左为队列，右为链表 

（目前为止的队列和单链表的对比，本质依然是新瓶装旧酒）

 以上的设计在函数QueueSize（求队列中元素个数）中复杂度依然是O(n)，但是如果在初始化和定义队列时加上size这个变量（加数据++，减数据--），整体复杂度又变回了O(1)。

        因此，数据结构的设计是灵活多变的，只是有一些传统，在传统的结构上我们应该根据自己的需要来增加、修改（包括是否需要size，是否需要哨兵位，是否需要头尾两个指针）

typedef int QDataType;
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;

//为了便于维护，我们将链表进行设计而得到队列
typedef struct Queue {
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

再按照之前链表的实现方式，实现队列的各个接口。

2.2初始化和销毁

有了整体思路，目前学习的数据结构都应该先实现初始化和销毁接口。

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

void QueueDestroy(Queue* pq) {
	assert(pq);
	QNode* cur = pq->phead;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

2.3出入队列

只有“入队列”一个函数需要malloc，所以我们不再封装BuyNewNode函数：

void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail!");
	}

	newnode->val = x;
	newnode->next = NULL;

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

  每次进入队列，ptail就向后走，所以出队列的时候就应该出phead位置的Node 

但是以上代码有问题如下：

1.size数值没有变化

2.红笔圈出的部分可能是 NULL ptr

3.如果只有一个节点的话，ptail即将变成野指针

因此，对于出队列，需要分成：多个节点，一个节点，零节点三种情况进行讨论

void QueuePop(Queue* pq) {
	assert(pq);
	//0个节点，使用此类暴力检查或者带if语句的温柔检查
	assert(pq->phead && pq->ptail);
	//一个节点，单独
	if (pq->phead->next == NULL) {
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

2.4取队列元素

虽然从理论上讲，队列只会从phead处取出数据，但是在具体运用中（如银行人工窗口的取号系统），我们要能够从头或者尾取出数据。

                                                  

实现如下： 

QDataType QueueFront(Queue* pq) {
	assert(pq);
	//必须使用暴力检查，因为有返回值
	assert(pq->phead);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq) {
	assert(pq);
	//必须使用暴力检查，因为有返回值
	assert(pq->ptail);

	return pq->ptail->val;
}

不同于没有返回值的出入队列函数，这两个函数都有返回值，若不适用暴力检查   来报错，就会返回一个不正确的值，埋下bug的种子。

Tips:

有读者问为什么后面的这些函数没使用perror检查是否成功，原因如下：

1.perror适用于偏系统的调用失败（如 malloc realloc）

2.这些调用如果真的失败，那电脑很可能已经出了大问题（那么小的空间都开辟不出来！！）

                                                    

2.5判断队列是否为空

bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->size == 0;
}

很巧妙的写法，如果siez为0就返回1，表示确实为空。

2.6返回队列中元素个数 

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

体现了size变量的好处。

2.7 Test 

不管是队列还是栈，检验方法都不同于之前的链表和顺序表，需要一个print函数来打印，队列和栈都是边使用边出，遍历一遍之后数据就全部出去了。

先检查入队列和取头功能

 最正确的测试方法：

数据用一个出一个。