Java棧的三種實現(xiàn)方式(完整版)

更新時間：2020年12月04日 18:12:26 作者：熊三@

這篇文章主要介紹了Java棧的三種實現(xiàn)方式(完整版),需要的朋友可以參考下

java什么是棧

系統(tǒng)中的堆、棧和數(shù)據(jù)結(jié)構(gòu)堆、棧不是一個概念。可以說系統(tǒng)中的堆、棧是真實的內(nèi)存物理區(qū)，數(shù)據(jù)結(jié)構(gòu)中的堆、棧是抽象的數(shù)據(jù)存儲結(jié)構(gòu)。

棧：實際上就是滿足后進先出的性質(zhì)，是一種數(shù)據(jù)項按序排列的數(shù)據(jù)結(jié)構(gòu)，只能在一端(稱為棧頂(top))對數(shù)據(jù)項進行插入和刪除。

棧區(qū)（stack）— 由編譯器自動分配釋放，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。

棧的優(yōu)勢是，存取速度比堆要快，僅次于直接位于CPU中的寄存器。但缺點是，存在棧中的數(shù)據(jù)大小與生存期必須是確定的，缺乏靈活性。

代碼：

Stack的基本使用
初始化
Stack stack=new Stack
判斷是否為空
stack.empty()
取棧頂值（不出棧）
stack.peek()
進棧
stack.push(Object);
出棧
stack.pop();
實例：
public class Test01 {
 public static void main(String[] args) {
 Stack stack=new Stack();
 //1.empty()棧是否為空
 System.out.println(stack.empty());
 //2.peek()棧頂值  3.進棧push()
 stack.push(new Integer(1));
 stack.push("b");
 System.out.println(stack.peek());
 //4.pop()出棧
 stack.pop();
 System.out.println(stack.peek());
 }
}

棧的主要操作

void push(int data)：將data（數(shù)據(jù)）插入棧
int pop()：刪除并返回最后一個插入棧的

棧的輔助操作

int top()：返回最后一個插入棧的元素，但不刪除
int size()：返回存儲在棧中的元素的個數(shù)
int isEmpty()：判斷棧中是否有元素
int isStackFull()：判斷棧中是否滿元素

實現(xiàn)

棧抽象數(shù)據(jù)類型有多種實現(xiàn)方式。下面是常用的方法：

基于簡單數(shù)組的實現(xiàn)方法
基于動態(tài)數(shù)組的實現(xiàn)方法
基于鏈表的實現(xiàn)方法

1）基于簡單數(shù)組實現(xiàn)：

public class Stack{
  private int size;//棧的大小
  private int top;//棧頂元素的下標(biāo)
  private char[] stackArray;//棧的容器
  public Stack(int size){
  	stackArray = new char[size];
  	top = -1;     //初始化棧的時候由于棧內(nèi)沒有元素，棧頂下標(biāo)設(shè)為-1  
  	this.size = size;
  }
  //入棧,棧頂?shù)南聵?biāo)+1
  public void push(char item){
  	stackArray[++top] = item;
  }
  //出棧，刪除棧頂元素，棧頂元素的下標(biāo)-1
  public int pop(){
  	return stackArray[top--];
  }
  //查看棧頂元素，不刪除
  public char find(){
  	return stackArray[top];
  }
  //判空
  public boolean isEmpty(){
  	return (top == -1);
  }
  //判滿
  public boolean isFull(){
  	return (top == size - 1);
  }
  public static void main(String[] args){
  	Stack stack = new Stack(5);
  	stack.push('a');
  	stack.push('b');
  	stack.push('c');
  	stack.push('d');
  	char ch = stack.find();
  	System.out.println(ch);
  }
}

運行結(jié)果：

2）基于動態(tài)數(shù)組實現(xiàn)：

擴容——給我的感覺就像是在搬家，搬完了東西，還得把鑰匙給主人

public class Stack {
	public int size;//棧的大小
  public int top;//棧頂元素的下標(biāo)
  public static char[] stackArray;//棧的容器
  public Stack(int size){
  	stackArray = new char[size];
  	top = -1;     //初始化棧的時候由于棧內(nèi)沒有元素，棧頂下標(biāo)設(shè)為-1     
  	this.size = size;
  }
  //入棧,棧頂?shù)南聵?biāo)+1
  public void push(char item){
  		if(isFull()){
  			doubleStack();
  		}
  		stackArray[++top] = item;
  }
  //模擬數(shù)組的擴容
  public void doubleStack(){
  	char[] newStackArray = new char[size*2];
  	for(int i = 0;i<size;i++){
  		newStackArray[i] = stackArray[i];
  	}
  	size = size*2;
  	stackArray = newStackArray;
  }
  //出棧，刪除棧頂元素，棧頂元素的下標(biāo)-1
  public int pop(){
  	if(isEmpty()){
  		System.out.println("Stack is Empty");
  		return 0;
  	}else{ 		
  		return stackArray[top--];
  	}
  }
  //查看棧頂元素，不刪除
  public char find(){
  	return stackArray[top];
  }
  //判空
  public boolean isEmpty(){
  	return (top == -1);
  }
  //判滿
  public boolean isFull(){
  	return (top == size - 1);
  }
  public static void main(String[] args){
  	Stack stack = new Stack(5);
  	stack.push('a');
  	stack.push('b');
  	stack.push('c');
  	stack.push('d');
  	stack.push('e');
  	stack.push('f');
  	stack.push('g');
  	stack.push('h');//一共8個元素
  	char ch = stack.find();
  	System.out.println(ch);
  	System.out.println(stackArray.length);
  }
}

運行結(jié)果：

h
10

3）基于鏈表實現(xiàn)

使用鏈表實現(xiàn)棧，通過在鏈表的表頭插入元素的方式實現(xiàn)push操作，刪除鏈表的表頭結(jié)點實現(xiàn)pop操作。表頭結(jié)點即棧頂結(jié)點

import java.util.EmptyStackException;
class Link{
	public char data;
	public Link next;
	public void show(){
		System.out.println(data + " ");
	}
	public Link(char data){
		this.data = data;
	}
}
public class Stack2 {
	Link head;
  public int size;//棧的大小
  public int top;//棧頂元素的下標(biāo)
  public static char[] stackArray;//棧的容器
  public void push(char data){
  	if(head == null){
  		head = new Link(data);
  	}else{
  		Link node = new Link(data);
  		node.next = head;
  		head = node;
  	}
  }
  public void pop(){
  	if(head == null){
  		throw new EmptyStackException();
  	}else{
  		char dat = head.data;
  		head.show();
  		head = head.next;
  	}
  }
  public int top(){
  	if(head == null){
  		return 0;
  	}else{
  		return head.data;
  	}
  }
  public boolean isEmpty(){
  	if(head == null) return true;
  	return false;
  }
  public static void main(String[] args){
  	Stack2 stack = new Stack2();
  	stack.push('A');
  	stack.push('B');
  	stack.push('C');
  	stack.push('D');
  	stack.push('E');
  	stack.push('F');
  	stack.pop();
  }
}

運行結(jié)果：

到此這篇關(guān)于Java棧的三種實現(xiàn)方式(完整版)的文章就介紹到這了,更多相關(guān)Java棧內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: