当前位置: 首页 > 最新文章 > 正文

二级根据top栈的元素个数(栈top=bottom栈中元素)

就这样,过起了"起早贪黑"的有车生活。进出的一端称为栈顶,另一端称为栈底。我们先看顺序存储方式: 从上图可以看出,需要两个指针,base指向栈底,top指向栈顶。不按套路出牌啊~~~下面讲解顺序栈的初始化、入栈,出栈,取栈顶元素等操作。栈顶元素所在的位置实际上是S.top-1,因此把该元素取出来,暂存在变量e中,然后S.top指针向下移动一个位置。例如4出队后:注意:因为顺序存储删除一个元素时,并

admin

就这样,过起了"起早贪黑"的有车生活。进出的一端称为栈顶,另一端称为栈底。我们先看顺序存储方式: 从上图可以看出,需要两个指针,base指向栈底,top指向栈顶。不按套路出牌啊~~~下面讲解顺序栈的初始化、入栈,出栈,取栈顶元素等操作。栈顶元素所在的位置实际上是S.top-1,因此把该元素取出来,暂存在变量e中,然后S.top指针向下移动一个位置。例如4出队后:注意:因为顺序存储删除一个元素时,并没有销毁该空间,所以4其实还在那个位置,只不过下次再有元素进栈时,就把它覆盖了。相当于该元素已出栈,因为栈的内容是S.base 到S.top-1。int GetTop //返回S的栈顶元素,栈顶指针不变{ if (S.top !

小张终于攒钱买了车,可是他家住在胡同的尽头,胡同很窄,只能通过一辆车,而且是死胡同,每天小张都为停车发愁,回家早了停在里面,早上上班就要让所有的人挪车,先让胡同口那辆出去,然后挨着一辆一辆出去,小张才能去上班。没办法,小张下班也不敢早回家了,等天黑了别的车都停进去了,再回去把车停在胡同口,这样早上就可以第一个去上班了。就这样,过起了"起早贪黑"的有车生活。

数据结构 第5讲 栈

我们看到这个胡同很窄,只能通过一辆车,而且是死胡同,只能从胡同口进出,画图:

数据结构 第5讲 栈

小汽车是线性排列,而且只能从一端进出,后进的汽车先出去,这就是"栈",栈也是一种线性表,只不过它是操作受限的线性表,只能在一端操作,后进先出(Last In First Out,LIFO)。

进出的一端称为栈顶(top),另一端称为栈底(base)。栈可以用顺序存储,也可以用链式存储。我们先看顺序存储方式:

数据结构 第5讲 栈

从上图可以看出,需要两个指针,base指向栈底,top指向栈顶。

顺序栈的结构体定义:

数据结构 第5讲 栈

栈定义好了之后,还要先定义个最大的分配空间,顺序结构都是如此,需要预先分配空间,因此可以采用宏定义:

#define Maxsize 100 //预先分配空间,这个数值根据实际需要预估确定;

注意:栈只能在一端操作,后进先出,是人为规定的,也就是说不允许在中间查找、取值、插入、删除等操作,但顺序栈本身是顺序存储的,有人就想我非要从中间取一个元素,那肯定可以取出来,没有问题,但是这样做,就不是栈了。不按套路出牌啊~~~

下面讲解顺序栈的初始化、入栈,出栈,取栈顶元素等操作(元素以int类型为例)。

1. 顺序栈初始化

初始化一个空栈:

数据结构 第5讲 栈

