第四章栈与队列1 （栈）

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 }

View Code

空栈抛出的异常类：

 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 }

View Code

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 }

View Code

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 }

View Code

所有的操作都在O(1)时间内完成

第四章 栈与队列1 （栈）

第四章栈与队列1 （栈）