C语言|C语言浅谈栈与队列的定义与操作 C语言浅谈栈与队列的定义与操

栈的定义
栈的实现

前置
初始化栈
栈的销毁
栈的插入
出栈的操作
取栈顶元素
栈的大小

队列的定义

队列的基本操作

队列的初始化
队列的销毁
队列的插入
队列的删除
队列的判空
取出队头元素
取出队尾元素
队列的大小

栈的定义栈同样是一种线性表，它的特性是插入元素必须从后面插入，删除元素也是从后面删除，进行数据删除和插入的一端称为栈顶，另一端是栈底。
压栈—就是插入元素
出栈—就是删除元素
它可以用数组实现也可以用链表实现

文章图片

但是用数组实现更好，因为链表的插入和删除要进行遍历，而数组可以进行随机访问，从而时间复杂度更低。

栈的实现
前置
【C语言|C语言浅谈栈与队列的定义与操作】栈的元素需要表明容量，还有栈顶

typedef int SDType; typedef struct Srack{ SDType* a; int top; int capacity; }ST;

初始化栈
把元素置为空，栈顶在下标为0的位置

void StackInit(ST* ps){ assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; }

栈的销毁
不再赘述

void StackDestrory(ST* ps){ assert(ps); free(ps); ps=NULL; ps->capacity = ps->top = 0; }

栈的插入
先判空，如果容量满了，进行增容，把栈顶元素进行赋值，再把栈顶指针加一

void StackPush(ST* ps, SDType x){ assert(ps); if (ps->top == ps->capacity) {int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SDType* tmp = (SDType)realloc(ps->capacity, sizeof(SDType) * newCapacity); if (tmp == NULL){printf("Realloc fail!\n"); }else{ps->a = tmp; ps->capacity = newCapacity; } } ps->a[ps->top] = x; ps->top++; }

出栈的操作
栈顶指针减一即可

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

取栈顶元素
先进行判空，不空的话直接取出栈顶指针指向的元素

SDType StackTop(ST* ps){ assert(ps); assert(!StackEmpty(ps)); return ps -> a[ps->top - 1]; }

栈的大小

int StackSize(ST* ps){ assert(ps); return ps->top; }

判断栈是否为空

bool StackEmpty(ST* ps){ return ps->top == 0; }

队列的定义队列只允许在一段进行插入操作，一段进行删除操作，在队尾进行插入，在队头进行删除

文章图片

队列的基本操作
队列的初始化
我们在进行基本操作的时候要用到头指针和尾指针

void QueueInit(Queue* pq){ assert(pq != NULL); pq->head = NULL; pq->tail = NULL; }

队列的销毁
将临时指针cur被赋值为head，保存下一个，遍历进行删除，最后把头指针和尾指针进行free

void QueueDestroy(Queue* pq){ assert(pq != NULL); QueueNode* cur = pq->head; QueueNode* next = cur->next; while (cur) {free(cur); cur = next; next = next->next; } pq->head = pq->tail = NULL; }

队列的插入
队列只能从队尾查，如果开始的时候队头和队尾重合，那就直接进行插入，
如果不，那就找到尾，在尾后边进行插入

void QueuePush(Queue* pq,QDataType x){ assert(pq); QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); newNode->data = https://www.it610.com/article/x; newNode->next = NULL; if (pq->head == NULL) {pq->head = pq->tail = newNode; } else {pq->tail->next = newNode; pq->tail = newNode; }}

队列的删除
很简单，删除队尾头元素，先保存下一个，再把队头复制给新的

void QueuePop(Queue* pq){ assert(pq); assert(!QueueEmpty(pq)); QueueNode* NewHead = pq->head->next; free(pq->head); pq->head = NewHead; if (pq->head == NULL) {pq->tail = NULL; }}

队列的判空
是否队头指向空