买机票便宜的网站建设,深圳定制旗袍实体店,建设银行深分行圳招聘网站,建设壁纸网站的目的系列文章目录 文章目录系列文章目录前言一、栈二、栈的实现三、接口函数的实现1、初始化2、销毁栈3、压栈与出栈4、判空5、元素个数6、返回栈顶元素四、栈中元素的访问总结前言
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。 一、…系列文章目录 文章目录系列文章目录前言一、栈二、栈的实现三、接口函数的实现1、初始化2、销毁栈3、压栈与出栈4、判空5、元素个数6、返回栈顶元素四、栈中元素的访问总结前言
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。 一、栈 栈的结构如上图所示像一个桶元素是在竖直放入的。
栈只允许在固定的一端进行插入和删除元素操作进行数据插入和删除操作的一端称为栈顶另一端称为栈底即元素遵循后进先出的原则但注意这个是相对于栈内的元素。
二、栈的实现 我们可以用数组或链表的结构来实现栈但栈这种数据结构是不存在随即插入这种方式的因为它只能尾插。 我们以链表的方式来模拟的时候我们需要不断地找尾这个过程的时间复杂度是O(N)。所以我们是用数组可以更好的来实现栈的结构。
typedef struct Stack
{STDataType* a;int capacity;int top;
}ST;三、接口函数的实现
1、初始化
void StackInit(ST* ps)
{assert(ps);ps-capacity 4;ps-a (STDataType*)malloc(sizeof(STDataType)*(ps-capacity));assert(ps-a);ps-top 0;//栈顶元素的下一位置下标 top 0/ 栈顶元素 top -1
}默认开辟四个元素大小空间将top设为0capacity设置为4。
2、销毁栈
void StackDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;}3、压栈与出栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//扩容if (ps-top ps-capacity){ps-a (STDataType*)realloc(ps-a, sizeof(STDataType) * ps-capacity * 2);ps-capacity * 2;assert(ps-a);}ps-a[ps-top] x;ps-top;
}void StackPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}压栈是尾部插入元素所以要注意可能要扩容。 当一个栈为空的时候恰好就是top为0的时候。
4、判空
bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}当一个栈为空的时候恰好就是top为0的时候因此我们可以通过top来判断栈是否为空。
5、元素个数
int StackSize(ST* ps)
{assert(ps);return ps-top;
}
6、返回栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}四、栈中元素的访问
栈是无法像顺序表和链表那样不断地遍历元素的。因为想要遍历元素必须取出栈顶元素也就是说我们必须删除栈顶的元素才能访问到下一个元素。因此栈只能遍历一次遍历一次之后就代表着栈已经空了。 总结
栈的特点就是后进先出。 任何问题都有解决的办法无法可想的事是没有的。——爱迪生
