大话数据结构六:特殊的线性表(栈)

1. 什么是栈?

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

2. 栈的特点:

1.) 栈又称为后进先出(Last In First out)的线性表,栈元素具有线性关系,即前驱后继关系。

2.) 栈的特殊之处在于:它的栈底是固定的,只允许在栈顶进行插入和删除操作。

3. 栈的顺序存储结构(Java数组实现):

// 栈的数组实现, 底层使用数组:
public class ArrayStack<T> {
    private Object[] arr; // 数组首元素作为栈底,因为它变化小
    private int length;  

    // 数据初始化
    public ArrayStack(){
        arr = new Object[16];
        length = 0;
    }  

    // 元素入栈
    public boolean push(T data) {
        if (length >= arr.length) { // 判断是否需要进行数组扩容
            resize();
        }
        arr[length++] = data;
        return true;
    }  

    // 元素出栈
    @SuppressWarnings("unchecked")
    public T pop() {
        if (length == 0) {
            return null;
        }
        return (T) arr[--length];
    }  

    // 将数组中的数据置为null, 方便GC进行回收
    public void clear() {
        for (int i = 0; i < length; i++) {
            arr[length] = null;
        }
        length = 0;
    }  

    // 数组扩充容量
    private void resize() {
        Object[] temp = new Object[arr.length * 3 / 2 + 1];
        for (int i = 0; i < length; i++) {
            temp[i] = arr[i];
            arr[i] = null;
        }
        arr = temp;
    }  

    // 获取栈中元素个数
    public int length() {
        return length;
    }  

    // 判断数组是否为空
    public boolean isEmpty() {
        return length == 0;
    }  

    // 打印栈中元素
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append(arr[i].toString());
            if (i != length - 1) {
                sb.append(", ");
            }
        }
        return sb.toString();
    }  

    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<Integer>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            stack.push(i); // 入栈
        }
        long temp = System.currentTimeMillis();
        System.out.println("push time: " + (temp - start));
        while (stack.pop() != null){
             ; // 出栈
        }
        System.out.println("pop time: " + (System.currentTimeMillis() - temp));
    }
}

更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

运行时间:
    push time: 257ms
    pop time: 5ms

4. 栈的链式存储结构(Java链表实现):

// 结点元素
public class Node<T> {
    private Node<T> prev; // 记住当前结点的前一结点
    private T data; // 数据域  

    public Node() {
    }  

    public Node(T data, Node<T> prev) {
        this.data = data;
        this.prev = prev;
    }  

    public Node<T> getPrev() {
        return prev;
    }  

    public void setPrev(Node<T> prev) {
        this.prev = prev;
    }  

    public T getData() {
        return data;
    }  

    public void setData(T data) {
        this.data = data;
    }
}
// 栈的链表实现, 底层使用单链表:
public class LinkedStack<T> {
    private Node<T> top; // 栈顶指针(链表尾结点)
    private int size; // 栈的长度  

    // 数据初始化
    public LinkedStack() {
        top = null;
        size = 0;
    }  

    // 结点入栈
    public boolean push(T data) {
        Node<T> newNode = new Node<T>(data,top); // 将top设置为新节点的前驱结点
        top = newNode; // 将新结点设置为栈顶指针
        size++;
        return true;
    }  

    // 结点出栈
    public T pop() {
        if (top != null) {
            Node<T> tempNode = top;
            top = top.getPrev(); // 将栈顶指针的前驱结点设置为栈顶指针
            size--;
            return tempNode.getData();
        }
        return null;
    }  

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

    // 获取栈的长度
    public int length() {
        return size;
    }  

    // 打印栈中元素
    public String toString() {
        Node<T> node = top;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            sb.append(node.getData().toString());
            if (i != size - 1) {
                sb.append(", ");
            }
            node = node.getPrev();
        }
        return sb.reverse().toString();
    }  

    public static void main(String[] args) {
        LinkedStack<Integer> stack = new LinkedStack<Integer>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            stack.push(i); // 入栈
        }
        long temp = System.currentTimeMillis();
        System.out.println("push time: " + (temp - start));
        while (stack.pop() != null){
            ;  // 出栈
        }
        System.out.println("pop time: " + (System.currentTimeMillis() - temp));
    }
}
运行时间:
    push time: 986ms
    pop time: 15ms

5. 两种实现方式比较:

通过入栈和出栈时间比较可以看出,数组实现在性能上还是有明显优势的,这是因为数组实现的栈在增加和删除元素时并不需要移动大量的元素,只是在扩大数组容量时,需要进行拷贝。然而链表实现的栈在入栈时需要将数据包装成Node,出栈时需要从Node中取出数据,同时还要维护栈顶指针和前驱指针。

6. JDK API中的栈:

1.) java.util.Stack: 一个普通的顺序栈,底层基于数组实现。这个类是线程安全的。
2.) java.util.LinkedList: 一个双向链表,线程不安全,可以当做栈来使用。在多线程环境下可以使用Collections类的工具方法将其改造成线程安全类。

