【数据结构初阶】栈和队列的建立

栈

概念和结构

栈是一种特殊的线性表，它只允许一端进行插入和删除数据操作，这一端被称为栈顶，则另一端被称为栈底，而栈内的数据遵循后进后出，先进后出的原则

入栈：栈的插入操作被称为进栈、入栈、压栈，插入的数据在栈顶

出栈：栈的删除操作被称为出栈，删除的数据也在栈顶

那我们要如何实现栈这个特殊的线性表呢？

在前面我们学过顺序表和链表，而栈的实现也可以使用顺序表或者链表来实现，那使用哪一种更好呢？

用顺序表来实现栈本质上就是用数组来实现，根据栈的特性：后进后出，先进后出可知，要用数组来实现栈就需要，将数组的尾部为作为栈的栈顶，来进行数据的插入和删除如此才能最大限度地减小在时间和空间的浪费（时间复杂度都为O(1)）

而使用链表实现栈，则最好是使用头节点为栈顶，进行头插、头删，但使用链表需要用到指针会比使用数组麻烦很多，所以我们大多数时候使用数组来实现栈，但链表也是可以的，在本文中我们就使用数组来实现一个栈

栈的实现

栈的结构

已知栈使用数组来实现，所以它的结构和顺序表差不多，唯一要考虑的就是栈是在栈顶实现插入和删除，所以要考虑的就是栈顶的元素，在数组中就是栈顶元素下标后一位

若有对顺序表的建立有什么困惑可以移步到该文中

手打顺序表：详细讲解顺序表的组成及原理，细节满满！！！_第1关:实现顺序表各种基本运算的算法-CSDN博客

typedef int STDataType;typedef struct Stack
{STDataType* arr;int top;//指向栈顶位置int capacity;//栈的容量
}ST;

栈的初始化

栈的初始化和顺序表是一样的

// 初始化栈
void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}

入栈

栈的数据插入在数组中和顺序表的尾插差不多，都是先判断空间是否不足，要是不足就进行空间的扩容，最后再在数组的尾部插入数据，记住栈的top要加一

// ⼊栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* temp = realloc(ps->arr, sizeof(STDataType) * newcapacity);if (temp == NULL){perror("realloc fail!");exit(1);}ps->arr = temp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}

出栈

栈的删除数据就和顺序表删除一样很简单，但在删除前要考虑栈是否为空，要是为空就不进行操作

//栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//出栈
void StackPop(ST* ps)
{assert(!StackEmpty(ps));//栈顶不能为空--ps->top;
}

获取栈顶元素

在栈的结构中已经定义好了top为栈顶元素下标的下一位，所以就只需要返回top下标的前一位，但在这之前也要判断栈是否为空

//取栈顶元素
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top-1];
}

获取栈中有效元素个数

这一步就很简单，直接返回结构中top就行了

//获取栈中有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}

销毁栈

栈的销毁和顺序表的销毁是一样的

// 销毁栈
void StackDestroy(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = ps->capacity = 0;
}

就此我们实现了一个简单的栈，该有的功能都有实现，如果你想扩展能够实现它功能，可以自己尝试一下哈

队列

概念和结构

队列和栈一样也是一种特殊的线性表，它特性就是，只能在一端进行数据插入操作，在另一端进行数据删除操作，所以队列具有先进先出，后进后出的原则，就和排队一样

入队列：进行数据的插入操作的一端叫做队尾

出队列：进行数据的删除操作的一端叫做队头

队列和栈一样也可以用数组和链表两种方式来实现，当相比与数组，链表的结构更优一点，因为如果使用数组来实现的队列在数组头部出数据的效率比较低

队列的实现

队列的结构

使用链表来实现队列，则队列的结点结构和链表一样，但队列是队头出数据、队尾入数据，所以我们需要在定义一个队列的结构体，包含队列的队头和队尾以及队列中元素个数

如果对链表的建立有什么困惑的请移步

详述手打单链表，全是干货！！！-CSDN博客

typedef int QDataType;typedef struct QueueNode//队列结点结构体
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* qhead;//队头QueueNode* qtail;//队尾int size;//队列元素个数
}Queue;

队列的初始化

队列的初始化和链表类似，需要考虑的是队列的结构中有两个指针（队头和队尾），初始化需要将它们置空

void QueueInit(Queue* pq)//初始化
{assert(pq);pq->qhead = pq->qtail = NULL;//队头和队尾都指向空pq->size = 0;
}

队尾入队

队列的入队和链表尾插类似，都要考虑是否为空的情况，当队列为空的时候，队尾和队头是在一块的，非空的时候就需要将数据插在队尾后面，在队尾指针向后移，size加一

void QPushBack(Queue* pq, QDataType x)//队尾入队
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL;//当队列为空时if (pq->qhead==NULL){pq->qhead = pq->qtail = newnode;}else{pq->qtail->next = newnode;pq->qtail = pq->qtail->next;}pq->size++;
}

队头出队

队列的数据删除就和链表的头删类似，也要考虑是否只有一个结点，当只有一个结点就只需要将队头指针free掉，再将两个指针置空就行，正常情况下就需要将队头结点free掉，在将队头指针指向下一个结点，当然了，在输出前也是要判断队列是否为空，也就是看队头结点是否为空

//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->qhead == NULL;
}
//队头出队
void QPopFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(&pq));//qhead nextif (pq->qhead == pq->qtail)//当队列就只有一个结点时{free(pq->qhead);pq->qhead = pq->qtail = NULL;}else{QueueNode* next = pq->qhead->next;free(pq->qhead);pq->qhead = next;}pq->size--;
}

取队头数据

在取队头数据前要判断队列是否为空，不为空就直接返回队头指针指向的数据就行

//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(&pq));return pq->qhead->data;
}

取队尾数据

当然了，能取队头数据就能取队尾数和取队头数据类似

//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(&pq));return pq->qtail->data;
}

队列有效元素个数

在前面队列的结构就已经知道了，直接返回size就行了

//队列有效元素个数
int QueueSize(Queue* pq)
{return pq->size;
}

销毁队列

队列的销毁和链表类似，也是一个结点一个结点的free掉，最后将队头指针和队尾指针置空，size=0

//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->qhead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->qhead = pq->qtail = NULL;pq->size = 0;
}

就此我们也完成了队列的建立