栈

  1 package array01;
  2 
  3 public class Array<T> {
  4     private T[] data; //存放数据
  5     private int size;
  6 
  7     //构造函数，传入数组的容量capacity构造Array
  8     public Array(int capacity){
  9         data = (T[])new Object[capacity];
 10         size = 0;
 11     }
 12 
 13     //无参构造 默认数组容量是10
 14     public Array(){
 15         this(10);
 16     }
 17 
 18     //获取数组中的元素个数
 19     public int getSize(){
 20         return size;
 21     }
 22 
 23     //获取数组的容量
 24     public int getCapacity(){
 25         return data.length;
 26     }
 27 
 28     public boolean isEmpty(){
 29         return size ==0;
 30     }
 31 
 32     public void addLast(T e){
 33         add(size,e);
 34     }
 35     public void addFirst(T e){
 36         add(0,e);
 37     }
 38 
 39 
 40     public void add(int index,T e){
 41 
 42         if(index < 0 || index > size){
 43             throw new IllegalArgumentException("Add failed. Require index < 0 || index > size");
 44         }
 45         if(size == data.length){
 46             resize(2 * data.length);
 47         }
 48         for (int i = size -1; i >= index; i --){
 49             data[i+1] = data[i];
 50         }
 51         data[index] = e;
 52         size ++;
 53 
 54     }
 55 
 56     // 获取index索引位置的元素
 57     public T get(int index){
 58         if(index <0 || index >= size){
 59             throw new IllegalArgumentException("Get failed. Index is illegal");
 60         }
 61         return data[index];
 62     }
 63     public T getLast(){
 64         return get(size - 1);
 65     }
 66 
 67     public T getFirst(){
 68         return get(0);
 69     }
 70 
 71 
 72     // 修改index索引位置的元素
 73     void set(int index ,T e){
 74         if(index <0 || index >= size){
 75             throw new IllegalArgumentException("Get failed. Index is illegal");
 76         }
 77         data[index] = e;
 78     }
 79     //查找数组中是否有元素e
 80     public boolean contains(T e){
 81 
 82         for(int i = 0 ; i < size ; i ++){
 83             if(data[i].equals(e)){
 84                 return true;
 85             }
 86         }
 87         return false;
 88     }
 89 
 90     //查找数组中元素所在的索引,如果不存在元素e 则返回-1
 91     public int find(T e){
 92         for(int i = 0 ; i < size ; i ++){
 93             if(data[i] == e){
 94                 return i;
 95             }
 96         }
 97         return -1;
 98     }
 99 
100     //从数组中删除index位置的元素 返回删除的元素
101     public T remove(int index){
102         if(index <0 || index >= size){
103             throw new IllegalArgumentException("Remove failed. Index is illegal");
104         }
105         T ret = data[index];
106         for(int i = index + 1 ; i <size ; i ++){
107             data[i - 1] =data[i];
108         }
109         size --;
110         if(size == data.length / 2){
111             resize(data.length / 2);
112         }
113         return ret;
114     }
115 
116     public T removeFirst(){
117         return remove(0);
118     }
119 
120     public T removeLast(){
121         return remove(size -1 );
122     }
123 
124     public void removeElement(T e){
125         int index = find(e);
126         if(index != -1){
127             remove(index);
128         }
129     }
130 
131 
132     @Override
133     public String toString(){
134          StringBuilder res = new StringBuilder();
135          res.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));
136          res.append("[");
137          for(int i = 0 ; i < size ; i ++){
138              res.append(data[i]);
139              if(i != size - 1){
140                  res.append(",");
141              }
142          }
143         res.append("]");
144          return res.toString();
145     }
146 
147     private void resize(int newCapacity){
148         T[] newData = (T[]) new Object[newCapacity];
149         for(int i = 0 ; i < size; i ++){
150             newData[i] = data[i];
151         }
152         data = newData;
153 
154 
155     }
156
157 
158 }

package stack;

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);//进栈
    E pop(); //出栈
    E peek(); //栈顶的元素
}

 1 package stack;
 2 
 3 import array01.Array;
 4 
 5 public class ArrayStack<E> implements  Stack<E> {
 6     Array<E> array;
 7     public ArrayStack(int capacity){
 8         array = new Array<>(capacity);
 9     }
10 
11     public ArrayStack(){
12         array = new Array<>();
13     }
14 
15     @Override
16     public int getSize() {
17         return array.getSize();
18     }
19 
20     @Override
21     public boolean isEmpty() {
22         return array.isEmpty();
23     }
24 
25     public int getCapacity(){
26         return array.getCapacity();
27     }
28 
29     @Override
30     public void push(E e) {
31         array.addLast(e);
32     }
33 
34     @Override
35     public E pop() {
36         return array.removeLast();
37     }
38 
39     @Override
40     public E peek() {
41         return array.getLast();
42     }
43 
44     @Override
45     public String toString(){
46         StringBuilder res = new StringBuilder();
47         res.append("Stack: ");
48         res.append("[");
49         for(int i = 0 ; i < array.getSize(); i  ++){
50             res.append(array.get(i));
51             if(i != array.getSize() - 1){
52                 res.append(", ");
53             }
54         }
55         res.append("] top");
56         return res.toString();
57     }
58 }

我们写一个主函数进行测试

 1 import stack.ArrayStack;
 2 
 3 public class Main {
 4     public static void main(String[] args) {
 5         ArrayStack<Integer> stack = new ArrayStack<>();
 6 
 7         for(int i = 0 ; i < 5 ; i ++){
 8             stack.push(i);
 9             System.out.println(stack);
10         }
11 
12 
13         stack.pop();
14         System.out.println(stack);
15 
16     }
17 }