java數(shù)據結構基礎:棧

更新時間：2021年07月27日 15:04:33 作者：魚小洲

這篇文章主要介紹了Java的數(shù)據解構基礎，希望對廣大的程序愛好者有所幫助，同時祝大家有一個好成績,需要的朋友可以參考下，希望能給你帶來幫助

準備工作

工具：idea+jdk8

技術要求：java基礎語法

編碼環(huán)節(jié)

首先，我們得先確定下來，用什么數(shù)據來模擬棧的操作。由于是一個一個的元素放入棧里面，我們可以考慮用數(shù)組來實現(xiàn)。

在這里插入圖片描述

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

所以我們事先得定義一個數(shù)組：

Objects[] arr;

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

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

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

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

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

push方法

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

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

pop方法

pop方法主要是用來移除棧頂?shù)脑亍?br />

先分析一下思路：我們要用index去指向棧頂?shù)脑?，該怎么去指定?br />

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

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

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

/**
 * 獲取棧頂元素
 *
 * @return
 */
public E pop() {
    // 如果棧容器中沒有元素則拋出異常
    if (this.index == -1) {
        throw new EmptyStackException();
    }
    // 記錄元素個數(shù)
    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; // 數(shù)組的默認長度
    private int size; // 記住棧容器的元素個數(shù)
    private int index = -1; // 操作數(shù)組下標位置的指針
    /**
     * 判斷棧容器是否為空
     */
    public boolean empty() {
        return this.size == 0 ? true : false;
    }
    /**
     * 獲取棧頂元素
     *
     * @return
     */
    public E pop() {
        // 如果棧容器中沒有元素則拋出異常
        if (this.index == -1) {
            throw new EmptyStackException();
        }
        // 記錄元素個數(shù)
        this.size--;
        // 返回棧頂元素
        System.out.println("刪除元素之前的當前下標："+index);
        return (E) this.arr[index--];
    }

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