专栏首页曾大稳的博客栈(Stack源码分析)

栈(Stack源码分析)

栈(stack)

  1. 从数据结构的角度理解:是一组数据的存放方式,特点为LIFO,即后进先出(Last in, first out)。在这种数据结构中,数据像积木那样一层层堆起来,后面加入的数据就放在最上层。使用的时候,最上层的数据第一个被用掉,这就叫做”后进先出”。
    1. 从代码运行方式角度理解:是调用栈,表示函数或子例程像堆积木一样存放,以实现层层调用。程序运行的时候,总是先完成最上层的调用,然后将它的值返回到下一层调用,直至完成整个调用栈,返回最后的结果。
    2. 从内存区域的角度上理解:是存放数据的一种内存区域。程序运行的时候,需要内存空间存放数据。一般来说,系统会划分出两种不同的内存空间:一种叫做stack(栈),另一种叫做heap(堆)。 参考链接:Stack的三种含义

(图片均来源于网络)


本文所述是站在数据结构的角度。 栈可以通过链表和数组实现,先看通过数组实现的方式。

可以通过查看Stack源码学习

可以看到StackVector的子类,Vector本身是一个可增长的线程安全的对象数组( a growable array of objects)

里面主要是如下方法

E push(E item)   
         把项压入堆栈顶部。   
E pop()   
         移除堆栈顶部的对象,并作为此函数的值返回该对象。   
E peek()   
         查看堆栈顶部的对象,但不从堆栈中移除它。   
boolean empty()   
         测试堆栈是否为空。    
int search(Object o)   
         返回对象在堆栈中的位置,以 1 为基数。

push

/**
    * Pushes an item onto the top of this stack. This has exactly
    * the same effect as:
    * <blockquote><pre>
    * addElement(item)</pre></blockquote>
    *
    * @param   item   the item to be pushed onto this stack.
    * @return  the <code>item</code> argument.
    * @see     java.util.Vector#addElement
    */
   public E push(E item) {
       addElement(item);

       return item;
   }

就是调用了VectoraddElement

/**
     * Adds the specified component to the end of this vector,
     * increasing its size by one. The capacity of this vector is
     * increased if its size becomes greater than its capacity.
     *
     * <p>This method is identical in functionality to the
     * {@link #add(Object) add(E)}
     * method (which is part of the {@link List} interface).
     *
     * @param   obj   the component to be added
     */
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

/**
     * This implements the unsynchronized semantics of ensureCapacity.
     * Synchronized methods in this class can internally call this
     * method for ensuring capacity without incurring the cost of an
     * extra synchronization.
     *
     * @see #ensureCapacity(int)
     */
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

就是判断是否扩容,然后赋值即可

poppeek

/**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

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

        return obj;
    }

 /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

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

Vector

 /**
     * Deletes the component at the specified index. Each component in
     * this vector with an index greater or equal to the specified
     * {@code index} is shifted downward to have an index one
     * smaller than the value it had previously. The size of this vector
     * is decreased by {@code 1}.
     *
     * <p>The index must be a value greater than or equal to {@code 0}
     * and less than the current size of the vector.
     *
     * <p>This method is identical in functionality to the {@link #remove(int)}
     * method (which is part of the {@link List} interface).  Note that the
     * {@code remove} method returns the old value that was stored at the
     * specified position.
     *
     * @param      index   the index of the object to remove
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }
    
/**
     * Returns the component at the specified index.
     *
     * <p>This method is identical in functionality to the {@link #get(int)}
     * method (which is part of the {@link List} interface).
     *
     * @param      index   an index into this vector
     * @return     the component at the specified index
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }

        return elementData(index);
    }

@SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

先调用peek()得到需要出栈的对象,也就是数组顶部的对象,在调用VectorremoveElementAt移除。

empty

/**
     * Tests if this stack is empty.
     *
     * @return  <code>true</code> if and only if this stack contains
     *          no items; <code>false</code> otherwise.
     */
    public boolean empty() {
        return size() == 0;
    }

search

/**
     * Returns the 1-based position where an object is on this stack.
     * If the object <tt>o</tt> occurs as an item in this stack, this
     * method returns the distance from the top of the stack of the
     * occurrence nearest the top of the stack; the topmost item on the
     * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
     * method is used to compare <tt>o</tt> to the
     * items in this stack.
     *
     * @param   o   the desired object.
     * @return  the 1-based position from the top of the stack where
     *          the object is located; the return value <code>-1</code>
     *          indicates that the object is not on the stack.
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

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

参考链接: java.util.Stack类简介


接下来看看使用链式的方式实现

代码表示:

 private Node top = null;
private int number = 0;

class Node {
    public T Item;
    public Node Next;
}

入栈:将top的指向换为入栈的对象,然后将这个入栈的对象指向上一个入栈的对象即可。

代码表示:

public void push(T node) {
        Node oldFirst = top;
        top = new Node();
        top.Item = node;
        top.Next = oldFirst;
        number++;
    }

出栈:根据出栈的对象得到next,然后top指向即可。 代码表示:

public T pop() {
       T item = top.Item;
       top = top.Next;
       number--;
       return item;
   }

一个伪代码类表示:

/**
 * Created by zzw on 2017/6/27.
 * Version:
 * Des:
 */

public class StackLinkedList<T> {

    private Node top = null;
    private int number = 0;

   class Node {
        public T Item;
        public Node Next;
    }

    public void push(T node) {
        Node oldFirst = top;
        top = new Node();
        top.Item = node;
        top.Next = oldFirst;
        number++;
    }

    public T pop() {
        T item = top.Item;
        top = top.Next;
        number--;
        return item;
    }
}

参考连接: 浅谈算法和数据结构: 一 栈和队列


水平有限,文中有什么不对或者有什么建议希望大家能够指出,谢谢!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 线性表(ArrayList 和 LinkedList源码分析)

    线性表(linear list) 是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。

    曾大稳
  • LinkedHashMap和LruCache源码分析

    LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashMap的...

    曾大稳
  • HashMap源码分析

    HashMap是一个很经典的键值对集合,从它的广泛应用程度和源码的学习角度上我们不得不去解析它。 我们先看一下HashMap的存储结构((图片均来源于网络)),...

    曾大稳
  • 【Gym 100733D】Little thief Shi(取数,DP)

    Shi realized that he was almost out of money, even renting Shitalian lands. Shi ...

    饶文津
  • IOS5开发-控件位置适应屏幕旋转代码

    - (void)willRotateToInterfaceOrientation:(UIInterfaceOrientation)toOrientation  ...

    阿新
  • How delta works

    Most existing big data storages based on HDFS are lack of feature upsert(if exis...

    用户2936994
  • CornerNet: 成对关键点物体检测 | CSDN博文精选

    5、用于Grouping Corners的 embedding vector的工作原理

    AI科技大本营
  • HDU 1506 Largest Rectangle in a Histogram(单调栈)

    attack
  • 从非二进制约束到二进制约束的正式验证转换(CS PL)

    在约束编程社区中众所周知,任何非二进制约束满足问题(具有有限域)都可以转换为等效的二进制约束问题。隐藏变量编码是最著名的翻译之一。在本文中,我们在证明助手Coq...

    啊瓜7706942
  • @Scheduled注解各参数详解

    该参数接收一个cron表达式,cron表达式是一个字符串,字符串以5或6个空格隔开,分开共6或7个域,每一个域代表一个含义。

    lyb-geek

扫码关注云+社区

领取腾讯云代金券