DS |
您所在的位置：网站首页 › 循环队列的实验原理是 › DS |
DS
|
目录
1.栈
1.1栈的概念及结构
1.2栈的实现
2.队列
2.1队列的概念及结构
2.2队列的实现
2.3循环队列及其实现
1.栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈:栈的删除操作叫做出栈，出数据也在栈顶。 栈一般可以用数组或者链表来进行实现，由于栈只能在一端（栈顶）进行操作，那么如果使用数组相对来说就会更简单一些，因为在数组尾部插入和删除元素的代价较小。但使用数组会导致要么栈的容量是固定值，要么就会涉及到扩容的问题，扩容的代价本身较大以及一旦进行扩容就难以避免空间浪费的问题。从这方面考虑，用链表来实现栈也是一个不错的选择。 下面直接上代码： 顺序栈的实现 //stack.h #ifndef _STACT_H_ #define _STACT_H_ #include #include #include #include //顺序栈 #define STACK_DEFAULT_SIZE 8 //默认容量 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);//获取元素个数 void StackDestroy(Stack* ps);//摧毁栈 #endif /* _STACT_H_ */ / //stack.c #include "stack.h" void StackInit(Stack* ps) { assert(ps); ps->_capacity = STACK_DEFAULT_SIZE; ps->_a = (STDataType *)malloc(sizeof(STDataType)* ps->_capacity); ps->_top = 0; } static bool IncStack(Stack *ps, int new_cap) { assert(ps); assert(new_cap > ps->_capacity); STDataType *new_a = (STDataType *)realloc(ps->_a, sizeof(STDataType)* new_cap); if (new_a == NULL){ return false; //扩容失败 } ps->_a = new_a; ps->_capacity = new_cap; printf("链表已成功扩容!\n"); return true; //扩容成功 } static bool IsFull(Stack *ps) |
【本文地址】
今日新闻 |
推荐新闻 |