Java 实现栈的三种方式

栈：LIFO（后进先出），自己实现一个栈，要求这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()这些基本的方法。

一、采用数组实现栈

提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用Arrays.copyOf()进行扩容

import java.util.Arrays;
/**
 * 数组实现栈
 * @param <T>
 */
class Mystack1<T> {
  //实现栈的数组
  private Object[] stack;
  //数组大小
  private int size;

  Mystack1() {
    stack = new Object[10];//初始容量为10
  }

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

  //返回栈顶元素
  public T peek() {
    T t = null;
    if (size > 0)
      t = (T) stack[size - 1];
    return t;
  }

  public void push(T t) {
    expandCapacity(size + 1);
    stack[size] = t;
    size++;
  }

  //出栈
  public T pop() {
    T t = peek();
    if (size > 0) {
      stack[size - 1] = null;
      size--;
    }
    return t;
  }

  //扩大容量
  public void expandCapacity(int size) {
    int len = stack.length;
    if (size > len) {
      size = size * 3 / 2 + 1;//每次扩大50%
      stack = Arrays.copyOf(stack, size);
    }
  }
}

public class ArrayStack {
  public static void main(String[] args) {
    Mystack1<String> stack = new Mystack1<>();
    System.out.println(stack.peek());
    System.out.println(stack.isEmpty());
    stack.push("java");
    stack.push("is");
    stack.push("beautiful");
    stack.push("language");
    System.out.println(stack.pop());
    System.out.println(stack.isEmpty());
    System.out.println(stack.peek());
  }
}

二、采用链表实现栈

/**
 * 链表实现栈
 *
 * @param <T>
 */
class Mystack2<T> {
  //定义链表
  class Node<T> {
    private T t;
    private Node next;
  }

  private Node<T> head;

  //构造函数初始化头指针
  Mystack2() {
    head = null;
  }

  //入栈
  public void push(T t) {
    if (t == null) {
      throw new NullPointerException("参数不能为空");
    }
    if (head == null) {
      head = new Node<T>();
      head.t = t;
      head.next = null;
    } else {
      Node<T> temp = head;
      head = new Node<>();
      head.t = t;
      head.next = temp;
    }
  }

  //出栈
  public T pop() {
    T t = head.t;
    head = head.next;
    return t;
  }

  //栈顶元素
  public T peek() {
    T t = head.t;
    return t;
  }

  //栈空
  public boolean isEmpty() {
    if (head == null)
      return true;
    else
      return false;
  }
}

public class LinkStack {
  public static void main(String[] args) {
    Mystack2 stack = new Mystack2();
    System.out.println(stack.isEmpty());
    stack.push("Java");
    stack.push("is");
    stack.push("beautiful");
    System.out.println(stack.peek());
    System.out.println(stack.peek());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.isEmpty());
    System.out.println(stack.pop());
    System.out.println(stack.isEmpty());
  }
}

三、采用LinkedList实现栈

push-----addFirst()
pop-------removeFirst()
peek-----getFirst()
isEmpty-isEmpty()

import java.util.LinkedList;

/**
 * LinkedList实现栈
 *
 * @param <T>
 */
class ListStack<T> {
  private LinkedList<T> ll = new LinkedList<>();

  //入栈
  public void push(T t) {
    ll.addFirst(t);
  }

  //出栈
  public T pop() {
    return ll.removeFirst();
  }

  //栈顶元素
  public T peek() {
    T t = null;
    //直接取元素会报异常，需要先判断是否为空
    if (!ll.isEmpty())
      t = ll.getFirst();
    return t;
  }

  //栈空
  public boolean isEmpty() {
    return ll.isEmpty();
  }
}

public class LinkedListStack {
  public static void main(String[] args) {
    ListStack<String> stack = new ListStack();
    System.out.println(stack.isEmpty());
    System.out.println(stack.peek());
    stack.push("java");
    stack.push("is");
    stack.push("beautiful");
    System.out.println(stack.peek());
    System.out.println(stack.pop());
    System.out.println(stack.isEmpty());
    System.out.println(stack.peek());
  }
}

接着分享java使用两种方式实现简单栈

