正月初九,开工大吉!
2024年,更上一层楼!

写在开头

其实在List的继承关系中,除了ArrayList和LinkedList之外,还有另外一个集合类stack(栈),它继承自vector,线程安全,先进后出,随着Java并发编程的发展,它在很多应用场景下被逐渐替代,成为了Java的遗落之类。不过,stack在数据结构中仍有一席之地,因此,我们有必要也应该好好的学一下!

Collection和Collections的区别?

在开始学习栈之前,先来解决一下之前一个网友在评论区问的问题:

Collection和Collections有什么区别?

虽然这两个类都在java.util包下,虽然只有一字之差,但它们的差别还是挺大的!
Collection 是JDK中集合层次结构中的最根本的接口。定义了集合类的基本方法。源码中的解释:

 * The root interface in the <i>collection hierarchy</i>.  A collection
 * represents a group of objects, known as its <i>elements</i>.  Some
 * collections allow duplicate elements and others do not.  Some are ordered
 * and others unordered.  The JDK does not provide any <i>direct</i>
 * implementations of this interface: it provides implementations of more
 * specific subinterfaces like <tt>Set</tt> and <tt>List</tt>.  This interface
 * is typically used to pass collections around and manipulate them where
 * maximum generality is desired.

Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法,不能实例化,Collection 集合框架的工具类。源码中的解释:

* This class consists exclusively of static methods that operate on or return
* collections.  It contains polymorphic algorithms that operate on
* collections, "wrappers", which return a new collection backed by a
* specified collection, and a few other odds and ends.

stack(栈)

栈(stack)是一种先进后出(Last In First Out,LIFO)的数据结构,类比于现实生活中的子弹上膛、泡泡圈。栈具有两个基本操作:入栈(push)和出栈(pop)。入栈表示将元素放入栈顶,而出栈表示从栈顶取出元素。

动图图解-入栈(push)

动图图解-出栈(pop)

在Java的工具包中其实帮我们封装好了一个类,java.util.Stack,它所提供的方法并不多,我们通过一个小示例感受一下。

【代码示例1】

Stack<String> stacks = new Stack<>();
//push方法入栈
 stacks.push("开");
 stacks.push("工");
 stacks.push("大");
 stacks.push("吉");
 stacks.push("!");
 System.out.println(stacks);
 //pop栈顶元素出栈
 String pop = stacks.pop();
 System.out.println(pop);
 //查看栈顶元素
 String peek = stacks.peek();
 System.out.println(peek);
 //判断堆栈是否为空
 boolean empty = stacks.empty();
 System.out.println(empty);
 //查看元素在堆栈中的位置
 int index = stacks.search("开");
 System.out.println(index);

输出:

[开, 工, 大, 吉, !]
!
吉
false
4

手写一个stack(堆栈)

通过上面的代码示例我们了解了一个栈所具备的功能特点,根据它的特点,我们尝试一下手写一个栈!
首先,准备一个数组用来存储元素,可以定义为Object,这样支持多数据类型,我们这里直接选用int类型的好嘞。
自定义栈-源码:

/**
 * @ClassName Stack
 * @Description 手写一个int类型的堆栈
 * @Author hzm
 * @Date 2024/2/18 14:21
 * @Version 1.0
 */
public class Stack {
    private int arr[];
    private int top;
    private int capacity;

    /**
     * 提供一个有参构造,初始化栈
     * @param size
     */
    public Stack(int size) {
        this.arr = new int[size];
        this.top = -1;
        this.capacity = size;
    }

    /**
     * 入栈
     * @param p
     */
    public void push(int p) {
        if (isFull()) {
            System.out.println("堆栈空间溢出\n程序终止\n");
            System.exit(1);
        }

        System.out.println("入栈:" + p);
        arr[++top] = p;
    }

    /**
     * 出栈
     * @return
     */
    public int pop() {
        if (isEmpty()) {
            System.out.println("空栈,不可POP");
            System.exit(1);
        }
        return arr[top--];
    }

    /**
     * 判断栈是否已满
     * @return
     */
    public Boolean isFull() {
        return top == capacity - 1;
    }

    /**
     * 判断栈是否为空
     * @return
     */
    public Boolean isEmpty() {
        return top == -1;
    }

    /**
     * 遍历栈内元素
     */
    public void printStack() {
        for (int i = 0; i <= top; i++) {
            System.out.println(arr[i]);
        }
    }

    /**
     * 返回栈的大小
     * @return
     */
    public int size() {
        return top + 1;
    }

    /**
     * 查看栈顶元素
     * @return
     */
    public void peek(){
        System.out.println("栈顶元素:" + arr[top]);
    }
}

测试类中调用手写的这个stack:

public class Test {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        //入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        //出栈
        int pop = stack.pop();
        System.out.println("出栈:"+ pop);
        //查看栈的大小
        int size = stack.size();
        System.out.println("栈容量:" + size);
        //查看栈顶元素
        stack.peek();
        //打印栈内元素
        stack.printStack();
    }
}

输出:

入栈:1
入栈:2
入栈:3
入栈:4
入栈:5
出栈:5
栈容量:4
栈顶元素:4
1
2
3
4

好了,今天的栈内容就写到这里吧,大家私下里可以找找leetcode上关于栈的算法题做做,深刻感受一下哈!

结尾彩蛋

如果本篇博客对您有一定的帮助,大家记得
留言+点赞+收藏
呀。原创不易,转载请联系Build哥!

标签: none

添加新评论