Java-Stack

本章是整理知识内容，为强化知识长期更新。

Stack

• 栈是元素的集合，其包含了两个基本操作：push 操作可以用于将元素压入栈，pop 操作可以将栈顶元素移除。
• 遵循后入先出（LIFO）原则。
• 时间复杂度:
• 索引: O(n)
• 搜索: O(n)
• 插入: O(1)
• 移除: O(1)

Stack

Collection成员之一，继承了Vector，通过重写Vector来实现LIFO（Last-in-First-out 后进先出）特性。

概述

• Java Stack是LIFO对象。它扩展了Vector类。

源码分析Stack

由于方法不多，直接贴整个类代码。Stack只有一个构造方法，也就说维护列队的特性是继承至Vector

public
class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }

    // 将对象推到堆叠顶部。
    public E push(E item) {
        addElement(item);

        return item;
    }

    // 删除堆栈顶部的对象，并返回该对象作为此函数的值。
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    // 查看堆栈顶部的对象，而不将其从堆栈中移除。
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    // 判断Stack是否为空，也就是长度为0的时候。
    public boolean empty() {
        return size() == 0;
    }

    // 返回一个对象在堆栈上的基于1的位置，找不到就返回-1。
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

1、push

@Test
public void test(){
    String[] arr = new String[]{"a","b","c","d"};
    Stack stack = new Stack();
    stack.addAll(Arrays.asList(arr));
    System.out.println(stack);
    stack.push("a");
    System.out.println(stack);
}
// 输出
[a, b, c, d]
[a, b, c, d, a]

2、pop

@Test
public void test1(){
    String[] arr = new String[]{"a","b","c","d"};
    Stack stack = new Stack();
    stack.addAll(Arrays.asList(arr));
    System.out.println(stack);
    stack.pop();
    System.out.println(stack);

}

// 输出
[a, b, c, d]
[a, b, c]

3、peek

@Test
public void test2(){
    String[] arr = new String[]{"a","b","c","d"};
    Stack<String> stack = new Stack();
    stack.addAll(Arrays.asList(arr));
    System.out.println(stack);
    String str = stack.peek();
    System.out.println(str);
    System.out.println(stack);
}
// 输出
[a, b, c, d]
d
[a, b, c, d]

4、search

@Test
public void test3(){
     String[] arr = new String[]{"a","b","c","d"};
        Stack<String> stack = new Stack();
        stack.addAll(Arrays.asList(arr));
        System.out.println(stack);
        Integer index = stack.search("a");
        System.out.println(index);
        index = stack.search("b");
        System.out.println(index);
}

//输出
[a, b, c, d]
4
3