用Java代碼完成棧數據構造的根本辦法歸結。本站提示廣大學習愛好者:(用Java代碼完成棧數據構造的根本辦法歸結)文章只能為提供參考,不一定能成為您想要的結果。以下是用Java代碼完成棧數據構造的根本辦法歸結正文
鏈式完成:
在棧的一段添加和刪除元素,在棧中保護一個指向棧頂的結點和一個count變量指導棧的年夜小:
private LinearNode top; //指向棧頂
private int count;//標志棧的年夜小
每次出棧和壓棧在鏈表的表頭:(也能夠再表尾,完成方法紛歧樣罷了)
top--->元素1--->元素2--->元素3.........
完成(附帶測試main):
LinkedStack
package Stack; import Bag.LinearNode; //為了重點來完成算法,將異常情形直接打印出然撤退退卻出法式,不再聲明異常類 public class LinkedStack implements StackADT { private LinearNode top; //指向棧頂 private int count;//標志棧的年夜小 public static void main(String[] args){ LinkedStack stack = new LinkedStack(); System.out.println("將0到10順次壓棧"); for(int i = 0;i < 10;i++) stack.push(i); System.out.println("持續履行5次出棧操作"); for(int i = 0;i < 5;i++) stack.pop(); System.out.println("棧為空嗎?: " + stack.isEmpty()); System.out.println("棧的年夜小為: " + stack.size()); System.out.println("棧頂元素為: " + stack.top.getElement()); System.out.println("棧頂元素為: " + stack.peek()); } public LinkedStack() { top = null; count = 0; } public int size() { return count; } public boolean isEmpty() { return (size() == 0); } public void push(Object element) { LinearNode node = new LinearNode(element); node.setNext(top); top = node; count++; } public Object pop() { if(isEmpty()) { System.out.println("stack is empty!"); System.exit(1); } Object result = top.getElement(); top = top.getNext(); count--; return result; } public Object peek() { Object result = top.getElement(); return result; } }
運轉成果:
將0到10順次壓棧
持續履行5次出棧操作
棧為空嗎?: false
棧的年夜小為: 5
棧頂元素為: 4
棧頂元素為: 4
數組完成:
棧底老是數組下標為0的地位,入棧出棧從數組下標的最初一個元素開端:
private Object[] contents; private int top;//top標志下一個入棧的地位,同時也表現棧的容量年夜小,跟鏈式完成的count比擬一下!!!
完成(附帶測試main):
ArrayStack
package Stack; public class ArrayStack implements StackADT { private Object[] contents; private int top;//top標志下一個入棧的地位,同時也表現棧的容量年夜小,跟鏈式完成的count比擬一下!!! private static int SIZE = 10; public ArrayStack() { contents = new Object[SIZE]; top = 0; } public void expand(){//借助於請求一個幫助空間,每次擴大容量一倍 Object[] larger = new Object[size()*2]; for(int index = 0;index < top;index++) larger[index] = contents[index]; contents = larger; } public int size() { return top; } public boolean isEmpty() { return (size() == 0); } public void push(Object element) { //if(isEmpty()) //expand(); if(top == contents.length) expand(); contents[top] = element; top++; } public Object pop() { if(isEmpty()) { System.out.println("stack is empty!"); System.exit(1); } Object result = contents[top-1]; contents[top-1] = null;//出棧 top--; return result; /*書上如許寫輕便一點::: * top--; * Object result = contents[top]; * contents[top] = null;*/ } public Object peek() { Object result; if(isEmpty()) result = null; else result = contents[top-1]; return result; } public static void main(String[] args) { ArrayStack stack = new ArrayStack(); System.out.println("將0到24順次壓棧,然後持續10次出棧"); for(int i = 0;i < 25;i++) stack.push(i); for(int i = 0;i < 10;i++) stack.pop(); System.out.println("棧的年夜小為: " + stack.size()); System.out.println("棧為空嗎?: " + stack.isEmpty()); System.out.println("棧頂元素為: " + stack.peek()); } }
運轉成果:
將0到24順次壓棧,然後持續10次出棧
棧的年夜小為: 15
棧為空嗎?: false
棧頂元素為: 14
應用聚集LinkedList來模仿棧
辦法
java的泛型可讓LinkedList模仿存儲各類數據類型的棧,包含int,double,String,Object等等,引見一下幾種用到的API接口:
入棧
void addFirst(E e); // 將指定元素拔出此列表的開首
獲得棧頂元素
E getFirst(); // 前往此列表的第一個元素
出棧
E removeFirst(); // 移除並前往此列表第一個元素
判棧空
boolean isEmpty(); // 斷定棧空
示例代碼
import java.util.LinkedList; import java.util.NoSuchElementException; public class SimulateStack { private LinkedList<Integer> stack = new LinkedList<Integer>(); public boolean isEmpty() { return this.stack.isEmpty(); } public void push(int data) { this.stack.addFirst(data); } public int pop() throws NoSuchElementException{ return this.stack.removeFirst(); } public int getTop() throws NoSuchElementException{ return this.stack.getFirst(); } public static void main(String args[]) { SimulateStack s = new SimulateStack(); s.push(1); s.push(2); s.push(3); while (! s.isEmpty()) { int data = s.getTop(); System.out.println(data); s.pop(); } } }