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

兩種棧的不同點

基于數組實現的棧需要指定初始容量，棧的大小是有限的（可以利用動態(tài)擴容改變其大?。阪湵韺崿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('當前棧已滿，無法繼續(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--]; } //判斷當前棧是否為空，只需判斷棧頂指針是否等于-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('測試是否執(zhí)行'); for(int i = 0; i < 10; i++){ System.out.println(myStackOfArray.pop()); } }}

基于鏈表實現棧

基于鏈表實現棧只要注意控制棧頂指針的指向即可。

/** * 鏈表方式實現棧 * @param <E> */public class MyStack<E> { /** * 內部節(jié)點類 * @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é)點的next指針指向當前top指針，隨后將top指針指向新節(jié)點 public boolean push(E e){ top = new Node(e, top); size++; return true; } //判斷棧是否為空 public boolean isEmpty(){ return size == 0; } //返回棧頂節(jié)點 public Node<E> peek(){ if(isEmpty()) throw new RuntimeException('棧為空'); return top; } //出棧，先利用臨時節(jié)點保存要彈出的節(jié)點值，再將top指針指向它的下一個節(jié)點，并將彈出的節(jié)點的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 實現棧內容請搜索好吧啦網以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持好吧啦網！