两种栈的不同点

基于数组实现的栈需要指定初始容量，栈的大小是有限的（可以利用动态扩容改变其大小），基于链表实现的栈则是没有大小限制的。

基于数组实现栈

数组实现栈的主要方法就是标识栈顶在数组中的位置，初始化时可以将栈顶指向为-1的虚拟位置，元素入栈则栈顶元素加1，出栈则栈顶元素减一，栈的元素容量为栈顶指针当前位置加1，且不能超过底层数组的最大容量。

/**
 * 以数组为底层实现栈
 * @param <T>
 */
public class MyStackOfArray<T> {
  private Object[] data;//底层数组
  private int maxSize = 0;//栈存储的最大元素个数
  private int top = -1;//初始时栈顶指针指向-1

  //默认初始化容量为10的栈
  public MyStackOfArray(){
    this(10);
  }

  //初始化指定大小的栈
  public MyStackOfArray(int initialSize){
    if(initialSize >= 0){
      this.maxSize = initialSize;
      data = new Object[initialSize];
      top = -1;
    }else{
      throw new RuntimeException("初始化容量不能小于0" + initialSize);
    }
  }

  //入栈，栈顶指针先加一再填入数据
  public boolean push(T element){
    if(top == maxSize - 1){
      throw new RuntimeException("当前栈已满，无法继续添加元素");
    }else{
      data[++top] = element;
      return true;
    }
  }

  //查看栈顶元素
  public T peek(){
    if(top == -1)
      throw new RuntimeException("栈已空");
    return (T) data[top];
  }

  //出栈，先弹出元素再将栈顶指针减一
  public T pop(){
    if(top == -1)
      throw new RuntimeException("栈已空");
    return (T) data[top--];
  }

  //判断当前栈是否为空，只需判断栈顶指针是否等于-1即可
  public boolean isEmpty(){
    return top == -1;
  }

  public int search(T element){
    int i = top;
    while (top != -1){
      if(peek() != element)
        top--;
      else
        break;
    }
    int result = top + 1;
    top = i;
    return top;
  }

  public static void main(String[] args) {
    MyStackOfArray<Integer> myStackOfArray = new MyStackOfArray<>(10);
    for(int i = 0; i < 10; i++){
      myStackOfArray.push(i);
    }
    System.out.println("测试是否执行");
    for(int i = 0; i < 10; i++){
      System.out.println(myStackOfArray.pop());
    }
  }
}

基于链表实现栈

基于链表实现栈只要注意控制栈顶指针的指向即可。

/**
 * 链表方式实现栈
 * @param <E>
 */
public class MyStack<E> {
  /**
   * 内部节点类
   * @param <E>
   */
  private class Node<E>{
    E e;
    Node<E> next;

    public Node(){}

    public Node(E e, Node<E> next){
      this.e = e;
      this.next = next;
    }
  }

  private Node<E> top;//栈顶指针
  private int size;//栈容量

  public MyStack(){
    top = null;
  }

  //入栈，将新节点的next指针指向当前top指针，随后将top指针指向新节点
  public boolean push(E e){
    top = new Node(e, top);
    size++;
    return true;
  }

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

  //返回栈顶节点
  public Node<E> peek(){
    if(isEmpty())
      throw new RuntimeException("栈为空");
    return top;
  }

  //出栈，先利用临时节点保存要弹出的节点值，再将top指针指向它的下一个节点，并将弹出的节点的next指针赋空即可
  public Node<E> pop(){
    if(isEmpty())
      throw new RuntimeException("栈为空");
    Node<E> value = top;
    top = top.next;
    value.next = null;
    size--;
    return value;
  }

  //返回当前栈的大小
  public int length(){
    return size;
  }

  public static void main(String[] args) {
    MyStack<Integer> myStack = new MyStack<>();
    for(int i = 0; i < 10; i++){
      myStack.push(i);
    }
    for(int i = 0; i < 10; i++){
      System.out.println(myStack.pop().e);
    }
  }
}

到此这篇关于Java 实现栈的三种方式的文章就介绍到这了,更多相关Java 实现栈内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！