栈的两种实现方式-向日葵屋

栈的两种实现方式

青旅半醒 2023-06-24 15:24 40阅读 0赞

一、数组实现栈

首先需要定义一个数组来储存栈中的数据，并定义一个变量来记录数组中储存元素的个数，编写一个构造方法来构造一个长度为十得数组。

//先顶i有一个数组来存储栈中的元素
```
private Object array[];
//定义数组中存储元素的个数
private int size;
//构造后一个长度与为10的数组
public MyStack() {
    array = new Object[10];
}
```
判断栈是否为空
只需要判断记录数组储存元素数量的变量是否为零即可。

//判断栈是否为空
public boolean isEmple() {
```
   return size == 0;
```
}
扩充数组
判断数组是否已经满了，如果满了则需要扩充数组，定义一个值为10的长度变量，调用Arrays中的copyOf(array, newsize)方法来扩充数组

//判断数组是否已经满了，如果满了则扩充数组
```
public void addarray(int size) {
    if(size>array.length) {
        int newsize = 10;
        array = Arrays.copyOf(array, newsize);
    }
}
```
向栈中添加元素
先调用addarray方法查看当前元素是否能添加进去，如果数组已满则扩充数组长度。最后直接将需要添加的元素赋给数组的第size++个元素。

//向栈中添加元素
```
public void put(E e) {
    //先判断数组是否能存储下当前元素,如果没有的话会自动扩充
    addarray(size+1);
    array[size++] = e;
}
```

5.查看栈顶元素
先判断栈是否为空，如果为空直接返回false,反之直接返回数组的最后一个元素。

//查看栈顶元素
    public E peek() {
        if(isEmple()) {
        //如果栈为空
            return null;
        }
        return (E) array[size-1];
    }

取出栈顶元素
直接调用peek方法，该方法会返回栈顶元素，直接将它赋给一个新的变量，然后将数组的最后一个元素也就是栈顶元素赋值为空，然后返回这个变量。

//取出栈顶元素
```
public E pop() {
    E e = peek();
    array[size-1] = null; //将栈顶赋为空
    size--;    //数组长度-1
    return e;
}
```

测试：

public static void main(String[] args) {

    MyStack<Integer> a = new MyStack<Integer>();
    a.put(1);
    a.put(2);
    a.put(3);
    a.put(4);
    System.out.println("栈顶元素为："+a.pop());
    System.out.println("栈顶元素为："+a.pop());
    System.out.println("栈顶元素为："+a.pop());
}

运行截图：

二、链表实现栈

节点类：定义节点的值，下一个节点和新节点的构造方法。

public class Node {

    E data;
    Node<E> next;
    public Node(E data) {
        this.data = data;
    }
}

实现类：先定义一个栈顶节点，判断栈知否为空，直接返回栈顶节点是否为空。

//定义一个栈顶节点
```
Node<E> top =null;
//判断栈是否为空
public boolean isEmple() {
    return top == null;
};
```

向栈中添加元素
先创建一个新节点，并判断栈是否为空，如果为空的话，直接将新节点赋给栈顶节点，反之将栈顶节点赋给它的后继节点，再将新节点赋给栈顶节点，并返回栈顶结点。

//向栈中添加节点

public E put(E e) {
    //创建一个新节点
    Node<E> newNode = new Node<E>(e);
    if(isEmple()) {
   //判断如果栈为空的话将新元素添加给栈顶节点
        top = newNode;
    }
    newNode.next = top;   //将栈顶节点节点赋给新节点的下一个节点
    top = newNode;    //将新节点赋给栈顶结点节点
    return (E) top;
}

查看栈顶元素：
先判断栈是否为空，如果为空返回空，反之返回栈顶节点值。

//查看栈顶元素
```
public E peek() {
    if(isEmple()) {
        return null;
    }
    return top.data;
}
```
取出栈顶元素：
直接调用peek方法，该方法会返回栈顶节点的值，将其赋给一个新变量，然后将栈顶节点的后继节点赋给它本身，最后返回这个新变量。

//取出栈顶元素
```
public E pop() {
    E e = peek();
    top = top.next;   //将栈顶节点的后继节点赋给栈顶节点
    return e;
}
```

测试：

public static void main(String[] args) {

    NodeStack<Integer> s = new NodeStack<Integer>(); 
    s.put(1);
    s.put(2);
    s.put(3);
    s.put(4);
    System.out.println("栈顶元素："+s.pop());
    System.out.println("栈顶元素："+s.pop());
    System.out.println("栈顶元素："+s.pop());
}