java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):棧

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

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

準(zhǔn)備工作

工具：idea+jdk8

技術(shù)要求：java基礎(chǔ)語法

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

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

在這里插入圖片描述

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

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

Objects[] arr;

數(shù)組定義好了之后呢，想想，我們?cè)趺慈カ@取到棧尾部或者棧首的元素呢？還記得數(shù)組的索引嗎？可以用索引來假設(shè)為棧的指針。所以，我們還得定義好棧的元素個(gè)數(shù)和棧的默認(rèn)長(zhǎng)度以及默認(rèn)的指針：

private int stackLength = 4; // 數(shù)組的默認(rèn)長(zhǎng)度
private int size; // 記住棧容器的元素個(gè)數(shù)
private int index = -1; // 操作數(shù)組下標(biāo)位置的指針

為什么這兒指向的是-1呢？我們知道，數(shù)組的第一個(gè)元素是索引為0，那么-1的意思就是不指向任何元素。待會(huì)兒我們?cè)谟玫臅r(shí)候再去指向他。

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

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

push方法

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

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

pop方法

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

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

刪除之后，對(duì)應(yīng)的size長(zhǎng)度該怎么去改變？

我們知道，當(dāng)元素添加了之后，index會(huì)跟著改變，那么就好比我們添加了三個(gè)元素，此時(shí)的index應(yīng)該就是指向的2。那就好辦了。

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

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

empty方法

判斷棧是否為空，這很簡(jiǎn)單。直接判斷當(dāng)前的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; // 存放元素的物理結(jié)構(gòu)
    private int stackLength = 4; // 數(shù)組的默認(rèn)長(zhǎng)度
    private int size; // 記住棧容器的元素個(gè)數(shù)
    private int index = -1; // 操作數(shù)組下標(biāo)位置的指針
    /**
     * 判斷棧容器是否為空
     */
    public boolean empty() {
        return this.size == 0 ? true : false;
    }
    /**
     * 獲取棧頂元素
     *
     * @return
     */
    public E pop() {
        // 如果棧容器中沒有元素則拋出異常
        if (this.index == -1) {
            throw new EmptyStackException();
        }
        // 記錄元素個(gè)數(shù)
        this.size--;
        // 返回棧頂元素
        System.out.println("刪除元素之前的當(dāng)前下標(biāo)："+index);
        return (E) this.arr[index--];
    }

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