相關(guān)文章
Java用鏈表實現(xiàn)棧
Java用數(shù)組實現(xiàn)隊列
Java用鏈表實現(xiàn)隊列
堆棧是一種線性結(jié)構(gòu)，也是一種特殊的線性表。它只在一端進行插入（入棧）或者刪除（出棧），這一端稱為棧頂，遵循后入先出的原則。
堆棧示意圖
可以使用一個數(shù)組和一個記錄棧頂位置的變量來實現(xiàn)棧的順序存儲結(jié)構(gòu)。具體代碼實現(xiàn)如下：
public class Mystack {
private int top;
private int maxSize;
private Object[] arr;
//無參構(gòu)造
//帶參構(gòu)造
//setter
//getter
public void Push(Object vaule) {
if(top == maxSize - 1) {
System.out.println("該棧已經(jīng)滿了"); //如果top=棧的最大長度，則說明棧中空間已經(jīng)放滿了
}else {
arr[++top] = vaule; //棧中還有足夠的空間，將棧頂位置+1，放入壓棧元素
System.out.println("壓棧元素為" + arr[top]);
}
}
public void Pop() {
if(top == -1) {
System.out.println("這是一個空棧"); //如果top=-1，則說明棧中沒有元素
}else {
Object vaule = arr[top];
arr[top--] = null; // 取出棧頂元素，棧頂位置-1，原棧頂為null
System.out.println("出棧元素為" + vaule);
}
}
}
//main測試
public static void main(String[] args) {
Object[] a = new Object[8]; //創(chuàng)建一個數(shù)組
String[] arr1 = {"1", "2", "3", "4", "5"}; //待壓棧的數(shù)組
int maxSize = a.length;
System.out.println("棧的長度是" + maxSize);
Mystack mystack = new Mystack(-1, maxSize, a); //創(chuàng)建一個棧對象
for (int i = 0; i < arr1.length; i++) {
mystack.Push(arr1[i]); //壓棧
}
System.out.println("--------------");
for (int i = 0; i < 2; i++) {
mystack.Pop(); //出棧
}
for (int i = 0; i < a.length; i++) {
System.out.println("----------");
System.out.println(a[i]); //觀察棧里的情況
}
}
輸出結(jié)果為：
棧的長度是8
壓棧元素為1
壓棧元素為2
壓棧元素為3
壓棧元素為4
壓棧元素為5
--
出棧元素為5
出棧元素為4
--
1
2
3
null
null
null
null
null
如何用一個數(shù)組實現(xiàn)兩個堆棧，要求最大程度利用數(shù)組空間
要完成上述要求，那么我們在有元素入棧時，只要棧中有空間，就需要進行入棧操作。這樣的話，無非兩種方法，一種是將數(shù)組從中間開辟成兩個棧，中間位置便是棧底，向兩邊進行入棧。
對于這種方法，存在一個弊端，如果其中一個堆棧滿了，而另外一個堆棧有空余空間，這樣就會造成空間的浪費。
方法一
為了解決這個問題，我們可以把數(shù)組的兩端作為兩個棧底，有元素入棧時，一同朝中間入棧。這樣只要數(shù)組有空余空間，那么就可以進行入棧操作。
方法二
具體代碼實現(xiàn)如下：
public class Mystack {
private int top1;
private int top2;
private int maxSize;
private Object[] arr;
//無參構(gòu)造
//帶參構(gòu)造
//setter
//getter
public void Push(Object vaule, int flag) {
if (top2 - top1 == 1) {
System.out.println("該棧已經(jīng)滿了"); //棧1是空棧時，其棧頂位置為-1；棧2是空棧時，其棧頂位置為棧最大長度；如果兩個棧頂位置差為1，則說明棧中空間已滿
} else {
if (flag == 1) {
arr[++top1] = vaule; //對棧1操作
System.out.println("壓棧元素為" + arr[top1]); //棧中還有足夠的空間，將棧頂位置+1，放入壓棧元素
} else {
arr[--top2] = vaule; //對棧2操作
System.out.println("壓棧元素為" + arr[top2]); //棧中還有足夠的空間，將棧頂位置-1，放入壓棧元素
}
}
}
public void Pop(int flag) {
if (flag == 1) { //對棧1操作
if (top1 == -1) {
System.out.println("這是一個空棧"); //對棧1，如果top1=-1，則說明棧中沒有元素
} else {
Object vaule = arr[top1];
arr[top1--] = null; // 取出棧頂元素，棧頂位置-1，原棧頂為null
System.out.println("出棧元素為" + vaule);
}
} else { //對棧2操作
if (top2 == maxSize) {
System.out.println("這是一個空棧"); //對棧2，如果top2=棧最大長度，則說明棧中沒有元素
} else {
Object vaule = arr[top2];
arr[top2++] = null; // 取出棧頂元素，棧頂位置+1，原棧頂為null
System.out.println("出棧元素為" + vaule);
}
}
}
}
//main測試
public static void main(String[] args) {
int flag1 = 1;
int flag2 = 1;
Object[] arr1 = new Object[4];
String[] arr2 = {"1", "2", "3", "4", "5"}; //待壓棧的數(shù)組
int maxSize = arr1.length;
Mystack mystack = new Mystack(-1, maxSize, maxSize, arr1);
for (int i = 0; i < arr2.length; i++) {
if (flag1 == 3) {
flag1 = 1; //切換堆棧
}
mystack.Push(arr2[i], flag1);
flag1 += 1;
}
System.out.println("------------");
for (int i = 0; i < arr2.length; i++) {
if (flag2 == 3) {
flag2 = 1;
}
mystack.Pop(flag2);
flag2 += 1;
}
System.out.println("------------");
for (int i = 0; i < arr1.length; i++) {
System.out.println(arr1[i]);
}
}
輸出結(jié)果為：
壓棧元素為1
壓棧元素為2
壓棧元素為3
壓棧元素為4
壓棧元素為5
--
出棧元素為5
出棧元素為4
--
1
3
null
null
null
null
null
2
