做网站通常用的软件,网站建设推广谷得网络,wordpress页面导航条,电子商务网站开发前言引言
在对顺序表#xff0c;链表有了充分的理解之后#xff0c;现在让我们学习栈和队列#xff01;#xff01;#xff01; 【链表】 #x1f448;链表 【顺序表】#x1f448;顺序表 目录
#x1f4af;栈
1.栈的概念及结构
2.栈的实现
⭐初始化栈
⭐入栈
⭐…引言
在对顺序表链表有了充分的理解之后现在让我们学习栈和队列 【链表】 链表 【顺序表】顺序表 目录
栈
1.栈的概念及结构
2.栈的实现
⭐初始化栈
⭐入栈
⭐出栈
⭐获取栈顶元素
⭐获取栈中有效元素个数
⭐检测栈是否为空
⭐销毁栈
✨实现结果
队列
1.队列的概念及结构
2.列队的实现
⭐初始化列队
⭐队尾入列队
⭐队尾出列队
⭐获取队列头部元素
⭐获取队列中有效元素个数
⭐检测队列是否为空
⭐销毁列队
✨实现结果 栈
1.栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。 先进后出 Last In First Out 让我们思考下面2道题目加深对栈的理解 2.栈的实现 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 // 下面是定长的静态栈的结构实际中一般不实用所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;// 初始化栈
void StackInit(Stack* ps);// 入栈
void StackPush(Stack* ps, STDataType data);// 出栈
void StackPop(Stack* ps);// 获取栈顶元素
STDataType StackTop(Stack* ps);// 获取栈中有效元素个数
int StackSize(Stack* ps);// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps);// 销毁栈
void StackDestroy(Stack* ps);
⭐初始化栈
typedef int STDateType;
typedef struct Stack
{STDateType* a;int top;int capacity;
}ST;
⭐入栈
void StackPush(ST* p, STDateType x)
{if (p-top p-capacity){STDateType* temp (STDateType*)realloc(p-a, p-capacity * 2*sizeof(STDateType));if (tempNULL){printf(realloc fail\n);exit(-1);}else{p-capacity * 2;p-a temp;}}p-a[p-top] x;p-top;
}
⭐出栈
void StackPoP(ST* p)
{assert(p);assert(p-top0);p-top--;
}
⭐获取栈顶元素
STDateType StackTop(ST* p)
{assert(p);assert(p-top 0);return p-a[p-top - 1];
}
⭐获取栈中有效元素个数
int Size(ST* p)
{return p-top;
}
⭐检测栈是否为空 如果为空返回非零结果如果不为空返回0
bool StackEmpty(ST* p)
{return p-top 0;
}
⭐销毁栈
void StackDestory(ST* p)
{assert(p);free(p-a);p-a NULL;p-capacity p-top 0;
}
✨实现结果
int main()
{ST p;StackInit(p);StackPush(p, 1);StackPush(p, 2);StackPush(p, 3);StackPush(p, 4);StackPush(p, 5);StackPush(p, 6);while (!StackEmpty(p)){printf(%d , StackTop(p));StackPoP(p);}StackDestory(p);return 0;
} 队列
1.队列的概念及结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头 2.列队的实现 队列的实现方式包括数组和链表。常见的队列实现方式有: 数组实现:使用一维数组存储元素通过头指针和尾指针分别指向队头和队尾实现入队和出队操作。链表实现:每个元素使用一个节点存储通过指针链接实现队列入队操作在链表末尾插入新节点出队操作删除链表头节点。 从head端删除元素从tail端插入元素 队列也可以数组和链表的结构实现使用链表的结构实现更优一些。因为如果使用数组的结构出队列在数组头上出数据效率会比较低。需要将后面的元素集体前移 // 链式结构表示队列
typedef struct QListNode
{struct QListNode* _pNext;QDataType _data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* _front;QNode* _rear;
}Queue;// 初始化队列
void QueueInit(Queue* q);// 队尾入队列
void QueuePush(Queue* q, QDataType data);// 队头出队列
void QueuePop(Queue* q);// 获取队列头部元素
QDataType QueueFront(Queue* q);// 获取队列中有效元素个数
int QueueSize(Queue* q);// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q);// 销毁队列
void QueueDestroy(Queue* q);
⭐初始化列队
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
⭐队尾入列队
void QueuePush(Queue* pq, QDatatype x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-data x;newnode-next NULL;if (pq-head NULL){assert(pq-tail NULL);pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}
⭐队尾出列队
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head ! NULL);if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}
⭐获取队列头部元素
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}
⭐获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}⭐检测队列是否为空 如果为空返回非零结果如果不为空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
⭐销毁列队
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}
✨实现结果
int main()
{Queue p;QueueInit(p);QueuePush(p, 1);QueuePush(p, 2);QueuePush(p, 3);QueuePush(p, 4);QueuePush(p, 5);while (!QueueEmpty(p)){printf(%d ,QueueFront( p));QueuePop(p);}QueueDestory(p);return 0;
} 以上就是本文章的全部内容啦~
感谢你看到最后点个赞再走吧
非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。✨✨ 欢迎订阅本专栏 ✨✨
