Java基于鏈表實(shí)現(xiàn)棧的方法詳解

更新時間：2020年03月17日 12:04:59 作者：WFaceBoss

這篇文章主要介紹了Java基于鏈表實(shí)現(xiàn)棧的方法,結(jié)合實(shí)例形式詳細(xì)分析了Java基于鏈表實(shí)現(xiàn)棧的原理、操作步驟與相關(guān)注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了Java基于鏈表實(shí)現(xiàn)棧的方法。分享給大家供大家參考，具體如下：

在上幾小節(jié)中我們實(shí)現(xiàn)了基本的鏈表結(jié)構(gòu)，并在上一節(jié)的底部給出了有關(guān)鏈表的源碼，此處在貼一次吧，猛戳

在開始棧的實(shí)現(xiàn)之前，我們再來看看關(guān)于鏈表的只在頭部進(jìn)行的增加、刪除、查找操作，時間復(fù)雜度均為O(1)，基于鏈表的這幾個優(yōu)勢，我們在此基礎(chǔ)上實(shí)現(xiàn)棧。

前言，在寫本小節(jié)之前，我們已經(jīng)實(shí)現(xiàn)了一個基于靜態(tài)數(shù)組的棧，轉(zhuǎn)到查看。此處我們實(shí)現(xiàn)基于鏈表的棧。

1.鏈表類拷貝到Stack 包下：

在實(shí)現(xiàn)基于靜態(tài)數(shù)組的棧的時候，我們已經(jīng)新建了一個package，此時我們將已經(jīng)實(shí)現(xiàn)的鏈表類拷貝到該package下，目錄結(jié)構(gòu)為：

2.實(shí)現(xiàn)棧

新建一個LinkedListStack類，實(shí)現(xiàn)Stack接口，相關(guān)代碼如下：

Stack接口:

package Stack;

public interface Stack<E> {

  //棧中元素個數(shù)
  int getSize();

  //棧中元素個數(shù)是否為空
  boolean isEmpty();

  //進(jìn)棧
  void push(E e);

  //出棧
  E pop();

  //查看棧頂元素
  E peek();
}

個LinkedListStack類:

package Stack;

public class LinkedListStack<E> implements Stack<E> {
  private LinkedList<E> list;

  public LinkedListStack() {
    list = new LinkedList<E>();
  }

  //棧中元素個數(shù)
  @Override
  public int getSize() {
    return list.getSize();
  }

  //棧中是否為空
  @Override
  public boolean isEmpty() {
    return list.isEmpty();
  }

  //在棧中添加元素
  @Override
  public void push(E e) {
    list.addFirst(e);
  }

  //從棧中刪除第一個元素
  @Override
  public E pop() {
    return list.removeFirst();
  }

  //查看棧中第一個元素
  @Override
  public E peek() {
    return list.getFirst();
  }


  //主要是便于輸出給對象信息
  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append("Stack: top ");
    res.append(list);
    return res.toString();
  }

}

3.添加測試代碼

為了測試的簡單，我們在已經(jīng)實(shí)現(xiàn)了Stack接口的LinkedListStack類中建立以main()方法，main中代碼如下：

  //測試
  public static void main(String[] args) {
    LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
    for (int i = 0; i < 5; i++) {
      stack.push(i);
      System.out.println(stack);
    }
    System.out.println("出棧一個元素：");
    stack.pop();
    System.out.println(stack);
  }

結(jié)果為：