Java實現(xiàn)棧和最小棧的方法

更新時間：2026年02月25日 10:47:21 作者：祈安_.

棧（Stack）是一種常用的數(shù)據(jù)結(jié)構(gòu),其核心特點是先進后出,這篇文章主要介紹了Java實現(xiàn)棧和最小棧的相關(guān)操作,需要的朋友可以參考下

一、棧的簡介

棧（Stack）是一種常用的數(shù)據(jù)結(jié)構(gòu)，其核心特點是先進后出。棧主要提供三種基本操作：push（入棧，將元素放入棧頂）、pop（出棧，取出并刪除棧頂元素）、peek/top（查看棧頂元素但不刪除）。?？梢杂脭?shù)組或鏈表實現(xiàn)，數(shù)組實現(xiàn)操作簡單、隨機訪問快，但容量固定或需要擴容；鏈表實現(xiàn)則不受容量限制，但需要額外的指針空間。最小棧（MinStack）還可以在 O(1) 時間內(nèi)獲取當前棧的最小值，通過額外的輔助棧記錄歷史最小值實現(xiàn)。

二、IStack

public interface IStack {
    void push(int x);
    int pop();
    int size();
    boolean empty();
    boolean full();
}

這段代碼定義了一個棧的接口 IStack，用于規(guī)范棧的基本功能。接口中聲明了五個方法：

push(int x)：將元素 x 入棧。

pop()：從棧頂彈出元素并返回，如果棧為空，通常會拋出異常。

size()：返回棧中當前元素的個數(shù)。

empty()：判斷棧是否為空。

full()：判斷棧是否已滿。

三、MyStack

import java.util.Arrays;
public class MyStack implements IStack{
    private int[] elem;
    private int usedSize;
    private static final int DEFAULT_CAPACITY=10;
    public MyStack(){
        elem=new int[DEFAULT_CAPACITY];
    }
    @Override
    public void push(int x) {
        if(full()){
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++]=x;
    }
    @Override
    public int pop() {
        if(empty()){
            throw new EmptyException("?？樟?);
        }
        int old=elem[usedSize-1];
        usedSize--;
        return old;
    }
    public int peek(){
        if(empty()){
            throw new EmptyException("?？樟?);
        }
        return elem[usedSize-1];
    }
    @Override
    public int size() {
        return usedSize;
    }
    @Override
    public boolean empty() {
        return usedSize==0;
    }
    @Override
    public boolean full() {
        if(usedSize==elem.length){
            return true;
        }
        return false;
    }
}

這段代碼實現(xiàn)了一個順序棧（數(shù)組棧），它通過數(shù)組 elem 存儲棧中的元素，并用 usedSize 記錄當前棧中元素的個數(shù)。棧的容量初始為 DEFAULT_CAPACITY（10），當數(shù)組滿時，push 方法會通過 Arrays.copyOf 將數(shù)組擴容為原來的兩倍，以保證?？梢詣討B(tài)增長。

push(int x) 將元素放入棧頂并更新 usedSize；

pop() 從棧頂彈出元素并返回，同時判斷棧是否為空，若為空則拋出自定義異常 EmptyException；

peek() 查看棧頂元素但不刪除，也會在空棧時拋異常。

size() 返回棧中當前元素數(shù)量，empty() 判斷棧是否為空，full() 判斷棧是否已滿。

四、MinStack

import java.util.Stack;
public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack(){
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    public void push(int val){
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            int peekVal=minStack.peek();
            if(val<=peekVal){
                minStack.push(val);
            }
        }
    }
    public void pop(){
        int val=stack.pop();
        if(!minStack.empty()){
            if(val== minStack.peek()){
                minStack.pop();
            }
        }
    }
    public int top(){
        return stack.peek();
    }
    public int getMin(){
        if(!minStack.empty()){
            return minStack.peek();
        }
        return -1;
    }
}
import java.util.Stack;
public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack(){
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    public void push(int val){
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            int peekVal=minStack.peek();
            if(val<peekVal){
                minStack.push(val);
            }
        }
    }
    public void pop(){
        int val=stack.pop();
        if(!minStack.empty()){
            if(val== minStack.peek()){
                minStack.pop();
            }
        }
    }
    public int top(){
        return stack.peek();
    }
    public int getMin(){
        if(!minStack.empty()){
            return minStack.peek();
        }
        return -1;
    }
}

這段代碼實現(xiàn)了一個最小棧，它可以在 O(1) 時間內(nèi)獲取當前棧中的最小值。代碼使用了兩個 Stack<Integer> 對象：stack 用于存儲所有入棧的元素，而 minStack 用于記錄棧中歷史最小值。

當執(zhí)行 push 操作時，如果 minStack 為空或新元素比當前最小值小，就將新元素壓入 minStack；這樣 minStack 的棧頂始終是當前最小值。

pop 操作會先從 stack 彈出元素，如果彈出的值等于 minStack 棧頂，也同步彈出 minStack 的棧頂，以保證最小值的正確性。

top() 方法返回當前棧頂元素，而 getMin() 返回當前最小值。

五、EmptyException

public class EmptyException extends RuntimeException{
    public EmptyException(String msg){
        super(msg);
    }
}

這段代碼定義了一個自定義異常類 EmptyException，它繼承自 Java 的 RuntimeException，用于在程序運行時表示“棧或隊列為空”的特殊情況。構(gòu)造方法 EmptyException(String msg) 接收一個字符串參數(shù) msg，并調(diào)用父類 RuntimeException 的構(gòu)造方法，將提示信息傳遞給異常對象。當?；蜿犃械葦?shù)據(jù)結(jié)構(gòu)在執(zhí)行 pop、peek 等操作時，如果當前沒有元素，就可以拋出這個異常，從而明確地告知調(diào)用者操作失敗的原因。

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

您可能感興趣的文章: