java中LinkedList 集合類實現棧和隊列

2019-11-18 15:33:56

字體：大中小

來源：轉載

供稿：網友

棧和隊列是兩種非凡的線性表，它們的邏輯結構和線性表相同，只是其運算規則較線性表有更多的限制，故又稱它們為運算受限的線性表。

   LinkedList數據結構是一種雙向的鏈式結構，每一個對象除了數據本身外，還有兩個引用，分別指向前一個元素和后一個元素，和數組的順序存儲結構（如：ArrayList）相比，插入和刪除比較方便，但速度會慢一些。

棧的定義
    　棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。
　　(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。
　　(2)當表中沒有元素時稱為空棧。
　　(3)棧為后進先出（Last In First Out）的線性表，簡稱為LIFO表。
    　棧的修改是按后進先出的原則進行。每次刪除（退棧）的總是當前棧中"最新"的元素，即最后插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。

實現代碼：
package com.gc.list;
import java.util.*;
public class MyStack {

PRivate LinkedList ll=new LinkedList();

public void push(Object o){
  ll.addFirst(o);
}
public Object pop(){
  return ll.removeFirst();
}

public Object peek(){
  return ll.getFirst();
}

public boolean empty(){
  return ll.isEmpty();
}

public static void main(String[] args){
  MyStack ms=new MyStack();
  ms.push("zhangsan");
  ms.push("lisi");
  ms.push("wangwu");

  System.out.println(ms.pop());
  System.out.println(ms.peek());
  System.out.println(ms.pop());
  System.out.println(ms.empty());
}
}

隊列定義
    　隊列（Queue）是只答應在一端進行插入，而在另一端進行刪除的運算受限的線性表

　　（1）答應刪除的一端稱為隊頭（Front）。
　　（2）答應插入的一端稱為隊尾（Rear）。
　　（3）當隊列中沒有元素時稱為空隊列。
　　（4）隊列亦稱作先進先出（First In First Out）的線性表，簡稱為FIFO表。

實現代碼：
package com.gc.list;
import java.util.*;
public class MyQueue {

private LinkedList ll=new LinkedList();
public void put(Object o){
  ll.addLast(o);
}
//使用removeFirst()方法，返回隊列中第一個數據，然后將它從隊列中刪除
public Object get(){
  return ll.removeFirst();
}

public boolean empty(){
  return ll.isEmpty();
}

public static void main(String[] args){
  MyQueue mq=new MyQueue();
  mq.put("zhangsan");
  mq.put("lisi");