企业策划 企业网站建设 品牌设计,自定义字段wordpress,必应搜索推广,哪里有seo排名优化本章重点 栈的概念及结构 栈的实现方式 数组实现栈接口 栈面试题目 概念选择题 一、栈的概念及结构 栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶#xff0c;另一端称为栈底。栈中的数…本章重点 栈的概念及结构 栈的实现方式 数组实现栈接口 栈面试题目 概念选择题 一、栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 栈顶Top线性表允许插入和删除的那一端。栈底Bottom固定的不允许进行插入和删除的另一端。空栈不含任何元素的空表。 二、栈的实现方式 由于栈只能在栈顶操作所以栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。单链表的尾插需要遍历结点这里使用带头双向循环链表也可但是空间销毁大。单链表也可以实现我们就需要让栈顶是头结点栈底是尾结点这样入栈就是头插效率高。
1.顺序堆栈 根据前边的分析可知顺序堆栈和顺序表的数据成员元素是相同的不同之处是顺序堆栈的入栈和出栈操作只能对当前栈顶元素进行。 顺序堆栈的存储结构如图3-2所示。其中a0a1,a2表示顺序堆栈要存储的元素序列stack 表示顺序堆栈存放元素的数组capacity 表示顺序堆栈数组stack的内存单元容量表示目前允许存储的元素最大个数)top表示顺序堆栈数组stack的当前栈顶位置。
2.链式堆栈 堆栈有两端插入元素和删除元素的一端为栈顶另一端为栈底。对链式堆栈来说显然,若把靠近头指针的一端定义为栈顶则插入元素和删除元素时不需要遍历整个链其时间复杂度为0(1若把远离头指针的一端定义为栈顶则每次插入元素和删除元素时都需要遍历整个链其时间复杂度为0(n。因此链式堆栈都设计成把靠近头指针的一端定义为栈顶。链式堆栈的头结点对操作实现的影响不大因此可有可无。依次向带头结点链式堆栈输入a0a1,a2…….an-1后带头结点链式堆栈的结构示意图如图3-3所示。
三、数组实现栈接口
// 下面是定长的静态栈的结构实际中一般不实用所以我们主要实现下面的支持动态增长的栈
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如果不为空返回非零结果
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);1.初始化栈void StackInit(Stack* ps)
初始化这里我们先不设置容量后续入栈再申请空间即可这里需要注意top的值我们设置的值是0它是表示非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-top 0;//表示栈顶元素的下一个位置ps-capacity 0;
} 2.入栈void StackPush(Stack* ps, STDataType data)
满栈当我们使一个元素入栈的之前我们往往需要判断一下栈是否为满栈防止发生上溢的情况。因为我们定义了一个capacity来表示当前已经分配的存储空间所以我们可以用ps-top ps-capacity 来判断当前使用的栈空间是否满了。所以当ps-top ps-capacity时表示已经满了。
满栈我们要首先追加存储空间然后才能将元素入栈。realloc()函数可以申请空间如果realloc第一个参数为空那么realloc的功能就类似于malloc这也是为什么我们前面初始化没有开辟空间的原因写在这里能省大量的代码。
// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps-top ps-capacity){int newCapacity (ps-capacity 0) ? 4 : ps-capacity * 2;//如果ps-a NULL功能相当与mallocSTDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] data;ps-top;
}
3.出栈void StackPop(Stack* ps)
出栈时我们首先要判断栈是否为空栈由于是顺序栈我们只需要判断ps-top 0即可判断当前栈的情况。
// 出栈
void StackPop(Stack* ps)
{assert(ps);//保证不为空assert(ps-top 0);ps-top--;
}
4.获取栈顶元素STDataType StackTop(Stack* ps)
取栈顶元素同样需要判断是否为空栈空栈也不能取出任何数据所以这里强制断言一旦为空栈直接程序报错
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);//保证不为空assert(ps-top 0);return ps-a[ps-top - 1];
}
5.获取栈中有效元素个数int StackSize(Stack* ps)
由于top是非空栈中的栈顶指针始终在栈顶元素的下一个位置上所以top就是当前栈中有效元素个数
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;
}
6.检测栈是否为空如果为空返回0如果不为空返回非零结果int StackEmpty(Stack* ps)
// 检测栈是否为空如果为空返回0如果不为空返回非零结果
int StackEmpty(Stack* ps)
{if (ps-top ! 0)return ps-top;elsereturn 0;
}
7.销毁栈void StackDestroy(Stack* ps)
销毁栈只需将申请的空间释放再把设置的大小和容量设施为0即可。
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}四、栈面试题目
括号匹配问题。OJ链接 当开始接触题目时我们会不禁想到如果计算出左括号的数量和右括号的数量如果每种括号左右数量相同会不会就是有效的括号了呢 事实上不是的假如输入是 [ { ] }每种括号的左右数量分别相等但不是有效的括号。这是因为结果还与括号的位置有关。 仔细分析我们发现对于有效的括号它的部分子表达式仍然是有效的括号比如 { ( )[ ) ] } 是一个有效的括号( )[ { } ] 是有效的括号[ ( ) ] 也是有效的括号。并且当我们每次删除一个最小的括号对时我们会逐渐将括号删除完。比如下面的例子。 这个思考的过程其实就是栈的实现过程。因此我们考虑使用栈当遇到匹配的最小括号对时我们将这对括号从栈中删除即出栈如果最后栈为空那么它是有效的括号反之不是。 bool isValid(char* s)
{Stack st;StackInit(st);char topVal;while (*s){switch (*s){case(:case[:case{:StackPush(st, *s);break;case):case]:case}://数量不匹配if (!StackEmpty(st))//栈为空{StackDestroy(st);//防止内存泄露return false;}topVal StackTop(st);StackPop(st);//顺序不匹配if (*s ) topVal ! ( || *s ] topVal ! [|| *s } topVal ! }){StackDestroy(st);//防止内存泄露return false;}break; }s;}//栈不为空此时只有右括号false说明数量不匹配int ret StackEmpty(st);StackDestroy(st);if (ret 0)return false;elsereturn true;
}
五、概念选择题 1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈然后再依次出栈则元素出栈的顺序是 。 A 、12345ABCDEB 、EDCBA54321C 、ABCDE12345D 、54321EDCBA 元素出栈的顺序遵循后进先出Last-In-First-OutLIFO原则因此选择B 2.若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是 A 1,4,3,2B 2,3,4,1C 3,1,4,2D 3,4,2,1 A1入栈后出栈234入栈4出栈3出栈2出栈可能。 B12入栈2出栈3入栈3出栈4入栈4出栈1出栈可能。 C123入栈3出栈接下来应该是2出栈或者4入栈不可能1出栈不可能。 D123入栈3出栈4入栈4出栈2出栈1出栈可能。 本章结束啦
