4、栈的实现:顺序存储和链式存储

Stack的ADT:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package ren.laughing.datastructure.base;
 
import ren.laughing.datastructure.exception.StackEmptyException;
 
/**
 * Stack 栈:后进先出
 * 只能在栈顶top进行插入(入栈)、删除(出栈)操作
 * @author Laughing_Lz
 * @time 2016年4月6日
 */
public interface Stack {
    //返回堆栈的大小
    public int getSize();
    //判断堆栈是否为空
    public boolean isEmpty();
    //数据元素 e入栈
    public void push(Object e);
    //栈顶元素出栈
    public Object pop() throws StackEmptyException;
    //取栈顶元素
    public Object peek() throws StackEmptyException;
    }

栈的顺序存储:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package ren.laughing.datastructure.baseImpl;
 
import ren.laughing.datastructure.base.Stack;
import ren.laughing.datastructure.exception.StackEmptyException;
/**
 * 栈的顺序存储结构
 * 一般来说在构造堆栈时不应设定堆栈的最大容量。
 * 一种合理的做法为先为堆栈分配一个基本容量,然后在实际的使用过程中,
 * 当堆栈的空间不够时再倍增存储空间,这个过程所需的时间均摊到每个数
 * 据元素时间为Θ(1),不会影响操作实现的时间复杂度。
 * @author Laughing_Lz
 * @time 2016年4月6日
 */
public class StackArray implements Stack {
    private final int LEN = 8;//默认数组的存储大小
    private Object[] elements;//数据元素数组
    private int top;//栈顶指针
 
    public StackArray() {
        this.elements = new Object[LEN];
        this.top = -1;//top为-1时表示空栈
    }
 
    @Override
    public int getSize() {
        return top+1;
    }
 
    @Override
    public boolean isEmpty() {
        if(top < 0){ return true; }else{ return false; } } @Override public void push(Object e) { if(getSize()>=elements.length){
            expandSpace();
        }
        //++top:因为入栈操作相当于insertAfter,
        //只能在顶点后插入,所以首先将top加1,再放入数据元素
        elements[++top] = e;
    }
 
    @Override
    public Object pop() throws StackEmptyException {
        if(top<0){
            throw new StackEmptyException("错误:栈为空,不可出栈操作");
        }else{
            Object obj = elements[top];
            elements[top--] = null;//先取出原栈顶数据元素,再置空、top减一
            return obj;
        }
    }
    //取栈顶元素
    @Override
    public Object peek() throws StackEmptyException {
        if(getSize()<=0){
            throw new StackEmptyException("错误:栈顶为空");
        }else{
            return elements[top];
        }
    }
    /**
     * 扩充数组长度
     */
    private void expandSpace() {
        Object[] a = new Object[elements.length * 2];
        for (int i = 0; i < elements.length; i++)
            a[i] = elements[i];
        elements = a;
    }
}

栈的链式存储:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package ren.laughing.datastructure.baseImpl;
 
import ren.laughing.datastructure.base.Stack;
import ren.laughing.datastructure.exception.StackEmptyException;
/**
 * Stack的链式存储
 * ★此链表为的不含头结点的单链表
 * @author Laughing_Lz
 * @time 2016年4月6日
 */
public class StackLinked implements Stack{
    private SLNode top;//链表首结点引用
    private int size;//栈的大小
 
    public StackLinked() {
        this.size = 0;
//        this.top = new SLNode(null, null);
        top = null;//这个是否也实例化了呢?和上面是否有区别?
    }
 
    @Override
    public int getSize() {
        return size;
    }
 
    @Override
    public boolean isEmpty() {
        return size==0;
    }
 
    @Override
    public void push(Object e) {
        SLNode node = new SLNode(e, top);//相当于insertBefore 在原栈顶前插入新的数据元素
        top = node;
        size++;
    }
 
    @Override
    public Object pop() throws StackEmptyException {
        if (size<=0){
            throw new StackEmptyException("错误,堆栈为空。");
        }
        Object obj = top.getData();
        top = top.getNext();
        size--;
        return obj;
    }
 
    @Override
    public Object peek() throws StackEmptyException {
        if (size<=0){
            throw new StackEmptyException("错误,堆栈为空。");
        }
        Object obj = top.getData();
        return obj;
    }
 
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注