Java 實(shí)現(xiàn)棧的三種方式

更新時(shí)間：2020年12月04日 17:54:24 作者：Survivior_Y

這篇文章主要介紹了棧：LIFO（后進(jìn)先出），自己實(shí)現(xiàn)一個(gè)棧，要求這個(gè)棧具有push()、pop()（返回棧頂元素并出棧）、peek() （返回棧頂元素不出棧）、isEmpty()這些基本的方法,需要的朋友可以參考下

棧：LIFO（后進(jìn)先出），自己實(shí)現(xiàn)一個(gè)棧，要求這個(gè)棧具有push()、pop()（返回棧頂元素并出棧）、peek() （返回棧頂元素不出棧）、isEmpty()這些基本的方法。

一、采用數(shù)組實(shí)現(xiàn)棧

提示：每次入棧之前先判斷棧的容量是否夠用，如果不夠用就用Arrays.copyOf()進(jìn)行擴(kuò)容

import java.util.Arrays;
/**
 * 數(shù)組實(shí)現(xiàn)棧
 * @param <T>
 */
class Mystack1<T> {
  //實(shí)現(xiàn)棧的數(shù)組
  private Object[] stack;
  //數(shù)組大小
  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;
  }
 
  //擴(kuò)大容量
  public void expandCapacity(int size) {
    int len = stack.length;
    if (size > len) {
      size = size * 3 / 2 + 1;//每次擴(kuò)大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());
  }
}

二、采用鏈表實(shí)現(xiàn)棧

/**
 * 鏈表實(shí)現(xiàn)棧
 *
 * @param <T>
 */
class Mystack2<T> {
  //定義鏈表
  class Node<T> {
    private T t;
    private Node next;
  }
 
  private Node<T> head;
 
  //構(gòu)造函數(shù)初始化頭指針
  Mystack2() {
    head = null;
  }
 
  //入棧
  public void push(T t) {
    if (t == null) {
      throw new NullPointerException("參數(shù)不能為空");
    }
    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實(shí)現(xiàn)棧

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

import java.util.LinkedList;
 
/**
 * LinkedList實(shí)現(xiàn)棧
 *
 * @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;
    //直接取元素會(huì)報(bào)異常，需要先判斷是否為空
    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使用兩種方式實(shí)現(xiàn)簡(jiǎn)單棧

兩種棧的不同點(diǎn)

基于數(shù)組實(shí)現(xiàn)的棧需要指定初始容量，棧的大小是有限的（可以利用動(dòng)態(tài)擴(kuò)容改變其大?。?，基于鏈表實(shí)現(xiàn)的棧則是沒有大小限制的。

基于數(shù)組實(shí)現(xiàn)棧

數(shù)組實(shí)現(xiàn)棧的主要方法就是標(biāo)識(shí)棧頂在數(shù)組中的位置，初始化時(shí)可以將棧頂指向?yàn)?1的虛擬位置，元素入棧則棧頂元素加1，出棧則棧頂元素減一，棧的元素容量為棧頂指針當(dāng)前位置加1，且不能超過底層數(shù)組的最大容量。

/**
 * 以數(shù)組為底層實(shí)現(xiàn)棧
 * @param <T>
 */
public class MyStackOfArray<T> {
  private Object[] data;//底層數(shù)組
  private int maxSize = 0;//棧存儲(chǔ)的最大元素個(gè)數(shù)
  private int top = -1;//初始時(shí)棧頂指針指向-1

  //默認(rèn)初始化容量為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);
    }
  }

  //入棧，棧頂指針先加一再填入數(shù)據(jù)
  public boolean push(T element){
    if(top == maxSize - 1){
      throw new RuntimeException("當(dāng)前棧已滿，無法繼續(xù)添加元素");
    }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--];
  }

  //判斷當(dāng)前棧是否為空，只需判斷棧頂指針是否等于-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("測(cè)試是否執(zhí)行");
    for(int i = 0; i < 10; i++){
      System.out.println(myStackOfArray.pop());
    }
  }
}

基于鏈表實(shí)現(xiàn)棧

基于鏈表實(shí)現(xiàn)棧只要注意控制棧頂指針的指向即可。

/**
 * 鏈表方式實(shí)現(xiàn)棧
 * @param <E>
 */
public class MyStack<E> {
  /**
   * 內(nèi)部節(jié)點(diǎn)類
   * @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;
  }

  //入棧，將新節(jié)點(diǎn)的next指針指向當(dāng)前top指針，隨后將top指針指向新節(jié)點(diǎn)
  public boolean push(E e){
    top = new Node(e, top);
    size++;
    return true;
  }

  //判斷棧是否為空
  public boolean isEmpty(){
    return size == 0;
  }

  //返回棧頂節(jié)點(diǎn)
  public Node<E> peek(){
    if(isEmpty())
      throw new RuntimeException("棧為空");
    return top;
  }

  //出棧，先利用臨時(shí)節(jié)點(diǎn)保存要彈出的節(jié)點(diǎn)值，再將top指針指向它的下一個(gè)節(jié)點(diǎn)，并將彈出的節(jié)點(diǎn)的next指針賦空即可
  public Node<E> pop(){
    if(isEmpty())
      throw new RuntimeException("棧為空");
    Node<E> value = top;
    top = top.next;
    value.next = null;
    size--;
    return value;
  }

  //返回當(dāng)前棧的大小
  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);
    }
  }
}

到此這篇關(guān)于Java 實(shí)現(xiàn)棧的三種方式的文章就介紹到這了,更多相關(guān)Java 實(shí)現(xiàn)棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: