玩转数据结构——栈和队列（栈）

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

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

 1 class Solution {
 2 
 3     public boolean isValid(String s) {
 4 
 5         ArrayStack<Character> stack = new ArrayStack<>();
 6         for(int i = 0 ; i < s.length() ; i ++){
 7             char c = s.charAt(i);
 8             if(c == ‘(‘ || c == ‘[‘ || c == ‘{‘)
 9                 stack.push(c);
10             else{
11                 if(stack.isEmpty())
12                     return false;
13 
14                 char topChar = stack.pop();
15                 if(c == ‘)‘ && topChar != ‘(‘)
16                     return false;
17                 if(c == ‘]‘ && topChar != ‘[‘)
18                     return false;
19                 if(c == ‘}‘ && topChar != ‘{‘)
20                     return false;
21             }
22         }
23         return stack.isEmpty();
24     }
25 
26     public static void main(String[] args) {
27 
28         System.out.println((new Solution()).isValid("()[]{}"));
29         System.out.println((new Solution()).isValid("([)]"));
30     }
31 }

1 public interface Stack<E> {
2 
3     int getSize();
4     boolean isEmpty();
5     void push(E e);
6     E pop();
7     E peek();
8 }