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使用兩種方式實現簡單棧

兩種棧的不同點

基于數組實現的棧需要指定初始容量，棧的大小是有限的（可以利用動態擴容改變其大?。阪湵韺崿F的棧則是沒有大小限制的。

基于數組實現棧

數組實現棧的主要方法就是標識棧頂在數組中的位置，初始化時可以將棧頂指向為-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--; elsebreak; } 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 實現棧內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！