c语言|栈和队列c语言实现详解 c语言|开发语言

栈的实现及理论概念

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端又称为栈顶。对栈的基本操作为进栈(Push)和出栈(Pop)，其执行策略为LIFO(后进先出2)，如下 【c语言|栈和队列c语言实现详解】
文章图片

首先我们来创建一个结构体栈，这里采用数组形式，因数组本身就为一段连续的空间，直接通过下标更加便于访问，代码如下
typedef int SDATE; //数据如此定义便于更改 typedef struct Stack { SDATE* data; int top; //栈顶 int capacity; //容量 }stack;

这里我们创建的是动态栈，首先我应当对数据进行初始
void InitStack(stack* pst) { assert(pst); //初始化数组大小 pst->data = https://www.it610.com/article/(SDATA*)malloc(4 * sizeof(SDATA)); if (data == NULL) { printf("malloc fail\n"); exit(-1); } else { pst->capacity = 4; pst->top = 0; //这里栈顶设置为0 } }

之后我们就来实现栈的插入，代码如下
void PushStack(stack* pst, SDATA x) { assert(pst); if (pst->capacity == pst->top)//判断是否空间足够，不够则扩容 { SDATA* exceed = (SDATA*)realloc(pst->data, 2*pst->capacity * sizeof(SDATA)); if (exceed == NULL) { printf("realloc fail"); exit(-1); } else { pst->data = https://www.it610.com/article/exceed; pst->capacity *= 2; } } pst->data[pst->top] = x; pst->top++; }

往后我们来依次实现Pop的其它接口，代码如下
void PopStack(stack* pst)//出栈 { assert(pst); assert(pst->top > 0); pst->top--; } bool StackEmpty(stack* pst)//判断是否有数据 { assert(pst); return pst->top == 0; } SDATA StackTop(stack* pst)//栈顶元素取出 { assert(pst); assert(pst->top > 0); return pst->data[pst->top - 1]; } int StackSize(stack* pst)//查看数据量 { assert(pst); return pst->top; } void DestroyStack(stack* pst)//销毁动态开辟空间 { assert(pst); free(pst->data); pst->data = https://www.it610.com/article/NULL; pst->top = 0; pst->capacity = 0; }

#pragma once #include #include #include #include typedef int SDATA; typedef struct Stack { SDATA* data; int top; int capacity; }stack; void InitStack(stack* pst); void PushStack(stack* pst, SDATA x); void PopStack(stack* pst); bool StackEmpty(stack* pst); SDATA StackTop(stack* pst); int StackSize(stack* pst); void DestroyStack(stack* pst);

以上便是栈的实现

接下来是队列的概念及实现

队列与栈一样是表，不同的是其插入在一端进行删除在另一端进行

队列的基本操作:Enqueue(入队)其在表的末端(称作队尾(rear)插入一个元素)，还有出队(Dequeun)其位于队列开头也称对头(front)，采用先进先出方式进行
文章图片

这里我们采用链表的方式实现，首先依旧是建个结构体链表
typedef int SDATA; typedef struct Queue//节点 { struct Queue* next; SDATA data; }Qnode; typedef struct Chmpas//队头、队位 { Qnode* front; Qnode* rear; }queue;

按照定义便建好了队列逻辑方式，下面便是实现其各个接口，以下变为几个基本接口
void InitQueue(queue* pt); //初始化 void PushQueue(queue* pt, SDATA x); //入队 void PopQueue(queue* pt); //出队 SDATA FrontData(queue* pt); //头部数据 SDATA RearData(queue* pt); //尾部数据 void DestroyQueue(queue* pt); //释放空间 int QueueSize(queue* pt); //队列数据

首先依旧是初始化，其次便是入队，代码如下
void InitQueue(queue* pt) { assert(pt); pt->front = pt->rear = NULL; } void PushQueue(queue* pt, SDATA x) { assert(pt); Qnode* newnode = (Qnode*)malloc(sizeof(Qnode)); //开辟节点 if(newnode == NULL) { printf("malloc fail\n"); return; } newnode->data = https://www.it610.com/article/x; newnode->next = NULL; if (pt->front == NULL) { pt->front = pt->rear = newnode; } else { pt->rear->next = newnode; Qnode* tp = pt->rear->next; pt->rear = tp; } }

接下来便是实现剩下的几个接口，代码如下
void PopQueue(queue* pt)//出队 { assert(pt); if (pt->front->next == NULL)//单个节点情况 { free(pt->front); pt->front = pt->rear = NULL; } Qnode* next = pt->front->next; //先临时保存再释放 free(pt->front); pt->front = next; } SDATA FrontData(queue* pt)//头部数据 { assert(pt); assert(pt->front); return pt->front->data; } SDATA RearData(queue* pt)//尾部数据 { assert(pt); assert(pt->rear); return pt->rear->data; } void DestroyQueue(queue* pt)//释放 { assert(pt); Qnode* cur = pt->front->next; while (cur) { Qnode* next = cur->next; free(cur); cur = next; } pt->front = pt->rear = NULL; } int QueueSize(queue* pt)//计算个数 { assert(pt); int count = 0; Qnode* cur = pt->front; //依旧采用循环方式 while (cur) { cur = cur->next; cur++; } return count; } bool QueueEmpty(queue* pt)//布尔判断 { assert(pt); return pt->front == NULL; }