java數據結構基礎:棧

Posted on by

準備工作

工具：idea+jdk8

技術要求：java基礎語法

編碼環節

首先，我們得先確定下來，用什麼數據來模擬棧的操作。由於是一個一個的元素放入棧裡面，我們可以考慮用數組來實現。

在這裡插入圖片描述

以上是Java官方文檔中的棧定義，我們也隻需要實現三個方法：判斷是否為空、移除棧頂對象、添加元素到棧的尾部

所以我們事先得定義一個數組：

Objects[] arr;

數組定義好瞭之後呢，想想，我們怎麼去獲取到棧尾部或者棧首的元素呢？還記得數組的索引嗎？可以用索引來假設為棧的指針。所以，我們還得定義好棧的元素個數和棧的默認長度以及默認的指針：

private int stackLength = 4; // 數組的默認長度
private int size; // 記住棧容器的元素個數
private int index = -1; // 操作數組下標位置的指針

為什麼這兒指向的是-1呢？我們知道，數組的第一個元素是索引為0，那麼-1的意思就是不指向任何元素。待會兒我們在用的時候再去指向他。

然後，我們還得定義出數組的初始化。以及初始化的長度。參考官方文檔的寫法，當棧的長度滿瞭之後我們就對棧長度進行1.5倍的擴容。我們就單獨提取出一個方法來放置；

/**
 * 數組初始化或者以1.5倍容量對數組擴容
 */
private void capacity() {
    // 數組初始化
    if (this.arr == null) {
        this.arr = new Object[this.stackLength];
    }
    // 以1.5倍對數組擴容
    if (this.size - (this.stackLength - 1) >= 0) { // 如果當前數組的元素個數大於瞭當前數組的最後一個索引值
        this.stackLength = this.stackLength + (this.stackLength >> 1); // 位運算，讓長度變成原來的1/2
        this.arr = Arrays.copyOf(this.arr, this.stackLength); // 復制一個新的數組，用新開辟的長度
    }
}

push方法

如何給棧添加元素？我們要考慮的地方：指針向右移動一位，也就是說指針要+1。其次，添加完元素之後，棧元素的長度發生瞭變化，size+1 。

public E push(E item){
    // 先初始化數組
    this.capacity();
    // 添加元素
    this.arr[++index] = item;
    // 記錄元素個數加一
    this.size++;
    return item;
}

pop方法

pop方法主要是用來移除棧頂的元素。

先分析一下思路：我們要用index去指向棧頂的元素，該怎麼去指定？

刪除之後，對應的size長度該怎麼去改變？

我們知道，當元素添加瞭之後，index會跟著改變，那麼就好比我們添加瞭三個元素，此時的index應該就是指向的2。那就好辦瞭。

當移除的時候，我們隻需要讓index–來操作就能解決問題；看代碼：

/**
 * 獲取棧頂元素
 *
 * @return
 */
public E pop() {
    // 如果棧容器中沒有元素則拋出異常
    if (this.index == -1) {
        throw new EmptyStackException();
    }
    // 記錄元素個數
    this.size--;
    // 返回棧頂元素
    System.out.println("刪除元素之前的當前下標："+index);
    return (E) this.arr[index--];
}

empty方法

判斷棧是否為空，這很簡單。直接判斷當前的size是不是0就能解決：

public boolean empty(){
	return this.index==0?true:false;
}

全部代碼

package com.zxy;
import java.util.Arrays;
import java.util.EmptyStackException;
/**
 * @Author Zxy
 * @Date 2021/2/2 20:24
 * @Version 1.0
 * 演示棧容器的使用
 */
public class MyStack<E> {
    private Object[] arr; // 存放元素的物理結構
    private int stackLength = 4; // 數組的默認長度
    private int size; // 記住棧容器的元素個數
    private int index = -1; // 操作數組下標位置的指針
    /**
     * 判斷棧容器是否為空
     */
    public boolean empty() {
        return this.size == 0 ? true : false;
    }
    /**
     * 獲取棧頂元素
     *
     * @return
     */
    public E pop() {
        // 如果棧容器中沒有元素則拋出異常
        if (this.index == -1) {
            throw new EmptyStackException();
        }
        // 記錄元素個數
        this.size--;
        // 返回棧頂元素
        System.out.println("刪除元素之前的當前下標："+index);
        return (E) this.arr[index--];
    }

    /**
     * 向棧頂添加元素
     *
     * @param item
     * @return
     */
    public E push(E item) {
        // 初始化數組
        this.capacity();
        // 向數組中添加元素
        System.out.println("添加元素之前的下標："+index);
        this.arr[++index] = item;
        System.out.println("添加元素之後的下標："+index);
        // 記錄元素個數
        this.size++;
        return item;
    }
    /**
     * 數組初始化或者以1.5倍容量對數組擴容
     */
    private void capacity() {
        // 數組初始化
        if (this.arr == null) {
            this.arr = new Object[this.stackLength];
        }
        // 以1.5倍對數組擴容
        if (this.size - (this.stackLength - 1) >= 0) { // 如果當前數組的元素個數大於瞭當前數組的最後一個索引值
            this.stackLength = this.stackLength + (this.stackLength >> 1); // 位運算，讓長度變成原來的1/2
            this.arr = Arrays.copyOf(this.arr, this.stackLength); // 復制一個新的數組，用新開辟的長度
        }
    }
    public static void main(String[] args) {
        MyStack<String> stack = new MyStack<>();
        stack.push("a");
        stack.push("b");
        stack.push("c");
        System.out.println(stack.size);
        System.out.println("當前棧頂元素："+stack.pop());
        /*System.out.println(stack.pop());
        System.out.println(stack.pop());*/
    }
}

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望能夠您能夠關註WalkonNet的更多內容！

推薦閱讀：