3.) 两个类都提供了push(),pop(),peek()等方法。

作者:csdn博客 zdp072

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索数组
, 顺序栈
, return
, 线性时间选择
, 结点
, 元素
, public
, length
, 出栈顺序
, pop打印
, 链式栈
出栈
,以便于您获取更多的相关知识。

时间: 2016-12-30

大话数据结构六:特殊的线性表(栈)的相关文章

c++-C++数据结构与算发线性表List问题。

问题描述 C++数据结构与算发线性表List问题. 看<数据结构与算法分析>,用书上的代码创建线性表的顺序表. 可是编译出现错误,求解答. AList.h #include <list> template < class Elem > class AList : public List<Elem> { private: int maxSize; int listSize; int fence; Elem* listArray; public: AList(i

c++的问题-数据结构(线性表)不知道怎么弄啊!!!

问题描述 数据结构(线性表)不知道怎么弄啊!!! 刚刚开始学数据结构 这个基本的线性表 感觉好像看不懂 求高手讲解一下线性表的建立嘛. 解决方案 线性表有两种方式,数组和链表,链表又分为单链表.双链表. 具体你找一本数据结构的教材,先把基础的看一看.

大话数据结构五:线性表的链式存储结构(双向链表)

1. 双向链表:在单链表的每个结点中,再设置一个指向其前驱结点的指针域,那么在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱. 2. 单链表和双向链表比较: 单链表:总是要从头到尾找结点,只能正遍历,不能反遍历. 双向链表: 可以从头找到尾,也可以从尾找到头,即正反遍历都可以,可以有效提高算法的时间性能,但由于每个结点需要记录两份指针,所以在空间占用上略多一点,这就是通过空间来换时间. 3. Java实现双向链表: // 双向链表 public class DoubleLi

大话数据结构四:线性表的链式存储结构(单向循环链表)

1. 单向循环链表:将单链表尾结点的指针端由空指针改为指向头结点,使整个单链表形成一个环,这种头尾相接的单链表称为单向循环链表.   2. 单向循环链表和单链表实现的区别: 1.)添加一个结点到单向循环链表末尾时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为null. 2.)判断是否到达表尾时,单向循环链表可以判断该结点是否指向头结点,单链表只需要知道是否为null.   3.Java实现单向循环链表: // 单向循环链表 public class CircularLinked

大话数据结构二:线性表的链式存储结构(单链表)

1. 线性表的链式存储结构:指的是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的,这就意味着这些数据元素可以存在内存未被占用的任意位置. 2. 结点:结点由存放数据元素的数据域和存放后继结点地址的指针域组成. 1.)顺序存储结构中,每个数据元素只需要存数据元素的信息就可以了. 2.)链式存储结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址. 3.)链表中第一个结点叫头结点,它的存储位置叫做头指针,它的数据域可以不存储任何信息,链表的最后一个结

数据结构教程 第六课 线性表的顺序表示和实现

本课主题: 线性表的顺序表示和实现 教学目的: 掌握线性表的顺序表示和实现方法 教学重点: 线性表的顺序表示和实现方法 教学难点: 线性表的顺序存储的实现方法 授课内容: 复习 1.存储结构 逻辑结构   "数据结构"定义中的"关系"指数据间的逻辑关系,故也称数据结构为逻辑结构. 存储结构   数据结构在计算机中的表示称为物理结构.又称存储结构. 顺序存储结构 链式存储结构 2.线性表的类型定义 一.线性表的顺序表示 用一组地址连续的存储单元依次存储线性表的数据元素

大话数据结构之三:线性表

1.定义: 线性表表示0个或者多个数据元素的有限序列 线性表的特性有: 除第一个元素外,每一个元素均有一个直接前驱 出最后一个元素外,每一个元素均有一个直接后继 2.线性表抽象数据类型 ADT List  Data          /*线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType.其中,除第一个元素a1外,   每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素.   数据元素直接是一对一的关系.*/  Op

大话数据结构一:线性表的顺序存储结构

1. 线性表的顺序存储结构:指的是用一段地址连续的存储单元依次存储线性表的数据元素. 2. Java实现线性表的顺序存储结构: // 顺序存储结构 public class SequenceList { private static final int DEFAULT_SIZE = 10; // 默认初始化数组大小 private int size; // 当前数组大小 private static Object[] array; public SequenceList() { init(DEF

数据结构的C++实现之线性表之顺序存储结构

线性表的数据对象集合为 {a1,a2,....an},每个元素的类型均为Datatype.其中,除第一个元素a1外,每一个元素有且 只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素.数据元素之间的关系是一对一的 关系. 线性表的顺序存储结构的优缺点: 优点:无须为表示表中元素之间的逻辑关系而增加额外的存储空间:可以快速地存取表中任一位置的元素O(1) 缺 点:插入和删除操作需要移动大量元素O(n):当线性表长度变化较大时,难以确定存储空间的容量:造成存储空间的"碎