栈的java实现

1. 栈模型

栈是一种只能在末端即栈顶top，进行插入和删除的线性数据结构。对栈的基本操作包括push和pop，即插入和删除操作。栈是一种“先进后出”的结构，与队列的“先进先出”结构相对应，同为受限制的线性数据结构。

2. 栈的数组实现

2.1 泛型的应用

使用泛型能够使实现的类更加通用，而不是只能够应用在特殊的场景。但是在使用泛型的过程中，也遇到了相应的问题，即泛型的使用是有限制的。
以下关于泛型的内容参考【Java】泛型学习笔记

定义泛型时的限制

  1. 不能实例化类型变量
    如T obj = new T();，可使用强制类型转换解决。
  2. 不能实例化泛型数组
    如T[] arr = new T[5];，可使用强制类型转换或反射解决。
  3. 不能在泛型类的静态上下文中使用类型变量
  4. 不能抛出或者捕获泛型类的实例

使用泛型时的限制

  1. 不能使用基本类型的值作为类型变量的值
    Foo<int> node = new Foo<int> (); // 非法
    应该选用这些基本类型对应的包装类型
    Foo<Integer> node = new Foo<Integer> ();
  2. 不能创建泛型类的数组
1
2
3
public static void main (String args[]) {
    Foo<Node> [] f =new Foo<Node> [6]; // 报错
}

解决方法：
可以声明通配类型的数组， 然后做强制转换

1
Foo<Node> [] f =(Foo<Node> [])new Foo<?> [6]; // 通过

在具体实现中只用到了定义限制中的第二点，解决方法使用强制类型转换。

2.2 实现代码

源码已发在github上了，详见DataStructuresAlgorithm/Stack

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
public class Stack<T> {
//    private T[] data;
    private Object[] data;
    private int maxSize;
    private int top;

    /*
    泛型
    1.不能实例化类型变量， 如T obj = new T ();
    2. 不能实例化泛型数组，如T [] arr = new T[3];
    解决方法：
    利用强制类型转换或者反射
     */

    //https://www.cnblogs.com/penghuwan/p/8420791.html
    //https://www.jianshu.com/p/e618b81aadb4

    //应用强制类型转换方法
    public Stack(int maxSize){
        this.maxSize = maxSize;
        //java type parameter cannot be instantiated directly
        data = new Object[maxSize];
        this.top = -1;
    }

    //应用反射方法
//    public Stack(Class<T> tClass, int maxSize){
//        this.maxSize = maxSize;
//        //java type parameter cannot be instantiated directly
//        data = (T[]) Array.newInstance(tClass, maxSize);
//        this.top = -1;
//    }

    public int getMaxSize(){
        return maxSize;
    }

    public boolean empty(){
        return top == -1;
    }

    public boolean isFull(){
        return top + 1 == maxSize;
    }

    public int getElementCount(){
        return top + 1;
    }

    //java中的Stack类是不定长的，所以push方法返回的是Object x
    public boolean push(Object x){
        if(isFull()){
            System.out.println("当前栈满");
            return false;
        }
        this.data[++top] = x;
        return true;
    }

    //java中的Stack类的pop方法返回的是栈顶Object
    public T pop() throws Exception{
        if(empty()) {
            throw new Exception("当前栈空");
        }
        return (T) this.data[top--];
    }

    public Object peek() throws Exception{
        if(empty()){
            throw new Exception("当前栈空");
        }
        return (T) this.data[top];
    }

    public static void main(String[] args) throws Exception {
        Stack<Integer> stack = new Stack<>(5);
        stack.push(3);
        stack.push(4);
        stack.push(2);
        stack.pop();
        System.out.println(stack.peek());
        stack.pop();
        System.out.println(stack.peek());

        Stack<String> stringStack = new Stack<>(5);
        stringStack.push("Hello");
        stringStack.push("world");
        stringStack.push("java");
        stringStack.pop();
        System.out.println(stringStack.peek());
        stringStack.push("stack");
        System.out.println(stringStack.peek());
    }
}