江阴外贸网站建设公司,沈阳网站公司排名,网站怎么做的有创意,wordpress 免费主题【数据结构】栈和队列 一#xff1a; 栈1.栈的概念及和结构2. 栈的实用3. 栈接口实现 二#xff1a; 队列1. 队列的概念和结构2. 队列的实用3. 队列接口实现 三#xff1a;扩展 一#xff1a; 栈
1.栈的概念及和结构
栈#xff1a;一种特殊的线性表#xff0c;其只允许… 【数据结构】栈和队列 一 栈1.栈的概念及和结构2. 栈的实用3. 栈接口实现 二 队列1. 队列的概念和结构2. 队列的实用3. 队列接口实现 三扩展 一 栈
1.栈的概念及和结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 2. 栈的实用 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 3. 栈接口实现
Stach.h:
// 下面是定长的静态栈的结构实际中一般不实用所以我们主要实现下面的支持动态增长的栈
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 StInit(Stack* ps);
// 入栈
void StPush(Stack* ps, STDataType data);
// 出栈
void StPop(Stack* ps);
// 获取栈顶元素
STDataType StTop(Stack* ps);
// 获取栈中有效元素个数
int StSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StEmpty(Stack* ps);
// 销毁栈
void StDestroy(Stack* ps)Stack.c:
#include Stack.hvoid STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;//top指向栈顶元素的下一个位置
}void STDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}void STPush(ST* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDateType* tmp (STDateType*)realloc(ps-a,sizeof(STDateType) * newCapacity);if (tmp NULL){perror(malloc fail);exit(-1);}//创建成功ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}STDateType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}二 队列
1. 队列的概念和结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)的原则。 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头
2. 队列的实用
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
3. 队列接口实现
Queue.h:
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//为了解决传二级指针的问题有两种方法
//第一种是传哨兵位另一种就是如下在封装一个结构体
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;// 初始化队列
void QueueInit(Que* pq);
// 队尾入队列
void QueuePush(Que* pq, QDataType x);
// 队头出队列
void QueuePop(Que* pq);
// 获取队列头部元素
QDataType QueueFront(Que* pq);
// 获取队列队尾元素
QDataType QueueBack(Que* pq);
// 获取队列中有效元素个数
int QueueSize(Que* pq);
// 检测队列是否为空如果为空返回1如果非空返回0
bool QueueEmpty(Que* pq);
// 销毁队列
void QueueDestroy(Que* pq);Queue.c:
#include Stack.hvoid STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;//top指向栈顶元素的下一个位置
}void STDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}void STPush(ST* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDateType* tmp (STDateType*)realloc(ps-a,sizeof(STDateType) * newCapacity);if (tmp NULL){perror(malloc fail);exit(-1);}//创建成功ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}STDateType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}三扩展
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现也可以使用循环链表实现。
