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

栈

栈的定义

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

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

栈的操作

定义

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

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

初始化

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

这里我将top初始化为0，top指向的是栈顶的下一个元素
- 此时top指向的是下标为4的位置
- 而栈内的元素也是4，因此，我们可以用top直接表示栈内的元素个数（优势）
- 当栈为空时，top为0
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;
}