欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java栈之链式栈存储结构的实现代码

程序员文章站 2024-03-31 15:26:10
java栈之链式栈存储结构实现 一、链栈 采用单链表来保存栈中所有元素,这种链式结构的栈称为链栈。 二、栈的链式存储结构实现 package com.iet...

java栈之链式栈存储结构实现

一、链栈

采用单链表来保存栈中所有元素,这种链式结构的栈称为链栈。

二、栈的链式存储结构实现

package com.ietree.basic.datastructure.stack;

/**
 * 链栈
 *
 * created by ietree
 * 2017/4/29
 */
public class linkstack<t> {

  // 定义一个内部类node,node实例代表链栈的节点
  private class node {

    // 保存节点的数据
    private t data;
    // 指向下个节点的引用
    private node next;
    // 无参构造器
    public node() {
    }
    // 初始化全部属性的构造器
    public node(t data, node next) {

      this.data = data;
      this.next = next;

    }

  }
  // 保存该链栈的栈顶元素
  private node top;
  // 保存该链栈中已包含的节点数
  private int size;
  // 创建空链栈
  public linkstack() {
    // 空链栈,top的值为null
    top = null;

  }

  // 以指定数据元素来创建链栈,该链栈只有一个元素
  public linkstack(t element) {

    top = new node(element, null);
    size++;

  }

  // 返回链栈的长度
  public int length() {

    return size;

  }

  // 进栈
  public void push(t element) {

    // 让top指向新创建的元素,新元素的next引用指向原来的栈顶元素
    top = new node(element, top);
    size++;

  }

  // 出栈
  public t pop() {

    node oldtop = top;
    // 让top引用指向原栈顶元素的下一个元素
    top = top.next;
    // 释放原栈顶元素的next引用
    oldtop.next = null;
    size--;
    return oldtop.data;

  }

  // 访问栈顶元素,但不删除栈顶元素
  public t peek(){

    return top.data;

  }

  // 判断链栈是否为空栈
  public boolean empty() {

    return size == 0;

  }

  // 请空链栈
  public void clear() {

    top = null;
    size = 0;

  }

  public string tostring() {

    // 链栈为空栈时
    if (empty()) {

      return "[]";

    } else {

      stringbuilder sb = new stringbuilder("[");
      for (node current = top; current != null; current = current.next) {

        sb.append(current.data.tostring() + ", ");

      }

      int len = sb.length();
      return sb.delete(len - 2, len).append("]").tostring();
    }

  }

}

测试类:

package com.ietree.basic.datastructure.stack;

/**
 * created by ietree
 * 2017/4/29
 */
public class linkstacktest {

  public static void main(string[] args) {

    linkstack<string> stack = new linkstack<string>();

    stack.push("aaaa");
    stack.push("bbbb");
    stack.push("cccc");
    stack.push("dddd");
    system.out.println(stack);

    system.out.println("访问栈顶元素:" + stack.peek());

    system.out.println("第一次弹出栈顶元素:" + stack.pop());

    system.out.println("第二次弹出栈顶元素:" + stack.pop());

    system.out.println("两次pop之后的栈:" + stack);

  }

}

程序输出:

[dddd, cccc, bbbb, aaaa]
访问栈顶元素:dddd
第一次弹出栈顶元素:dddd
第二次弹出栈顶元素:cccc
两次pop之后的栈:[bbbb, aaaa]

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!