5.基础数据结构-栈

5.基础数据结构-栈

5.1 相关概念

数据结构栈（Stack）是一种特殊的线性表：
????????栈顶（Top）： 栈顶是指栈中最靠近“出口”或“操作端”的那个位置。新元素总是被压入（push）到栈顶，当进行弹出（pop）操作时，也是从栈顶移除元素。因此，栈顶始终指向当前栈内的最后一个加入的元素。

????????栈底（Bottom）： 栈底则是指栈中固定不变的那个位置，通常是在创建栈时初始化的第一个位置，也可以理解为栈中最早加入的那些元素所在的位置。在实际操作中，栈底不发生变化，除非整个栈为空或者重新初始化。

????????后进先出（Last In First Out, LIFO）：

????????最后被压入（push）到栈中的元素将是第一个被弹出（pop）的元素。这意味着在没有其他操作的情况下，栈顶元素总是最后被添加的那一个。
????????受限的插入和删除操作：

????????栈只允许在栈顶进行插入（称为“压入”或"push"操作）和删除（称为“弹出”或"pop"操作）。不能直接访问或修改栈内的中间元素。

5.2 接口

public interface Stock<E> extends Iterable<E> {
    /**
     * @Description 向栈压入元素
     * @Author LY
     * @Param [value] 待压入的值
     * @return boolean 是否成功
     * @Date 2024/1/18 9:53
     **/
    boolean push(E value);

    /**
     * @Description 从栈顶弹出元素
     * @Author LY
     * @return E    如果栈非空，返回栈顶元素，否则返回null
     * @Date 2024/1/18 9:53
     **/
    E pop();

    /**
     * @Description 返回栈顶元素，不弹出
     * @Author LY
     * @return E    如果栈非空，返回栈顶元素，否则返回null
     * @Date 2024/1/18 9:55
     **/
    E peek();

    /**
     * @Description  检查栈是否为空
     * @Author LY
     * @return boolean 空返回true，否则返回false
     * @Date 2024/1/18 9:55
     **/
    boolean isEmpty();
    /**
     * @Description 栈是否满已满
     * @Author LY
     * @return boolean 满 true 否则 false
     * @Date 2024/1/18 11:34
     **/
    boolean isFull();
}

5.3 链表实现

public class LinkedListStock<E> implements Stock<E>{
    public static void main(String[] args) {
        LinkedListStock<Integer>stock=new LinkedListStock<>(2);
        boolean empty1 = stock.isEmpty();
        boolean full1 = stock.isFull();
        boolean push1 = stock.push(1);
        boolean push2 = stock.push(2);
        boolean push3 = stock.push(3);
        boolean empty2 = stock.isEmpty();
        boolean full2 = stock.isFull();
        Integer peek1 = stock.peek();
        Integer pop1 = stock.pop();
        Integer pop2 = stock.pop();
        Integer pop3 = stock.pop();
        Integer peek2 = stock.peek();
    }
    //容量
    private int capatity=Integer.MAX_VALUE;
    //元素个数
    private int size=0;
    private Node head=new Node(null,null);
    public LinkedListStock() {
    }
    public LinkedListStock(int capatity) {
        this.capatity = capatity;
    }
    static  class Node<E>{
        E value;
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }
    @Override
    public boolean push(E value) {
        if(isFull()){
            return false;
        }
        Node node = new Node(value, head.next);
        head.next=node;
        size++;
        return true;
    }
    @Override
    public E pop() {
        if(isEmpty()){
            return null;
        }
        Node<E> first = head.next;
        head.next=first.next;
        size--;
        return first.value;
    }
    @Override
    public E peek() {
        if(isEmpty()){
            return null;
        }
        Node<E> first = head.next;
        return first.value;
    }
    @Override
    public boolean isEmpty() {
        return size==0;
    }
    @Override
    public boolean isFull() {
        return size==capatity;
    }
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p=head;
            @Override
            public boolean hasNext() {
                return p!=null;
            }
            @Override
            public E next() {
                E value = p.value;
                p=p.next;
                return value;
            }
        };
    }
}

..?