Java数据结构（二）_JAVA_编程开发_程序员俱乐部

class="MsoNormal" style="text-align: center;">Java数据结构（二）

——栈

栈是一种特殊的线性表。栈的数据元素以及数据元素的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和caozuo.html" target="_blank">删除操作，而栈只允许在固定一段进行插入和删除操作。栈中允许进行插入和删除操作的一段称为栈顶，另一端称为栈底。栈的插入操作通常我们都成为进栈或入栈~~而删除操作通常称为出栈或退栈。

根据栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是当前栈顶元素，这样，最后进入栈的数据元素总是最先退出栈，因此栈也被称为后进后出表。

顺序栈

?

1. package?pzw.Stack;??
2. /**?
3. ?*?使用顺序存储结构实现的堆栈?
4. ?*?@author?pzw?
5. ?*?
6. ?*/??
7. public?class?SeqStack?implements?Stack{??
8. ??????
9. ????final?int?defaultSize?=?10;//默认构造函数的堆栈的大小??
10. ????int?top;//栈顶位置??
11. ????Object[]?stack;//数组对象??
12. ????int?maxStackSize;//该堆栈最大元素个数??
13. ????//无参构造函数??
14. ????public?SeqStack(){??
15. ????????initiate(defaultSize);??
16. ????}??
17. ????//构造函数??
18. ????public?SeqStack(int?size){??
19. ????????initiate(size);??
20. ????}??
21. ????//初始化堆栈??
22. ????private?void?initiate(int?sz){??
23. ????????maxStackSize?=?sz;??
24. ????????top?=?0;??
25. ????????stack?=?new?Object[sz];??
26. ????}??
27. ??????
28. ????public?void?push(Object?elm)?throws?Exception?{??
29. ????????if(top?==?maxStackSize){??
30. ????????????throw?new?Exception("该堆栈已满");??
31. ????????}??
32. ????????stack[top]?=?elm;//保存元素??
33. ????????top++;??
34. ????}??
35. ??
36. ????public?Object?pop()?throws?Exception?{??
37. ????????if(top?==?0){??
38. ????????????throw?new?Exception("该堆栈已空");??
39. ????????}??
40. ????????top--;????
41. ????????return?stack[top];??
42. ????}??
43. ??
44. ????public?Object?getTop()?throws?Exception?{??
45. ????????if(top?==?0){??
46. ????????????throw?new?Exception("该堆栈已空");??
47. ????????}??
48. ????????return?stack[top-1];??
49. ????}??
50. ??
51. ????public?boolean?notEmpty()?{??
52. ????????//?TODO?Auto-generated?method?stub??
53. ????????return?top?>?0;??
54. ????}??
55. ??
56. }??

?

链式栈

?

1. package?pzw.Stack;??
2. /**?
3. ?*?链式存储结构堆栈的实现?
4. ?*?@author?PZW?
5. ?*?
6. ?*/??
7. public?class?LinStack?implements?Stack{??
8. ????public?Node?top;//栈顶结点??
9. ????public?int?size;//结点个数??
10. ??????
11. ????//构造函数??
12. ????public?LinStack(){??
13. ????????top?=?null;??
14. ????????size?=?0;??
15. ????}??
16. ??????
17. ????public?void?push(Object?elm)?throws?Exception?{??
18. ????????top?=?new?Node(elm,top);??
19. ????????size++;??
20. ????}??
21. ??
22. ????public?Object?pop()?throws?Exception?{??
23. ????????if(size?==?0){??
24. ????????????throw?new?Exception("该堆栈已空");??
25. ????????}??
26. ????????Object?elm?=?top.elm;??
27. ????????top?=?top.next;??
28. ????????size--;??
29. ????????return?elm;??
30. ????}??
31. ??
32. ????public?Object?getTop()?throws?Exception?{??
33. ????????if(size?==?0){??
34. ????????????throw?new?Exception("该堆栈已空");??
35. ????????}??
36. ??????????
37. ????????return?top.elm;??
38. ????}??
39. ??
40. ????@Override??
41. ????public?boolean?notEmpty()?{??
42. ????????//?TODO?Auto-generated?method?stub??
43. ????????return?size?>?0;??
44. ????}??
45. ??
46. } ?

• Stack.zip (2.4 KB)
• 描述: 栈的实现
• 下载次数: 0