但行好事  莫问前程

自己实现集合框架(十一):链式栈的实现

这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和java集合有个大概的了解。当然实现没有java集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。

一.链式栈

采用链式储存结构的栈叫做链式栈,采用单链表来实现。单链表的第一个结点为栈顶结点,设top指向栈顶结点,入栈操作是在当前栈顶结点之前插入新的结点;出栈操作是删除当前栈顶结点并返回栈顶元素值,再使top指向新的栈顶结点。链式栈的空栈(a)入栈操作(b)出栈操作(c)如下图示所示:

二.链式栈的实现

1. 定义链式栈

前面文章自己实现集合框架(九):栈接口介绍了栈接口的定义,链式栈类LinkedStack实现栈接口SStack,并实现栈接口中定义的方法,代码如下所示:

package org.light4j.dataStructure.linearList.stack.link;

import org.light4j.dataStructure.linearList.Node;
import org.light4j.dataStructure.linearList.stack.SStack;

/**
 * 链式栈
 * 
 * @author longjiazuo
 * 
 * @param <E>
 */
public class LinkedStack<E> implements SStack<E> {
    private Node<E> top;// 栈顶元素结点

    public LinkedStack() {
        this.top = null;
    }
}

代码解释:

链式栈实现栈接口类SStack,但不能继承前面实现的单链表类SinglyLinkedList,因为栈不支持线性表在任意位置的插入和删除操作。

2. 判断栈是否为空

   /**
     * 判断栈是否为空,若为空则返回true
     * 
     * @return
     */
    @Override
    public boolean isEmpty() {
        return this.top == null;
    }

代码解释

链式栈是否为空栈的依据是判断栈顶结点是否为空。

3. 入栈

     /**
     * 元素入栈,成为新的栈顶元素,若操作成功返回true
     */
    @Override
    public boolean push(E element) {
        if (element == null) {// 空对象不能入栈
            return false;
        }
        this.top = new Node<E>(element, this.top);// 新的元素作为栈顶元素,原来的栈顶元素作为其后继元素
        return true;
    }

代码解释:

top指向栈顶结点,入栈操作是在当前栈顶结点之前插入新的结点。

4.出栈

    /**
     * 元素出栈,返回当前栈顶元素,栈顶元素改变,若栈为空则返回null
     */
    @Override
    public E pop() {
        if (!isEmpty()) {// 判断是否为空空栈
            E temp = this.top.data;// 取栈顶元素
            this.top = this.top.next;// 删除原来的栈顶结点,改变栈顶元素
            return temp;// 返回原来的栈顶元素值
        }
        return null;
    }

代码解释:

出栈操作是删除当前栈顶结点并返回栈顶元素值,再使top指向新的栈顶结点。

5. 取栈顶元素值

      /**
     * 取栈顶元素值,元素未出栈,栈顶元素未改变
     */
    @Override
    public E get() {
        if (!isEmpty()) {// 判断是否为空栈
            return this.top.data;// 返回栈顶元素值
        }
        return null;
    }

6.重写toString()方法

     /**
     * 返回栈中各元素的字符串表示
     */
    @Override
    public String toString() {
        String str = "(";
        Node<E> p = this.top;// 新建一个结点指向栈顶结点top
        while (p != null) {
            if (p.next == null) {// 判断是否有后继结点
                str += p.data;
            } else {
                str += p.data + ",";
            }
            p = p.next;
        }
        return str + ")";
    }

三. 测试

package org.light4j.dataStructure.linearList.stack.link;

import org.light4j.dataStructure.linearList.stack.SStack;

public class Test {
    public static void main(String[] args) {
        SStack<String> stack = new LinkedStack<String>();
        System.out.println(stack.isEmpty());//判空
        stack.push("A");//入栈
        stack.push("B");
        stack.push("C");
        System.out.println(stack.toString());
        stack.pop();// 出栈
        stack.push("D");
        stack.get();// 取栈顶元素
        System.out.println(stack.toString());
        System.out.println(stack.isEmpty());//判空
    }
}

运行结果如下图所示:

四.时间复杂度分析

栈的入栈,出栈操作都在栈顶进行,不需要遍历单链表,所以栈的入栈操作push(),出栈操作pop()和取栈顶元素get()的时间复杂度都是O(1)

五.源代码示例

github地址:点击查看
码云地址:点击查看

打赏
欢迎关注人生设计师的微信公众账号
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(十一):链式栈的实现

分享到:更多 ()

人生设计师-接受不同的声音

联系我关于我