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

栈

栈的定义

栈：只允许在一端进行插入或删除的操作
事实上，线性表和链表都可以实现栈，但栈的特点更符合用顺序表实现

• 顺序表的队尾相当于栈顶，对栈放入数据，相当于顺序表的下标arr[index++] = x，而栈弹出数据时，相当顺序表的下标index–，即可。
• 相比之下链表就没有这么的符合，入栈时，链表为其创建一个结点进行尾插，出栈时，进行尾删，中间的过程稍微繁琐，并没有顺序表方便
• 所以今天我们也是用顺序表来实现一个栈
  
  

栈的操作

定义

说明：
top：是指向栈顶的位置，还是栈顶的下一个位置，在初始化讨论
capacity：表示栈的容量，因为是用顺序表实现，入栈的时候也需要判断是否现有元素个数是否达到容量
arr：就是个指向数组的指针

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

初始化

说明：
初始化的时候我并没有给数组开辟空间，那么后面入栈的时候再进行扩容
因此capacity也就是0；
top：

1. 这里我将top初始化为0，top指向的是栈顶的下一个元素
   • 此时top指向的是下标为4的位置
   • 而栈内的元素也是4，因此，我们可以用top直接表示栈内的元素个数（优势）
   • 当栈为空时，top为0
     
2. top指向栈顶的位置，当栈为空的时候top为-1；
   这种方式的优势在于可以将top直接当做下标

void STInit(ST* st)
{
	assert(st != NULL);

	st->arr = NULL;
	st->capacity = 0;
	st->top = 0;//指向栈顶的下一个元素
}

入栈

说明：
因为初始化的时候没有给数组开辟空间，所以入栈的时候要考虑是给栈开辟空间还是为栈扩容

void STPush(ST* st, STDataType x)
{
	assert(st != NULL);

	if (st->capacity == st->top)
	{
		int capacity = st->capacity == 0 ? 4 : st->capacity * 2;
		STDataType* newp = (STDataType*)realloc(st->arr, sizeof(STDataType) * capacity);
		if (newp == NULL)
		{
			perror("realloc fail");
			return;
		}
		st->arr = newp;
		st->capacity = capacity;
		newp = NULL;
	}

	st->arr[st->top++] = x;

}

出栈

void STPop(ST* st)
{
	assert(st);

	if (!STEmpty(st))
	{
		st->top--;
	}
}
	

返回栈顶元素

因为这里的top表示栈顶的下一个位置，所以栈顶元素的下标是top-1

STDataType STTop(ST* st)
{
	assert(st);

	if (!STEmpty(st))
	{
		return st->arr[st->top - 1];
	}
	return -1;
}

判断栈是否为空

top为0就表示栈为空

bool STEmpty(ST* st)
{
	assert(st);

	return st->top == 0;
}

返回栈内元素个数

前面说了，top表示为栈顶元素的优点在于，top可以直接表示为元素个数

int STSize(ST* st)
{
	assert(st);

	return st->top;
}

销毁栈

void STDestory(ST* st)
{
	assert(st);

	free(st->arr);
	st->top = 0;
	st->capacity = 0;
	
}

队列

队列的定义

从队的一头插入元素，另一头弹出元素

用顺序表实现还是用链表

• 队列的特点是不符合顺序表来实现的，入队相当于顺序表的尾插，出队时，顺序表将下标为0的元素移除，那么只能将后面的数据依次向前移一位，出一次队就要将整个顺序表移动一次，这样的代价是非常大的。
• 链表就很符合这个特点，入队就相当于尾插，出队就是头插，相比之下很方便，还是链表实现比较好

队列的操作

定义

用链表实现队列，那么就需要用到链表的这个结构体
队列想要入栈，是尾插，那么总不能每次插入一次就将链表遍历一遍寻找尾结点，所以，我们需要一个指针tail去记录尾结点
队列想要出栈，是头插，当然这只是原因之一，因为有了指向头结点的指针才能找到这个链表

typedef int QDataType;
typedef struct ListNode
{
	QDataType data;
	struct ListNode* next;
}ListNode;

typedef struct Queue
{
	ListNode* head;
	ListNode* tail;
}Queue;

初始化

因为队列里还没有元素，指针都置空

void QueueInit(Queue* qu)
{
	assert(qu);

	qu->head = NULL;
	qu->tail = NULL;
}

入队

每一次入队都是先创建一个结点，在进行连接
这里要考虑队列为空的情况与不为空的情况是否可以共用一套代码

void QueuePush(Queue* qu, QDataType x)
{
	assert(qu);

	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	if (new_node == NULL)
	{
		perror("malloc fail");
		return;
	}
	new_node->next = NULL;
	new_node->data = x;
	if (QueueEmpty(qu))
	{
		qu->head = new_node;
		qu->tail = new_node;
	}
	else
	{
		qu->tail->next = new_node;
		qu->tail = qu->tail->next;
	}
}

出队

先考虑队列为空的情况，
接着是不为空，不为空又分为一个结点和多个节点
分别去处理三种情况，尤其是要考虑只有一个结点的情况

void QueuePop(Queue* qu)
{
	assert(qu);

	if (!QueueEmpty(qu))
	{
		ListNode* tmp = qu->head;
		if (qu->head == qu->tail)//这个条件说明只有一个结点
		{
			free(tmp);
			tmp = NULL;
			qu->head = NULL;
			qu->tail = NULL;
		}
		else
		{
			qu->head = qu->head->next;
			free(tmp);
			tmp = NULL;
		}
	}
}

返回队头元素

不为空就返回head指向结点的数据，为空返回-1

QDataType QueueTop(Queue* qu)
{
	assert(qu);

	if (!QueueEmpty(qu))
	{
		return qu->head->data;
	}
	return -1;
}

返回队尾元素

QDataType QueueBack(Queue* qu)
{
	assert(qu);

	if (!QueueEmpty(qu))
	{
		return qu->tail->data;
	}
	return -1;
}

判断队列是否为空

判断是否为空很简单，只用判断两个指针是否同时为空
但也要考虑到意外状况，如果在函数外传参传错，导致两个指针其中一个为空，一个不为空，这种情况检查起来非常麻烦，所以在这里断言一下

bool QueueEmpty(Queue* qu)
{
	assert(qu);
	assert(!(qu->head == NULL && qu->tail != NULL));
	assert(!(qu->head != NULL && qu->tail == NULL));

   return qu->head == NULL && qu->tail == NULL;
}

返回队列元素个数

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

	int size = 0;
	ListNode* cur = qu->head;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

销毁队列

相当于销毁一个链表，最后函数结束时，手动将实参qu置空

void QueueDestory(Queue* qu)
{
	assert(qu);

	ListNode* cur = qu->head;
	while (cur != NULL)
	{
		ListNode* nxt = cur->next;
		free(cur);
		cur = nxt;
	}
	qu->head = NULL;
	qu->tail = NULL;
}