用动态数组实现栈

用动态数组实现栈

  1. 栈的定义
    栈是一种后进先出的数据结构Last in first out(LIFO)
  2. 栈的定义
    栈应该至少实现以下接口

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    package StacksAndQueues.ArrayStack;

    /**
    * @ Description: Stack接口 标准的栈应该具有以下5个对外方法
    * @ Date: Created in 19:00 11/07/2018
    * @ Author: Anthony_Duan
    */
    public interface Stack<E> {

    //得到栈中元素的个数
    int getSize();

    //判断栈是否为空
    boolean isEmpty();

    // 入栈操作
    void push(E e);

    //出栈操作
    E pop();

    //获取栈顶元素的值
    E peek();
    }
  3. 使用动态数组作为底层实现栈

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
package StacksAndQueues.ArrayStack;

/**
* @ Description: 使用Array动态数组类封装而成的栈实现,包括了动态增长与缩减
* @ Date: Created in 19:02 11/07/2018
* @ Author: Anthony_Duan
*/
public class ArrayStack<E> implements Stack<E> {


private Array<E> array;

public ArrayStack(int capacity) {
array = new Array<E>(capacity);
}

public ArrayStack() {
array = new Array<E>();
}

@Override
public int getSize() {
return array.getSize();
}

@Override
public boolean isEmpty() {
return array.isEmpty();
}

@Override
public void push(E e) {
array.addLast(e);
}

@Override
public E pop() {
return array.removeLast();
}

@Override
public E peek() {
return array.getLast();
}


@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append("[");
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1) {
res.append(",");
}
}
res.append("] top");
return res.toString();
}
}
  1. 利用动态数组实现的栈的复杂度分析
  • void push(E e); ———————O(1) 均摊
  • E pop(); ——————————O(1) 均摊
  • int getSize(); ———————O(1)
  • E pop(); ——————————O(1)
  • E peek();——————————O(1)
  1. 动态数组的实现代码
    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
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    package StacksAndQueues.ArrayStack;

    /**
    * @ Description: 动态数组的实现
    * 为Stack实现做存储,新增加了两个getFirst与getLast方法
    * @ Date: Created in 14:37 11/07/2018
    * @ Author: Anthony_Duan
    */
    public class Array<E> {

    private E[] data;

    /**
    * size指向的是数组中最后一个元素的下一个空的存储单元
    */
    private int size;

    /**
    * 构造函数,传入数组的容量capacity构造Array
    *
    * @param capacity
    */
    public Array(int capacity) {
    data = (E[]) new Object[capacity];
    size = 0;
    }

    /**
    * 无参构造方法 默认数组长度为10
    */
    public Array() {
    this(10);
    }

    /**
    * 获得数组的容量
    *
    * @return
    */
    public int getCapacity() {
    return data.length;
    }

    /**
    * 获得数组中元素的个数
    *
    * @return
    */
    public int getSize() {
    return size;
    }

    /**
    * 判断数组是否为空
    *
    * @return
    */
    public boolean isEmpty() {
    return size == 0;
    }

    /**
    * 在index索引的位置插入一个新元素e
    * 如果数组已经满了就扩充数组,新扩充的数组的长度是原来的2倍
    *
    * @param index
    * @param e
    */
    public void add(int index, E e) {
    if (size == data.length) {
    resize(2 * data.length);
    }
    if (index < 0 || index > size) {
    throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    }
    for (int i = size - 1; i >= index; i--) {
    data[i + 1] = data[i];
    }
    data[index] = e;
    size++;

    }

    /**
    * 向数组末尾追加元素e
    *
    * @param e
    */
    public void addLast(E e) {
    add(size, e);
    }

    /**
    * 向数组的头部添加元素e
    *
    * @param e
    */
    public void addFirst(E e) {
    add(0, e);
    }

    /**
    * 获得指定索引的元素
    *
    * @param index
    * @return
    */
    public E get(int index) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Set failed. Index is illegal.");
    } else {
    return data[index];
    }

    }

    /**
    * 获得数组中的第一个元素
    *
    * @return
    */
    public E getFirst() {
    return get(0);
    }

    /**
    * 获取数组中的最后一个元素
    *
    * @return
    */
    public E getLast() {
    return get(size - 1);
    }

    /**
    * 修改指定索引元素的值为e
    *
    * @param index
    * @param e
    */
    public void set(int index, E e) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Set failed. Index is illegal.");
    } else {
    data[index] = e;
    }
    }

    /**
    * 判断数组中是否包含元素e
    *
    * @param e
    * @return
    */
    public boolean contains(E e) {
    for (int i = 0; i < size; i++) {
    if (data[i].equals(e)) {
    return true;
    }
    }
    return false;
    }

    /**
    * 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
    *
    * @param e
    * @return
    */
    public int find(E e) {
    for (int i = 0; i < size; i++) {
    if (data[i].equals(e)) {
    return i;
    }
    }
    return -1;
    }

    /**
    * 删除指定索引的元素 返回该索引的值
    * 如果数组中的元素的个数小于数组长度的四分之一就缩短数组长度为原来的二分之一
    *
    * @param index
    * @return
    */
    public E remove(int index) {
    if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Remove failed. Index is illegal.");
    }
    E ret = data[index];
    for (int i = index + 1; i < size; i++) {
    data[i - 1] = data[i];
    }
    size--;
    // loitering objects != memory leak 这里置空后垃圾回收机制会自动回收 否则不会回收 但也不属于内存泄露
    data[size] = null;

    //这里之所以用四分之一是为了做了lazy的处理 避免数组出现复杂度震荡的情况 如果除以2则
    // removeLast 时 resize 过于着急(Eager) 可能会出现震荡

    if (size == data.length / 4 && data.length / 2 != 0) {
    resize(data.length / 2);
    }
    return ret;
    }

    /**
    * 从数组中删除元素e 在数组存在多个e时只能删除第一个
    *
    * @param e
    */
    public void removeElement(E e) {
    int index = find(e);
    if (index != -1) {
    remove(index);
    }
    }

    /**
    * 从数组中删除第一个元素, 返回删除的元素
    *
    * @return
    */
    public E removeFirst() {
    return remove(0);
    }

    /**
    * 从数组中删除最后一个元素, 返回删除的元素
    *
    * @return
    */
    public E removeLast() {
    return remove(size - 1);
    }

    /**
    * 将数组空间的容量变成newCapacity大小
    *
    * @param newCapacity
    */
    private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
    newData[i] = data[i];
    }
    data = newData;
    }


    @Override
    public String toString() {
    StringBuilder res = new StringBuilder();
    res.append(String.format("Arry: size = %d , capacity = %d\n", size, data.length));
    res.append("[");
    for (int i = 0; i < size; i++) {
    res.append(data[i]);
    if (i != size - 1) {
    res.append(", ");
    }
    }
    res.append("]");
    return res.toString();
    }
    }
-------------End Of This ArticleThank You For Reading-------------