`
maosheng
  • 浏览: 566179 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Stack 的实现原理深入剖析

    博客分类:
  • Java
阅读更多
Stack 介绍:

Stack是栈。它的特性是:先进后出(FILO, First In Last Out)。

java工具包中的Stack是继承于Vector(矢量队列)的,由于Vector是通过数组实现的,这就意味着,Stack也是通过数组实现的,而非链表。当然,我们也可以将LinkedList当作栈来使用

Stack 的继承关系:

java.lang.Object
↳     java.util.AbstractCollection<E>
   ↳     java.util.AbstractList<E>
       ↳     java.util.Vector<E>
           ↳     java.util.Stack<E>

public class Stack<E> extends Vector<E> {}

由于Stack和继承于Vector,因此它也包含Vector中的全部API

Stack 构造函数:

Stack只有一个默认构造函数,如下:

Stack()

Stack 源码解析:

package java.util;

public
class Stack<E> extends Vector<E> {
    // 版本ID。这个用于版本升级控制,这里不须理会!
    private static final long serialVersionUID = 1224463164541339165L;

    // 构造函数
    public Stack() {
    }

    // push函数:将元素存入栈顶
    public E push(E item) {
        // 将元素存入栈顶。
        // addElement()的实现在Vector.java中
        addElement(item);

        return item;
    }

    // pop函数:返回栈顶元素,并将其从栈中删除
    public synchronized E pop() {
        E    obj;
        int    len = size();

        obj = peek();
        // 删除栈顶元素,removeElementAt()的实现在Vector.java中
        removeElementAt(len - 1);

        return obj;
    }

    // peek函数:返回栈顶元素,不执行删除操作
    public synchronized E peek() {
        int    len = size();

        if (len == 0)
            throw new EmptyStackException();
        // 返回栈顶元素,elementAt()具体实现在Vector.java中
        return elementAt(len - 1);
    }

    // 栈是否为空
    public boolean empty() {
        return size() == 0;
    }

    // 查找“元素o”在栈中的位置:由栈底向栈顶方向数
    public synchronized int search(Object o) {
        // 获取元素索引,elementAt()具体实现在Vector.java中
        int i = lastIndexOf(o);

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

总结:

(1) Stack实际上也是通过数组去实现的。
       执行push时(即,将元素推入栈中),是通过将元素追加的数组的末尾中。
       执行peek时(即,取出栈顶元素,不执行删除),是返回数组末尾的元素。
       执行pop时(即,取出栈顶元素,并将该元素从栈中删除),是取出数组末尾的元素,然后将该元素从数组中删除。

(2) Stack继承于Vector,意味着Vector拥有的属性和功能,Stack都拥有。

 
Stack 使用示例:

import java.util.Stack;
import java.util.Iterator;
import java.util.List;

/**
* @desc Stack的测试程序。测试常用API的用法
*
* @author maosheng
*/
public class StackTest {

    public static void main(String[] args) {
        Stack stack = new Stack();
        // 将1,2,3,4,5添加到栈中
        for(int i=1; i<6; i++) {
            stack.push(String.valueOf(i));
        }

        // 遍历并打印出该栈
        iteratorThroughRandomAccess(stack) ;

        // 查找“2”在栈中的位置,并输出
        int pos = stack.search("2");
        System.out.println("the postion of 2 is:"+pos);

        // pup栈顶元素之后,遍历栈
        stack.pop();
        iteratorThroughRandomAccess(stack) ;

        // peek栈顶元素之后,遍历栈
        String val = (String)stack.peek();
        System.out.println("peek:"+val);
        iteratorThroughRandomAccess(stack) ;

        // 通过Iterator去遍历Stack
        iteratorThroughIterator(stack) ;
    }

    /**
     * 通过快速访问遍历Stack
     */
    public static void iteratorThroughRandomAccess(List list) {
        String val = null;
        for (int i=0; i<list.size(); i++) {
            val = (String)list.get(i);
            System.out.print(val+" ");
        }
        System.out.println();
    }

    /**
     * 通过迭代器遍历Stack
     */
    public static void iteratorThroughIterator(List list) {

        String val = null;
        for(Iterator iter = list.iterator(); iter.hasNext(); ) {
            val = (String)iter.next();
            System.out.print(val+" ");
        }
        System.out.println();
    }

}















分享到:
评论

相关推荐

    深入剖析Spring Web源码(含一二版)带目录

    《深入剖析Spring Web源码(含一二版)》是一本深度解析Spring Web框架核心机制的书籍,涵盖了Spring MVC和Spring Web的重要源码分析。这本书旨在帮助开发者深入理解Spring Web的工作原理,提升对Spring框架的使用和...

    深入剖析printf函数

    通过上述对printf函数的深入剖析,我们可以发现它不仅仅是一个简单的输出函数,背后涉及到C语言标准库的封装、系统调用机制、汇编语言实现等复杂的计算机科学知识。了解这些知识点,有助于我们更深入地理解程序的...

    STL源码剖析 pdf电子版

    《STL源码剖析》是侯捷先生撰写的一本经典之作,专为深入理解C++标准模板库(Standard Template Library,简称STL)而设。...此外,了解STL的实现原理也有助于调试和优化代码,更好地利用STL提供的强大功能。

    tcpip_stack_v1_2_TCP,IP_TCP_IP_udpmac_UDP_tcp.zip

    本篇文章将深入剖析名为"tcpip_stack_v1_2_TCP,IP_TCP_IP_udpmac_UDP_tcp"的源码,揭示TCP/IP协议栈的工作原理,帮助读者理解网络通信的核心机制。 首先,我们从最底层开始,MAC(Media Access Control)层是数据...

    关于缓冲区(Stack overflow)溢出的资料

    Aleph One在其著名文章《Smashing The Stack For Fun And Profit》中详细解析了堆栈溢出的原理及如何利用这一漏洞。文章中提到,在许多C语言实现中,当函数内的自动变量数组被越界写入时,可以破坏执行堆栈,使函数...

    Reading-and-comprehense-linux-Kernel-network-protocol-stack-master.7z

    《深入理解Linux网络协议栈:2.6版内核源码剖析》 在信息技术领域,Linux内核的网络协议栈是实现操作系统与网络通信的核心组件。对于任何对网络编程、系统优化或者网络设备驱动开发感兴趣的IT专业人士来说,理解...

    STL源码剖析.pdf

    STL源码剖析的重点在于深入理解其底层实现机制和设计原理,这不仅涉及对数据结构和算法的深入探讨,也包括对内存管理、构造函数、析构函数、拷贝构造函数和赋值操作符等关键实现的洞察。在面向对象的编程范式下,STL...

    stl源码剖析

    通过对STL源码的深入剖析,开发者不仅可以提升C++编程技巧,还能学习到软件设计原则和算法实现的精髓,这对于成为高级C++开发者或系统架构师来说是必不可少的。这份“stl源码剖析”资料将是你探索STL世界的一把钥匙...

    STL源码剖析 侯捷

    侯捷先生在书中对SGI版本的STL源码进行了深入剖析,SGI STL是最初的开源实现,对后来的C++标准库产生了深远影响。通过阅读此书,读者可以学习到以下关键知识点: 1. **迭代器(Iterators)**:STL的核心之一,它们...

    STL源码剖析PDF+SGI STL源码

    书中详细解析了STL的核心组件,帮助读者理解其设计思想和实现原理。 首先,STL由四部分组成:容器、迭代器、算法和函数对象。容器如vector、list、deque、set、map等,它们是数据存储的主要方式,各有优缺点,适应...

    STL 源码剖析(完整简体版)

    在《STL源码剖析(完整简体版)》这本书中,作者深入浅出地讲解了STL的内部工作原理,帮助读者掌握STL的高级实现技巧。 首先,我们来了解**STL的核心组件**: 1. **容器(Containers)**:如vector、list、deque、...

    STL源码剖析--侯捷

    侯捷在书中对这些组件的源码进行了深入剖析,帮助读者理解其内部工作原理。 1. 容器:STL中的容器是存储元素的结构,如vector、list、deque、stack、queue、priority_queue和set、multiset、unordered_set、...

    STL源码剖析

    这本书《STL源码剖析》深入探讨了STL的内部实现机制,对于想要了解C++ STL工作原理的开发者来说,是一本非常有价值的参考书。 STL的核心概念包括: 1. **容器(Containers)**:如vector、list、deque、set、map等...

    STL 源码剖析(侯捷著).pdf

    这本书以其深入浅出的讲解方式,为读者揭示了STL背后的实现原理和设计思想,对于想要深入了解C++编程、提升软件开发水平的程序员来说,是一本不可多得的参考书。 STL是C++编程中的一个重要组成部分,它提供了高效且...

    STL 源码剖析 PDF

    侯捷的《STL源码剖析》深入解析了这些概念的实现细节,包括容器的内存布局、算法的优化策略以及函数对象的使用技巧,对理解STL的工作原理和提升C++编程能力大有裨益。通过阅读和学习,开发者能够更好地利用STL来编写...

    STL源码剖析简体中文版.pdf

    - 《STL源码剖析》这本书旨在帮助有一定C++基础的开发者深入了解STL的工作原理和实现细节。 - 通过阅读此书,读者不仅可以学到如何高效地使用STL,还可以掌握泛型编程的技术要点。 - 对于那些希望成为高级C++程序员...

Global site tag (gtag.js) - Google Analytics