溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
棧介紹
棧是一個先入后出的有序列表。
棧是限制線性表中元素的插入和刪除只能在線性表中同一端進行的一種特殊的線性表，允許插入和刪除的一端，為變化的一端，稱為棧頂，另一端為固定的一端，稱為棧底。
最先放入棧中的元素在棧底，最后放入的元素在棧頂。
最先出棧的元素在棧頂，最后出棧的元素在棧底。
分析
使用數組來模擬棧的實現，首先考慮到數組的長度是固定的，所以使用棧就必須給一個特定的長度，即最大長度MaxSize。自定義一個棧頂指針， 初始化數據為-1，因為數組的索引值是從0開始的，為了不引起沖突，從-1開始。
棧為空：當top=-1時，即等于初始化數據，沒有任何元素存在數組中，則說明棧為空。
棧滿：隨著添加元素，棧頂指針將會往后移動，但是要考慮到數組的長度是固定的，就存在一個滿的情況。判斷條件是當top=MaxSize-1時，棧就滿了。比如定義3個大小的數組，放入一個數據1，top從-1變為0，再放入一個數據2，top從0變成1，再放入一個數據3，top從1變成2.這時候數組已經滿了，判斷條件即為top =MaxSize，為棧滿。
進棧：進棧前先判斷棧是否滿了，否則不能進棧。將top+1，在將數組索引為top的元素賦值為添加進來的數據。
出棧：出棧前先判斷棧是否為空，否則不能出棧。如果不為空，先取棧頂的元素，即索引值為top的元素，然后在將top-1。
遍歷棧：遍歷時也要判斷棧中是否為空，遍歷數據也是從棧頂元素開始遍歷， 一直遍歷到棧底就結束了。
代碼實現
package cn.mrlij.stack;
import java.util.Arrays;
import java.util.Scanner;
/**
* 使用數組實現棧
*
* @author dreamer
*
*/
public class ArrayStackDemo {
public static void main(String[] args) {
// 測試
ArrayStack a = new ArrayStack(5);
boolean flag = true;// 用于判斷循環結束的標志
Scanner sc = new Scanner(System.in);
String key = "";// 用于接受菜單的選項
while (flag) {
System.out.println("show：顯示棧");
System.out.println("exit：退出程序");
System.out.println("push：進棧");
System.out.println("pop：出棧");
key = sc.nextLine();
switch (key) {
case "show":
a.show();
break;
case "exit":
flag = false;
System.out.println("程序結束！");
break;
case "push":
System.out.println("請輸入要進棧的數據：");
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;// 定義數組的最大長度
private int[] arr;// 定義數組，數據就放在該數組
private int top = -1;// 定義棧頂，初始化數據為-1
public ArrayStack(int maxSize) {
this.MaxSize = maxSize;
arr = new int[MaxSize];
}
// 判斷數組是否為空
public boolean isEmpty() {
return top == -1;
}
// 判斷數組是否滿了
public boolean isFull() {
System.out.println("棧頂：" + top + "最大長度：" + MaxSize);
return top == MaxSize - 1;
}
// 進棧
public void push(int val) {
// 先判斷棧是否滿了，滿了就不能添加進去
if (isFull()) {
System.out.println("棧已經滿了~~");
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("沒有數據");
return;
}
for (int i = top; i >= 0; i--) {
System.out.print(arr[i] + "\t");
}
System.out.println();
}
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
