数据结构——栈(Stack)与队列(Queue)的手写实例_栈 手写

一、 栈与队列的定义

栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。

　队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。

二、 用数组实现栈

1、栈的接口定义

/**
 * 定义栈的接口
 *
 * @author zhuhuix
 * @date 2020-05-01
 */
public interface Stack {
   
    /**
     * 入栈
     * @param object 入栈元素
     */
    void push(Object object);

    /**
     * 出栈
     * @return 出栈元素
     */
    Object pop();

    /**
     *  获取元素个数
     * @return 元素个数
     */
    int getElementCount();

    /**
     * 遍历栈的元素
     */
    void traverse();

}

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

2、栈的接口实现

/**
 * 栈的接口实现
 *
 * @author zhuhuix
 * @date 2020-05-01
 */
public class StackImpl implements Stack {
   
	
    protected Object[] element;

    protected int elementCount;

    private int defaultSize = 16;

    private int maxSize;

    StackImpl() {
   
        element = new Object[defaultSize];
        maxSize = defaultSize;
    }

    StackImpl(int size) {
   
        element = new Object[size];
        maxSize = size;
    }

    @Override
    public void push(Object object) {
   
        //如果元素个数已经达到数组的最大个数，则进行扩容
        if (elementCount == maxSize) {
   
            element = Arrays.copyOf(element, elementCount + defaultSize);
        }
        element[elementCount++] = object;

    }
	// 本代码未实现数组的自动缩小，具体方法可参考JDK
    @Override
    public Object pop() {
   
        if (elementCount == 0) {
   
            throw new ArrayIndexOutOfBoundsException("栈中无元素");
        }
        Object object = element[--elementCount];
        element[elementCount] = null;
        return object;
    }

    @Override
    public int getElementCount() {
   
        return elementCount;
    }

    @Override
    public void traverse() {
   
        for (int i = 0; i < elementCount; i++
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