4.1栈
栈的定义：又称堆栈，它是运算受限的线性表，其限制是仅允许在表的一段进行插入和删除操作，不允许在其他任何位置进行插入，查找，删除等操作。
栈的接口Stack：
1 package com.datastructure.chapter04.interfaces;
2
3 import com.datastructure.chapter04.Exception.StackEmptyException;
4
5 /**
6 * @ClassName: Stack
7 * @Description: 栈接口
8 * @author
9 * @date 2018年3月16日 下午8:52:24
10 *
11 */
12 public interface Stack {
13
14 //返回堆栈的大小
15 public int getSize();
16
17 //判断堆栈是否为空
18 public boolean isEmpty();
19
20 //数据元素e入栈
21 public void push(Object e);
22
23 //栈顶元素出栈
24 public Object pop() throws StackEmptyException;
25
26 //取栈顶元素
27 public Object peek() throws StackEmptyException;
28
29
30 }
空栈抛出的异常类：
1 package com.datastructure.chapter04.Exception;
2
3 @SuppressWarnings("serial")
4 public class StackEmptyException extends RuntimeException {
5
6 public StackEmptyException(String err) {
7 super(err);
8 }
9
10 }
4.1.2 Stack的顺序存储实现
1 package com.datastructure.chapter04.interfaces;
2
3 import com.datastructure.chapter04.Exception.StackEmptyException;
4
5 /**
6 * @ClassName: StackArray
7 * @Description: 栈的顺序存储实现
8 * @author
9 * @date 2018年3月16日 下午9:05:52
10 *
11 */
12 public class StackArray implements Stack {
13
14 private final int LEN = 8;//数组的默认大小
15 private Object[] elements;//数据元素数组
16 private int top;//栈顶指针
17
18
19 public StackArray(){
20 top = -1;
21 elements = new Object[LEN];
22 }
23
24
25 /* (非 Javadoc)
26 * <p>Title: getSize</p>
27 * <p>Description: 返回堆栈的大小</p>
28 * @return
29 * @see com.datastructure.chapter04.interfaces.Stack#getSize()
30 */
31 @Override
32 public int getSize() {
33 return top+1;
34 }
35
36 /* (非 Javadoc)
37 * <p>Title: isEmpty</p>
38 * <p>Description: 判断堆栈的大小</p>
39 * @return
40 * @see com.datastructure.chapter04.interfaces.Stack#isEmpty()
41 */
42 @Override
43 public boolean isEmpty() {
44
45 return top<0;
46 }
47
48 /* (非 Javadoc)
49 * <p>Title: push</p>
50 * <p>Description: 数据元素e入栈</p>
51 * @param e
52 * @see com.datastructure.chapter04.interfaces.Stack#push(java.lang.Object)
53 */
54 @Override
55 public void push(Object e) {
56 if(getSize()>=elements.length) expandSpace();
57 elements[++top] = e;
58 }
59
60 /**
61 * @Title: expandSpace
62 * @Description: 对数组进行扩容
63 * @param
64 * @return void
65 * @throws
66 */
67 private void expandSpace() {
68 Object[] a = new Object[elements.length*2];
69 for (int i = 0; i < elements.length; i++)
70 a[i] = elements[i];
71 elements = a;
72 }
73
74
75 /* (非 Javadoc)
76 * <p>Title: pop</p>
77 * <p>Description: 栈顶元素出栈</p>
78 * @return
79 * @throws StackEmptyException
80 * @see com.datastructure.chapter04.interfaces.Stack#pop()
81 */
82 @Override
83 public Object pop() throws StackEmptyException {
84 if(getSize()<1)
85 throw new StackEmptyException("错误，堆栈为空。");
86 Object obj = elements[top];
87 elements[top--]= null;
88 return obj;
89 }
90
91 /* (非 Javadoc)
92 * <p>Title: peek</p>
93 * <p>Description: 取栈顶元素</p>
94 * @return
95 * @throws StackEmptyException
96 * @see com.datastructure.chapter04.interfaces.Stack#peek()
97 */
98 @Override
99 public Object peek() throws StackEmptyException {
100 if(getSize()<1)
101 throw new StackEmptyException("错误，堆栈为空。");
102 return elements[top];
103 }
104
105
106 }
push、pop、peek运行时间都是O(1).
4.1.3 Stack的链式存储实现
1 package com.datastructure.chapter04.impl;
2
3 import com.datastructure.chapter04.Exception.StackEmptyException;
4 import com.datastructure.chapter04.interfaces.Stack;
5
6 public class StackSLinked implements Stack {
7
8 private SLNode top;//链表首结点引用
9
10 private int size; //栈的大小
11
12 public StackSLinked() {
13 top = null;
14 size = 0;
15 }
16
17
18 /* (非 Javadoc)
19 * <p>Title: getSize</p>
20 * <p>Description: 返回堆栈的大小</p>
21 * @return
22 * @see com.datastructure.chapter04.interfaces.Stack#getSize()
23 */
24 @Override
25 public int getSize() {
26 return size;
27 }
28
29 /* (非 Javadoc)
30 * <p>Title: isEmpty</p>
31 * <p>Description: 判断堆栈是否为空 </p>
32 * @return
33 * @see com.datastructure.chapter04.interfaces.Stack#isEmpty()
34 */
35 @Override
36 public boolean isEmpty() {
37
38 return size == 0;
39 }
40
41 /* (非 Javadoc)
42 * <p>Title: push</p>
43 * <p>Description: 数据元素进栈</p>
44 * @param e
45 * @see com.datastructure.chapter04.interfaces.Stack#push(java.lang.Object)
46 */
47 @Override
48 public void push(Object e) {
49 SLNode q = new SLNode(e, top);
50 top = q;
51 size++;
52 }
53
54 /* (非 Javadoc)
55 * <p>Title: pop</p>
56 * <p>Description: 栈顶出栈</p>
57 * @return
58 * @throws StackEmptyException
59 * @see com.datastructure.chapter04.interfaces.Stack#pop()
60 */
61 @Override
62 public Object pop() throws StackEmptyException {
63 if(size<1)
64 throw new StackEmptyException("错误，堆栈为空");
65 Object obj = top.getData();
66 top = top.getNext();
67 return obj;
68 }
69
70 /* (非 Javadoc)
71 * <p>Title: peek</p>
72 * <p>Description: 取栈顶元素</p>
73 * @return
74 * @throws StackEmptyException
75 * @see com.datastructure.chapter04.interfaces.Stack#peek()
76 */
77 @Override
78 public Object peek() throws StackEmptyException {
79
80 if(size<1)
81 throw new StackEmptyException("错误，堆栈为空");
82 return top.getData();
83 }
84
85 }
所有的操作都在O(1)时间内完成