Java數(shù)據(jù)結(jié)構(gòu)與算法之棧(Stack)實現(xiàn)詳解
本篇是java數(shù)據(jù)結(jié)構(gòu)與算法的第2篇，從本篇開始我們將來了解棧的設計與實現(xiàn)，以下是本篇的相關知識點：
棧的抽象數(shù)據(jù)類型順序棧的設計與實現(xiàn)鏈式棧的設計與實現(xiàn)棧的應用
棧的抽象數(shù)據(jù)類型
棧是一種用于存儲數(shù)據(jù)的簡單數(shù)據(jù)結(jié)構(gòu)，有點類似鏈表或者順序表（統(tǒng)稱線性表），棧與線性表的最大區(qū)別是數(shù)據(jù)的存取的操作，我們可以這樣認為棧(Stack)是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進行，一般而言，把允許操作的一端稱為棧頂(Top)，不可操作的一端稱為棧底(Bottom)，同時把插入元素的操作稱為入棧(Push),刪除元素的操作稱為出棧(Pop)。若棧中沒有任何元素，則稱為空棧，棧的結(jié)構(gòu)如下圖：
由圖我們可看成棧只能從棧頂存取元素，同時先進入的元素反而是后出，而棧頂永遠指向棧內(nèi)最頂部的元素。到此可以給出棧的正式定義：棧(Stack)是一種有序特殊的線性表，只能在表的一端(稱為棧頂，top，總是指向棧頂元素)執(zhí)行插入和刪除操作，最后插入的元素將第一個被刪除，因此棧也稱為后進先出(Last In First Out,LIFO)或先進后出(First In Last Out FILO)的線性表。棧的基本操作創(chuàng)建棧，判空，入棧，出棧，獲取棧頂元素等，注意棧不支持對指定位置進行刪除，插入，其接口Stack聲明如下：
/*
* 棧接口抽象數(shù)據(jù)類型
*/
public interface Stack<T> {
/**
* 棧是否為空
* @return
*/
boolean isEmpty();
/**
* data元素入棧
* @param data
*/
void push(T data);
/**
* 返回棧頂元素,未出棧
* @return
*/
T peek();
/**
* 出棧,返回棧頂元素,同時從棧中移除該元素
* @return
*/
T pop();
}
順序棧的設計與實現(xiàn)
順序棧，顧名思義就是采用順序表實現(xiàn)的的棧，順序棧的內(nèi)部以順序表為基礎，實現(xiàn)對元素的存取操作，當然我們還可以采用內(nèi)部數(shù)組實現(xiàn)順序棧，在這里我們使用內(nèi)部數(shù)據(jù)組來實現(xiàn)棧，至于以順序表作為基礎的棧實現(xiàn)，將以源碼提供。這里先聲明一個順序棧其代碼如下，實現(xiàn)Stack和Serializable接口：
/*
* 順序棧的實現(xiàn)
*/
public class SeqStack<T> implements Stack<T>,Serializable {
private static final long serialVersionUID = -5413303117698554397L;
/**
* 棧頂指針,-1代表空棧
*/
private int top=-1;
/**
* 容量大小默認為10
*/
private int capacity=10;
/**
* 存放元素的數(shù)組
*/
private T[] array;
private int size;
public SeqStack(int capacity){
array = (T[]) new Object[capacity];
}
public SeqStack(){
array= (T[]) new Object[this.capacity];
}
//.......省略其他代碼
}
其獲取棧頂元素值的peek操作過程如下圖（未刪除只獲取值）：
以上是獲取棧頂元素的操作，代碼如下：
/**
* 獲取棧頂元素的值,不刪除
* @return
*/
@Override
public T peek() {
if(isEmpty())
new EmptyStackException();
return array[top];
}
從棧添加元素的過程如下（更新棧頂top指向）：
以上是入棧操作，代碼如下：
/**
* 添加元素,從棧頂(數(shù)組尾部)插入
* 容量不足時，需要擴容
* @param data
*/
@Override
public void push(T data) {
//判斷容量是否充足
if(array.length==size)
ensureCapacity(size*2+1);//擴容
//從棧頂添加元素
array[++top]=data;
}
棧彈出棧頂元素的過程如下（刪除并獲取值）：
以上是出棧操作，代碼如下：
/**
* 從棧頂(順序表尾部)刪除
* @return
*/
@Override
public T pop() {
if(isEmpty())
new EmptyStackException();
size--;
return array[top--];
}
到此，順序棧的主要操作已實現(xiàn)完，是不是發(fā)現(xiàn)很簡單，確實如此，棧的主要操作就這樣，當然我們也可以通過前一篇介紹的MyArrayList作為基礎來實現(xiàn)順序棧，這個也比較簡單，后面也會提供帶代碼，這里就不過多啰嗦了。下面給出順序棧的整體實現(xiàn)代碼：
import java.io.Serializable;
import java.util.EmptyStackException;
/*
* 順序棧的實現(xiàn)
*/
public class SeqStack<T> implements Stack<T>,Serializable {
private static final long serialVersionUID = -5413303117698554397L;
/**
* 棧頂指針,-1代表空棧
*/
private int top=-1;
/**
* 容量大小默認為10
*/
private int capacity=10;
/**
* 存放元素的數(shù)組
*/
private T[] array;
private int size;
public SeqStack(int capacity){
array = (T[]) new Object[capacity];
}
public SeqStack(){
array= (T[]) new Object[this.capacity];
}
public int size(){
return size;
}
@Override
public boolean isEmpty() {
return this.top==-1;
}
/**
* 添加元素,從棧頂(數(shù)組尾部)插入
* @param data
*/
@Override
public void push(T data) {
//判斷容量是否充足
if(array.length==size)
ensureCapacity(size*2+1);//擴容
//從棧頂添加元素
array[++top]=data;
size++;
}
/**
* 獲取棧頂元素的值,不刪除
* @return
*/
@Override
public T peek() {
if(isEmpty())
new EmptyStackException();
return array[top];
}
/**
* 從棧頂(順序表尾部)刪除
* @return
*/
@Override
public T pop() {
if(isEmpty())
new EmptyStackException();
size--;
return array[top--];
}
/**
* 擴容的方法
* @param capacity
*/
public void ensureCapacity(int capacity) {
//如果需要拓展的容量比現(xiàn)在數(shù)組的容量還小,則無需擴容
if (capacity<size)
return;
T[] old = array;
array = (T[]) new Object[capacity];
//復制元素
for (int i=0; i<size ; i++)
array[i]=old[i];
}
public static void main(String[] args){
SeqStack<String> s=new SeqStack<>();
s.push("A");
s.push("B");
s.push("C");
System.out.println("size->"+s.size());
int l=s.size();//size 在減少,必須先記錄
for (int i=0;i<l;i++){
System.out.println("s.pop->"+s.pop());
}
System.out.println("s.peek->"+s.peek());
}
}
鏈式棧的設計與實現(xiàn)
了解完順序棧，我們接著來看看鏈式棧，所謂的鏈式棧（Linked Stack），就是采用鏈式存儲結(jié)構(gòu)的棧，由于我們操作的是棧頂一端，因此這里采用單鏈表（不帶頭結(jié)點）作為基礎，直接實現(xiàn)棧的添加，獲取，刪除等主要操作即可。其操作過程如下圖：
從圖可以看出，無論是插入還是刪除直接操作的是鏈表頭部也就是棧頂元素，因此我們只需要使用不帶頭結(jié)點的單鏈表即可。代碼實現(xiàn)如下，比較簡單，不過多分析了：
import com.zejian.structures.LinkedList.singleLinked.Node;
import java.io.Serializable;
/*
* 棧的鏈式實現(xiàn)
*/
public class LinkedStack<T> implements Stack<T> ,Serializable{
private static final long serialVersionUID = 1911829302658328353L;
private Node<T> top;
private int size;
public LinkedStack(){
this.top=new Node<>();
}
public int size(){
return size;
}
@Override
public boolean isEmpty() {
return top==null || top.data==null;
}
@Override
public void push(T data) {
if (data==null){
throw new StackException("data can\'t be null");
}
if(this.top==null){//調(diào)用pop()后top可能為null
this.top=new Node<>(data);
}else if(this.top.data==null){
this.top.data=data;
}else {
Node<T> p=new Node<>(data,this.top);
top=p;//更新棧頂
}
size++;
}
@Override
public T peek() {
if(isEmpty()){
throw new EmptyStackException("Stack empty");
}
return top.data;
}
@Override
public T pop() {
if(isEmpty()){
throw new EmptyStackException("Stack empty");
}
T data=top.data;
top=top.next;
size--;
return data;
}
//測試
public static void main(String[] args){
LinkedStack<String> sl=new LinkedStack<>();
sl.push("A");
sl.push("B");
sl.push("C");
int length=sl.size();
for (int i = 0; i < length; i++) {
System.out.println("sl.pop->"+sl.pop());
}
}
}
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
將springboot項目生成可依賴的jar并引入到項目中的方法
SpringBoot項目默認打包的是可運行jar包,也可以打包成不可運行的jar包,本文給大家介紹將springboot項目生成可依賴的jar并引入到項目中的方法,感興趣的朋友一起看看吧2023-11-11
發(fā)現(xiàn)許多小伙伴還不清楚Java二叉搜索樹的基本操作,今天特地整理了這篇文章,文中有非常詳細的代碼示例,對正在學習Java的小伙伴很有幫助,需要的朋友可以參考下2021-05-05
java自定義任務類定時執(zhí)行任務示例 callable和future接口使用方法
Callable是類似于Runnable的接口，實現(xiàn)Callable接口的類和實現(xiàn)Runnable的類都是可被其它線程執(zhí)行的任務2014-01-01
方法重載是指在一個類中定義多個同名的方法，但要求每個方法具有不同的參數(shù)的類型或參數(shù)的個數(shù)。調(diào)用重載方法時，Java編譯器能通過檢查調(diào)用的方法的參數(shù)類型和個數(shù)選擇一個恰當?shù)姆椒?。方法重載通常用于創(chuàng)建完成一組任務相似但參數(shù)的類型或參數(shù)的個數(shù)不同的方法。2016-04-04
java 畫pdf用itext調(diào)整表格寬度、自定義各個列寬的方法
這篇文章主要介紹了java 畫pdf用itext調(diào)整表格寬度、自定義各個列寬的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-01-01
這篇文章主要介紹了SpringMVC 實現(xiàn)用戶登錄實例代碼的相關資料,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了Java變量，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-08-08
Spring?Cache是一個框架，實現(xiàn)了基于注解的緩存功能，只需要簡單地加一個注解，就能實現(xiàn)緩存功能，這篇文章主要介紹了Spring?Cache簡介和使用,需要的朋友可以參考下2023-03-03
這篇文章主要介紹了Java后臺開發(fā)之表單提交之前驗證的實現(xiàn)代碼，非常不錯具有參考借鑒價值，需要的朋友參考下吧2017-02-02
在SpringBoot中使用UniHttp簡化天地圖路徑規(guī)劃調(diào)用實踐記錄(場景分析)
本文介紹了如何在SpringBoot項目中使用UniHttp簡化天地圖路徑規(guī)劃接口的調(diào)用,通過一個具體的例子展示了如何根據(jù)中文地址獲取經(jīng)緯度坐標,并使用UniHttp調(diào)用天地圖路徑規(guī)劃服務,感興趣的朋友一起看看吧2025-02-02