利用數(shù)組實現(xiàn)棧（Java實現(xiàn)）

更新時間：2019年09月25日 15:32:41 作者：dreamer_it

這篇文章主要為大家詳細(xì)介紹了利用數(shù)組實現(xiàn)棧，具有一定的參考價值，感興趣的小伙伴們可以參考一下

棧介紹

棧是一個先入后出的有序列表。

棧是限制線性表中元素的插入和刪除只能在線性表中同一端進(jìn)行的一種特殊的線性表，允許插入和刪除的一端，為變化的一端，稱為棧頂，另一端為固定的一端，稱為棧底。

最先放入棧中的元素在棧底，最后放入的元素在棧頂。

最先出棧的元素在棧頂，最后出棧的元素在棧底。

分析

使用數(shù)組來模擬棧的實現(xiàn)，首先考慮到數(shù)組的長度是固定的，所以使用棧就必須給一個特定的長度，即最大長度MaxSize。自定義一個棧頂指針，初始化數(shù)據(jù)為-1，因為數(shù)組的索引值是從0開始的，為了不引起沖突，從-1開始。

棧為空：當(dāng)top=-1時，即等于初始化數(shù)據(jù)，沒有任何元素存在數(shù)組中，則說明棧為空。

棧滿：隨著添加元素，棧頂指針將會往后移動，但是要考慮到數(shù)組的長度是固定的，就存在一個滿的情況。判斷條件是當(dāng)top=MaxSize-1時，棧就滿了。比如定義3個大小的數(shù)組，放入一個數(shù)據(jù)1，top從-1變?yōu)?，再放入一個數(shù)據(jù)2，top從0變成1，再放入一個數(shù)據(jù)3，top從1變成2.這時候數(shù)組已經(jīng)滿了，判斷條件即為top =MaxSize，為棧滿。

進(jìn)棧：進(jìn)棧前先判斷棧是否滿了，否則不能進(jìn)棧。將top+1，在將數(shù)組索引為top的元素賦值為添加進(jìn)來的數(shù)據(jù)。

出棧：出棧前先判斷棧是否為空，否則不能出棧。如果不為空，先取棧頂?shù)脑?，即索引值為top的元素，然后在將top-1。

遍歷棧：遍歷時也要判斷棧中是否為空，遍歷數(shù)據(jù)也是從棧頂元素開始遍歷，一直遍歷到棧底就結(jié)束了。

代碼實現(xiàn)

package cn.mrlij.stack;
 
import java.util.Arrays;
import java.util.Scanner;
 
/**
 * 使用數(shù)組實現(xiàn)棧
 * 
 * @author dreamer
 *
 */
public class ArrayStackDemo {
 public static void main(String[] args) {
 // 測試
 ArrayStack a = new ArrayStack(5);
 boolean flag = true;// 用于判斷循環(huán)結(jié)束的標(biāo)志
 Scanner sc = new Scanner(System.in);
 String key = "";// 用于接受菜單的選項
 while (flag) {
 System.out.println("show：顯示棧");
 System.out.println("exit：退出程序");
 System.out.println("push：進(jìn)棧");
 System.out.println("pop：出棧");
 key = sc.nextLine();
 switch (key) {
 case "show":
 a.show();
 break;
 case "exit":
 flag = false;
 System.out.println("程序結(jié)束！");
 break;
 
 case "push":
 
 System.out.println("請輸入要進(jìn)棧的數(shù)據(jù)：");
 int val = sc.nextInt();
 a.push(val);
 
 break;
 case "pop":
 try {
 int pop = a.pop();
 System.out.println("出棧的值是：" + pop);
 } catch (Exception e) {
 // TODO: handle exception
 System.out.println(e.getMessage());
 }
 break;
 default:
 break;
 }
 
 }
 
 }
}
 
class ArrayStack {
 private int MaxSize;// 定義數(shù)組的最大長度
 private int[] arr;// 定義數(shù)組，數(shù)據(jù)就放在該數(shù)組
 private int top = -1;// 定義棧頂，初始化數(shù)據(jù)為-1
 
 public ArrayStack(int maxSize) {
 this.MaxSize = maxSize;
 arr = new int[MaxSize];
 }
 
 // 判斷數(shù)組是否為空
 public boolean isEmpty() {
 
 return top == -1;
 }
 
 // 判斷數(shù)組是否滿了
 public boolean isFull() {
 System.out.println("棧頂：" + top + "最大長度：" + MaxSize);
 return top == MaxSize - 1;
 }
 
 // 進(jìn)棧
 public void push(int val) {
 // 先判斷棧是否滿了，滿了就不能添加進(jìn)去
 if (isFull()) {
 System.out.println("棧已經(jīng)滿了~~");
 return;
 }
 top++;
 arr[top] = val;
 }
 
 // 出棧
 public int pop() {
 // 先判斷棧是否為空
 if (isEmpty()) {
 throw new RuntimeException("棧為空，無法出棧！");
 }
 int val = arr[top];
 top--;
 return val;
 }
 
 public void show() {
 if (isEmpty()) {
 System.out.println("沒有數(shù)據(jù)");
 return;
 }
 for (int i = top; i >= 0; i--) {
 System.out.print(arr[i] + "\t");
 }
 System.out.println();
 }
 
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: