快捷導(dǎo)航

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

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

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

一、棧的簡介

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

二、IStack

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

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

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

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

size()：返回棧中當(dāng)前元素的個(gè)數(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;
    }
}

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

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

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

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

size() 返回棧中當(dāng)前元素?cái)?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;
    }
}

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

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

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

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

五、EmptyException

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

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

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

您可能感興趣的文章: