主题:Java数据结构:栈的实现
栈是Java语言中最重要的数据结构之一,它的实现,至少应该包括以下几个方法:
1. pop() 出栈操作,弹出栈顶元素。
2. push(E e) 入栈操作
3. peek() 查看栈顶元素
4. isEmpty() 栈是否为空
另外,实现一个栈,还应该考虑到几个问题:
1. 栈的初始大小以及栈满以后如何新增栈空间
2. 对栈进行更新时需要进行同步
简单示例,使用数组实现栈,代码如下:
1.
public class Stack{
2.
3. // Java 不支持泛型数组,如需使用,请使用Java提供的容器
4. private Object[] stack;
5.
6. // 栈的默认初始大小
7. private static final int INIT_SIZE = 2;
8.
9. // 栈顶索引
10. private int index;
11.
12. public Stack() {
13. stack = new Object[INIT_SIZE];
14. index = -1;
15. }
16.
17. /**
18. * 构造方法
19. *
20. * @param initSize
21. * 栈的初始大小
22. */
23. public Stack(int initSize) {
24. if (initSize < 0) {
25. throw new IllegalArgumentException();
26. }
27. stack = new Object[initSize];
28. index = -1;
29. }
30.
31. /**
32. * 出栈操作
33. *
34. * @return 栈顶对象
35. */
36. public synchronized E pop() {
37. if (!isEmpty()) {
38. E temp = peek();
39. stack[index--] = null;
40. return temp;
41. }
42. return null;
43. }
44.
45. /**
46. * 入栈操作
47. *
48. * @param obj
49. * 等待入栈的对象
50. */
51. public synchronized void push(E obj) {
52. if (isFull()) {
53. Object[] temp = stack;
54. // 如果栈满,则创建空间为当前栈空间两倍的栈
55. stack = new Object[2 * stack.length];
56. System.arraycopy(temp, 0, stack, 0, temp.length);
57. }
58. stack[++index] = obj;
59. }
60.
61. /**
62. * 查看栈顶对象
63. *
64. * @return 栈顶对象
65. */
66. public E peek() {
67. if (!isEmpty()) {
68. return (E) stack[index];
69. }
70. return null;
71. }
72.
73. /**
74. * 查看栈是否为空
75. *
76. * @return 如果栈为空返回true,否则返回false
77. */
78. public boolean isEmpty() {
79. return index == -1;
80. }
81.
82. /**
83. * 查看栈是否满
84. *
85. * @return 如果栈满返回true,否则返回false
86. */
87. public boolean isFull() {
88. return index >= stack.length - 1;
89. }
90. }
最后说明,Java中实现了栈(java.util.Stack)的数据结构,它是通过继承Vector类实现的,一般情况下我们直接拿来用就行了。
疯狂java视频 android视频:http://www.fkjava.org/video.html