天津网站制作网页,营销网站制作免费咨询,逆冬黑帽seo培训,网站的总体结构文章目录 1.栈介绍2. 哪种结构实现栈会更优#xff1f;3.栈代码实现#xff08;C语言#xff09; 往期相关文章#xff1a;
线性表之顺序表线性表之链表
1.栈介绍 栈是一种特殊的线性表#xff0c;只允许在栈顶#xff08;Top#xff09;进行插入和删除元素操作#… 文章目录 1.栈介绍2. 哪种结构实现栈会更优3.栈代码实现C语言 往期相关文章
线性表之顺序表线性表之链表
1.栈介绍 栈是一种特殊的线性表只允许在栈顶Top进行插入和删除元素操作另一端称为栈底栈中的数据元素遵守后进先出LIFOLast In First Out或 先进后出的原则。
栈的插入操作Push称为压栈 或 入栈 或 进栈。栈的删除操作Pop也叫出栈 或 弹栈。 栈顶top也可以是最后一次进栈的数据位置比如上图中栈顶可以分别是100、200、300的位置这取决于栈顶初始化成 0 还是 -1。如果栈顶最开始初始化为0则栈顶是如上图所演示的位置因为是先Push然后再栈底top如果栈顶初始化为-1则栈顶是最后一次进栈的数据下标位置因为是先top然后再Push。
2. 哪种结构实现栈会更优 栈的实现一般可以使用数组或链表实现。对栈而言数组的结构实现更优一些因为数组在尾上插入和删除数据的代价很小时间复杂度均为O(1)且没有其它额外开销。下面具体分析两种结构实现栈的优缺点。
对于链表实现栈问题很多。一是链表有八种二是每种链表实现起来都存在缺点。下面简单分析下链表实现栈的问题 先说单向链表实现栈即便是多维护一个尾指针对于栈的删除操作还是需要遍历因为需要找到尾节点的上一个节点。 而对于双向链表为了解决单向链表实现栈的删除操作问题唯一可行的只有双向循环链表不仅轻松地找到尾结点同时还能找到上一个节点确实能解决上面谈到的问题。不过这又有其它问题了每个节点相比于单向链表都多维护了一个指针变量有一定内存开销。
所以说实现栈的最优结构还得是数组且数组自身的特性也产生了几个优点。数组的存储是连续的正是因为这个原因
数组的寄存器命中率比链表高寄存器命中后不会产生寄存器空间污染。
数组实现栈的话就没有任何缺点吗答案是有的前面也说过栈是一种特殊的线性表。
空间给大了或每次扩容扩大了然后又不使用那空间就浪费了4空间给小了或者每次扩容扩小了那插入数据时容量不够经常需要扩容realloc扩容本身也有一些消耗最不能接受的是如果后面的内存不足以扩容设定的大小realloc扩容可能会异地扩容内存碎片增多异地扩容意思是跳过这段大小不够的内存空间到另一片内存区域扩容这也会导致跳过的那一段内存变成内存碎片如果一直没有程序去使用空间也浪费掉了关于realloc扩容可以看看我的这篇文章 指针与动态内存 2.3realloc部分。
不过上述数组的缺点也是能控制的。比如数组初始化大小根据需求给一个折中扩容方案也折中比如按自身1.5倍扩这样能控制扩容的频率不至于太频繁异地扩容的几率也小一些优点相比于缺点利大于弊最重要的是比起链表的优缺点也要好上许多
3.栈代码实现C语言
stack.h
#pragma once#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int valuetype;typedef struct {valuetype* arr;int top;int capacity;
} Stack;void Init(Stack* stack);void Push(Stack* stack, valuetype value);
void Pop(Stack* stack);valuetype Top(Stack* stack);
int Size(Stack* stack);
bool Empty(Stack* stack);void Destroy(Stack* stack);stack.c
#define _CRT_SECURE_NO_WARNINGS 1#include Stack.hvoid Init(Stack* stack) {assert(stack);stack-arr NULL;stack-capacity stack-top 0;
}void Push(Stack* stack, valuetype value) {assert(stack);if (stack-top stack-capacity) {stack-capacity stack-capacity 0 ? 10 : (int)(stack-capacity * 1.5);stack-arr (valuetype*)realloc(stack-arr, sizeof(valuetype) * stack-capacity);if (stack-arr NULL) {perror(realloc failed in the function Push(Stack*, valuetype).);return;}}stack-arr[stack-top] value;
}void Pop(Stack* stack) {assert(stack stack-top 0);stack-top--;
}valuetype Top(Stack* stack) {assert(stack stack-top 0);return stack-arr[stack-top - 1];
}int Size(Stack* stack) {assert(stack);return stack-top;
}bool Empty(Stack* stack) {assert(stack);return stack-top 0;
}void Destroy(Stack* stack) {assert(stack);free(stack-arr);stack-arr NULL;stack-capacity stack-top 0;
}