[cpp] view plain copy

  1. <span style="font-family:'Times New Roman';font-size:18px;">bool InitStack(SqStack &S) //构造一个空栈S

  2. {

  3. S.base = newint[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间

  4. if (!S.base) //空间分配失败

  5. returnfalse;

  6. S.top=S.base; //top初始为base,空栈

  7. returntrue;

  8. }</span>

2. 入栈

入栈前要判断是否栈满,如果栈已满,则入栈失败,否则将元素放入栈顶,栈顶指针向上移动一个空间(top++)。

  • 例如输入1,入栈:

数据结构 第5讲 栈

  • 接着输入2,入栈:

数据结构 第5讲 栈

bool Push(SqStack &S, int e) // 插入元素e为新的栈顶元素

{

if (S.top-S.base == Maxsize) //栈满

return false;

*(S.top++) = e; //元素e压入栈顶,然后栈顶指针加1,等价于*S.top=e; S.top++;

return true;

}

3. 出栈

出栈前要判断是否栈空,如果栈是空的,则出栈失败,否则将栈顶元素暂存给一个变量,栈顶指针向下移动一个空间(top--)。

数据结构 第5讲 栈

栈顶元素所在的位置实际上是S.top-1,因此把该元素取出来,暂存在变量e中,然后S.top指针向下移动一个位置。既然这样干脆先移动,即--S.top,然后再取元素就可以了。

例如4出队后:

数据结构 第5讲 栈

注意:因为顺序存储删除一个元素时,并没有销毁该空间,所以4其实还在那个位置,只不过下次再有元素进栈时,就把它覆盖了。相当于该元素已出栈,因为栈的内容是S.base 到S.top-1。

bool Pop(SqStack &S, int &e) //删除S的栈顶元素,暂存在变量e中

{

if (S.base == S.top) //栈空

return false;

e = *(--S.top); //栈顶指针减1,将栈顶元素赋给e

return true;

}

4. 取栈顶元素

取栈顶元素和出栈不同,取栈顶元素只是把栈顶元素复制一份,而出栈是指栈内不再包含这个元素。

例如取栈顶元素*(S.top-1),即元素4,取值后S.top的值没有改变,栈内元素的个数也没有改变。

数据结构 第5讲 栈

int GetTop(SqStack S) //返回S的栈顶元素,栈顶指针不变

{

if (S.top != S.base) //栈非空

return *(S.top - 1); //返回栈顶元素的值,栈顶指针不变

else

return -1;

}

顺序栈基本操作完整代码:

完整代码:

[cpp] view plain copy

  1. #include<iostream>

  2. usingnamespace std;

  3. #define Maxsize 100 //预先分配空间,这个数值根据实际需要预估确定;

  4. typedefstruct SqStack {

  5. int *base; //栈底指针

  6. int *top; //栈顶指针

  7. }SqStack;

  8. bool InitStack(SqStack &S) //构造一个空栈S

  9. {

  10. S.base = newint[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间

  11. if (!S.base) //空间分配失败

  12. returnfalse;

  13. S.top=S.base; //top初始为base,空栈

  14. returntrue;

  15. }

  16. bool Push(SqStack &S, int e) // 插入元素e为新的栈顶元素

  17. {

  18. if (S.top-S.base == Maxsize) //栈满

  19. returnfalse;

  20. *(S.top++) = e; //元素e压入栈顶,然后栈顶指针加1,等价于*S.top=e; S.top++;

  21. returntrue;

  22. }

  23. bool Pop(SqStack &S, int &e) //删除S的栈顶元素,暂存在变量e中

  24. {

  25. if (S.base == S.top) //栈空

  26. returnfalse;

  27. e = *(--S.top); //栈顶指针减1,将栈顶元素赋给e

  28. returntrue;

  29. }

  30. int GetTop(SqStack S) //返回S的栈顶元素,栈顶指针不变

  31. {

  32. if (S.top != S.base) //栈非空

  33. return *(S.top - 1); //返回栈顶元素的值,栈顶指针不变

  34. else

  35. return -1;

  36. }

  37. int main()

  38. {

  39. int n,x;

  40. SqStack S;

  41. InitStack(S);//初始化一个顺序栈S

  42. cout <<"请输入元素个数n:" <<endl;

  43. cin>>n;

  44. cout <<"请依次输入n个元素,依次入栈:" <<endl;

  45. while(n--)

  46. {

  47. cin>>x; //输入元素

  48. Push(S, x);

  49. }

  50. cout <<"元素依次出栈:" <<endl;

  51. while(S.top!=S.base)//如果栈不空,则依次出栈

  52. {

  53. cout<<GetTop(S)<<"\t";//输出栈顶元素

  54. Pop(S, x); //栈顶元素出栈

  55. }

  56. return 0;

  57. }


上一篇: 微软的100道算法面试题(终结版) 下一篇:Winform开发技术详解 - 应用环境 & 相关技术介绍
返回顶部