java基础之-----初识栈

待我称王封你为后i 2022-12-30 10:36 203阅读 0赞

### 初识栈和队列 ###

*  栈
 *   *  LinkedList类中的栈操作方法
     *  ArrayDeque中的栈操作
     *  ArrayDeque特点

# 栈 #

栈是之中基本数据结构，具有先进后出的特性。  
在java中的栈结构实现。

//vactor已经被ArrayList替代了，Stack也不建议使用了
    class Stack<E> extends Vector<E> { }

Deque接口

//可以使用LinkedList类中的栈操作方法---底层使用双向链表
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    
    //也可以使用ArrayDeque中的栈操作方法---底层使用数组
    public class ArrayDeque<E> extends AbstractCollection<E>
                               implements Deque<E>, Cloneable, Serializable

## LinkedList类中的栈操作方法 ##

对于栈的主要操作有四个：  
1.push()—进栈/压栈：向栈中添加元素 @since 1.6  
2.peek()—弹栈：返回栈顶的值，但不删除该元素 @since 1.5  
3.pop()—出栈：返回栈顶的值，并删除该元素 @since 1.6  
4.isEmpty()—判空：判断栈是否为空  
源码浅析：  
1.push()—进栈/压栈：向栈中添加元素

//进栈
    public void push(E e) { 
            addFirst(e);  //此处调用了addFirst()方法
        }
    //将指定的元素插入此列表的开头。
    public void addFirst(E e) { 
            linkFirst(e); //此处调用了linkFirst()方法
        }
    //将e链接为第一个元素--即头插法
    //这里为什么要用头插法呢，因为通过头插法，元素是按插入顺序倒序排列的，出栈的时候从头结点顺序弹出即可
    private void linkFirst(E e) { 
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

2.peek()—弹栈：返回栈顶的值，但不删除该元素

public E peek() { 
        final Node<E> f = first; //这里的first始终指向链表的第一个节点
        return (f == null) ? null : f.item;
    }

3.pop()—出栈：返回栈顶的值，并删除该元素

//弹栈
        public E pop() { 
            return removeFirst();
        }
    //从此列表中删除并返回第一个元素。
        public E removeFirst() { 
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
    //取消链接非空的第一个节点f.
        private E unlinkFirst(Node<E> f) { 
            // assert f == first && f != null;
            final E element = f.item;    //拿到节点的值
            final Node<E> next = f.next; //拿到指向下一个节点的地址
            f.item = null;   //把值置空
            f.next = null;   // 把指向下一个节点的地址值置空，这两步操作有助于GC回收废弃空间
            first = next;    //头结点指针后移
            if (next == null)      //判断是否为尾结点，是：尾指针置空，否：头节点前指针置空
                last = null;	   
            else	
                next.prev = null;
            size--;
            modCount++;
            return element;
        }

4.isEmpty()—判空：判断栈是否为空  
这个有点绕弯弯，我来给你捋一捋  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70]

首先：collection接口中定义了一个（以LinkedList实现类为主线）
    collection------>boolean isEmpty();
    它有两个小弟List和AbstractCollection其中都有
    List（接口）---->boolean isEmpty();
    AbstractCollection（抽象类）------->实现了
        public boolean isEmpty() { 
            return size() == 0;
        }
    之后AbstractList又继承了AbstractCollection并且实现了List
    
    public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> 
    但是在其中并没有再重写isEmpty()方法。
    
    再看LinkedList的上司
    public abstract class AbstractSequentialList<E> extends AbstractList<E> 
    
    就这样AbstractCollection实现的isEmpty()方法一脉单传到了LinkedList手里。
    
    成为了它判空的方法。

动手小练习----MyLinkedList实现栈操作。

public class MyLinkedList2<T>  { 
        //首先创建一个双向节点
        private class Node<T>{ 
            private T value;
            private Node<T> prev;
            private Node<T> next;
            public Node(Node<T> prev,T value,Node<T> next){ 
                this.prev = prev;
                this.value = value;
                this.next = next;
            }
        }
    
        //声明链表中的必需要素
        private Node<T> first; //始终指向头结点的指针
        private Node<T> last;  //始终指向尾结点的指针
        private int size;      //代表链表的长度
    
        //实现栈操作
        //1.入栈---使用头插法向链表汇总插入元素
        public void push(T e){ 
            //获取头结点
            final Node<T> f = first;
            //新建一个节点，把元素装进去
            final Node<T> newNode = new Node<>(null,e,f);
            //因为是头插法，现在first要指向最新的节点了
            first = newNode;
            //判断是否是空链表
            if(f == null){ 
                last = newNode;  //是的话尾结点指向插入的第一个节点
            }else { 
                f.prev = newNode; //非空节点的话把之前头节点的前指针指向新插入的节点，完成节点拼接
            }
            size++;
        }
        //2.出栈---返回链表的第一个节点(返回栈顶的值，但不删除该元素)
        public T peek(){ 
            final Node<T> f = first;
            return (f==null) ? null : f.value;
        }
        //3.出栈--返回链表的第一个非空节点，并删除该节点的值(返回栈顶的值，并删除该元素)
        public T pop(){ 
            final Node<T> f= first;
            final T element;
            if (f == null){ 
                throw new NoSuchElementException();
            }else { 
                element = f.value;
                final Node<T>  next = f.next;
                f.value = null;
                f.next = null;
                first = next;
                if (next == null){ 
                    last = next;
                }else { 
                    next.prev = null;
                }
                size--;
            }
            return element;
        }
        //4.栈的判空
        public boolean isEmpty(){ 
            return size == 0;
        }
    
        public static void main(String[] args) { 
            MyLinkedList2<Object> stack = new MyLinkedList2<>();
            stack.push("A");
            stack.push("B");
            stack.push("C");
            System.out.println(stack.peek());
            System.out.println(stack.pop());
            System.out.println(stack.peek());
            System.out.println(stack.pop());
            System.out.println(stack.isEmpty());
        }
    
    }

## ArrayDeque中的栈操作 ##

public class ArrayDeque<E> extends AbstractCollection<E>
                               implements Deque<E>, Cloneable, Serializable

同样的四个方法：  
push()，peek()，pop()，isEmpty()

0.因为ArrayDeque底层实现是数组，所以在ArrayDeque中用到了以下几个变量：

**1）transient Object\[\] elements;**

JDK1.81中对该变量的注释

/** * The array in which the elements of the deque are stored. * The capacity of the deque is the length of this array, which is * always a power of two. The array is never allowed to become * full, except transiently within an addX method where it is * resized (see doubleCapacity) immediately upon becoming full, * thus avoiding head and tail wrapping around to equal each * other. We also guarantee that all array cells not holding * deque elements are always null. */

直译过来是这样婶的

*用于存储双端队列的元素的数组。 双端队列的容量是此数组的长度，始终为2的幂。除非在addX方法中短暂地改变数组的大小（请参见doubleCapacity），在数组变满后立即对其进行大小调整（请参阅doubleCapacity），否则该数组永远不允许填充，从而避免了头和尾彼此缠绕而彼此相等。我们还保证所有不包含双端队列元素的数组单元始终为空。*

**2）transient int head;**

/** * The index of the element at the head of the deque (which is the * element that would be removed by remove() or pop()); or an * arbitrary number equal to tail if the deque is empty. */

*位于双端队列开头的元素的索引（这是*元素，将由remove（）或pop（）删除）；如果双端队列为空，则为*等于tail的任意数字*

**3）transient int tail;**

/** * The index at which the next element would be added to the tail * of the deque (via addLast(E), add(E), or push(E)). */

*下一个元素将被添加到双端队列的末尾处的索引（通过addLast（E），add（E）或push（E））*

**1.push()方法**  
将一个元素压入由这个deque容器表示的栈中。换句话说，在这个deque容器的前面插入元素。  
//这里有点绕，可以点下面的连接学习下，我自己也没太搞懂就不误人子弟了

public void push(E e) { 
            addFirst(e);
        }
        //将指定的元素插入此双端队列的前面。
         public void addFirst(E e) { 
         if (e == null)
             throw new NullPointerException();
         
         elements[head = (head - 1) & (elements.length - 1)] = e;
         if (head == tail)
             doubleCapacity();
         }
         //此双容器的容量加倍。只在满的时候调用，也就是说，当头和尾已经成相等的时候。
        private void doubleCapacity() { 
            assert head == tail;
            int p = head;
            int n = elements.length;
            int r = n - p; // number of elements to the right of p
            int newCapacity = n << 1;
            if (newCapacity < 0)
                throw new IllegalStateException("Sorry, deque too big");
            Object[] a = new Object[newCapacity];
            System.arraycopy(elements, p, a, 0, r);
            System.arraycopy(elements, 0, a, r, p);
            elements = a;
            head = 0;
            tail = n;
        }

[ArrayDeque辅助链接][ArrayDeque]

**2）peek()方法**

public E peek() { 
            return peekFirst();
        }
        
        @SuppressWarnings("unchecked")
        public E peekFirst() { 
            // elements[head] is null if deque empty
            return (E) elements[head];
        }

**3）pop()方法**

public E pop() { 
            return removeFirst();
        }
        /** * @throws NoSuchElementException {@inheritDoc} */
        public E removeFirst() { 
            E x = pollFirst();
            if (x == null)
                throw new NoSuchElementException();
            return x;
        }
        public E pollFirst() { 
            int h = head;
            @SuppressWarnings("unchecked")
            E result = (E) elements[h];
            // Element is null if deque empty
            if (result == null)
                return null;
            elements[h] = null;     // Must null out slot
            head = (h + 1) & (elements.length - 1);
            return result;
        }

4)isEmpty()方法

public boolean isEmpty() { 
            return head == tail;
        }

这个难度太大，我没法自己实现了。

## ArrayDeque特点 ##

ArrayDeque是Deque接口的一个实现，使用了可变数组，所以没有容量上的限制。  
ArrayDeque是线程不安全的，在没有外部同步的情况下，不能再多线程环境下使用。  
ArrayDeque是Deque的实现类，可以作为栈来使用，效率高于Stack，也可以作为队列来使用，效率高于LinkedList。  
需要注意的是，ArrayDeque不支持null值。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70]: /images/20221120/7925a6556b5d4c5fa0634eff72dff98c.png
[ArrayDeque]: https://blog.csdn.net/qq_39409110/article/details/85851079