目录

1.栈底层结构的选择

2.栈的实现

3.栈

3.1入栈

3.2出栈

3.3栈顶删除

4.队列

4.1队列介绍

4.2队列初始化

4.3入队列

4.4队头删除

---

---

1.栈底层结构的选择

栈是一种数据结构

具有“后进先出的”的特点

现在面临的两种选择，一种是顺序表，另一种是链表。选择顺序表应该是优于链表的，链表的出栈和入栈时过于复杂，可以选用顺序表，仅需改变数组的下标即可实现。

2.栈的实现

栈首先要有栈顶，容量，和数据。

存入栈的数据只能出栈顶的数据，不能修改栈底的数据以及其他的数据，栈顶我们用top来表示，顺序表是arr,capacity来表示栈的容量大小。

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

这样栈的结构实现好了，接着实现栈的功能。

3.栈

3.1入栈

入栈之前我们要确保栈还有多余的空间可以留给新的数据，所以要对栈进行检查容量大小。

if (ps->top == ps->capacity)
{
	int tmp = ps->capacity == 0 ? 4 : 2 * ps->capacity;
	STDataType* p = (STDataType*)realloc(ps->arr, sizeof(STDataType) * tmp);
	if (p == NULL)
	{
		perror("realloc Fail");
		exit(1);
	}
	else
	{
		ps->arr = p;
		ps->capacity = tmp;
	}
}

如果top和capacity相等的话，就要进行扩容。

3.2出栈

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

 值得注意的是出栈之情要检查是否为空指针，是否为空栈。

3.3栈顶删除

栈顶删除就是将top减一即可，这里不做过多解释。

void STPop(ST* ps)
{
    assert(!StackEmpty(ps));
    assert(ps);
    ps->top--;


}

4.队列

4.1队列介绍

队列是使用链表实现的，包含队头队尾，队列节点等。

4.2队列初始化

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

4.3入队列

void QueuePush(Queue* pq, QDataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc faild");
		exit(1);
	}
	else
	{

		newnode->data = x;
		newnode->next = NULL;
	}

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

入队列需要先创建一个队列节点，然后将需要插入的数据x赋给新节点。

值得注意的是要先确定pq和pq是非空的。

4.4队头删除

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* tmp = pq->phead->next;
		free(pq->phead);
		pq->phead = tmp;
	}
	pq->size--;

}

如果对头和队尾相等，此时是只有一个节点，直接将头节点释放就行，然后将头尾节点置为空指针。

如果头尾不相等，那先创建一个临时指针保存phead，然后释放头节点，最后将头节点置为tmp即可，最后要将size--，这样一个删除的接口就实现好了。

队列主要的难实现的函数就是这些，其他的简单的这里就不解释了。