資料結構中的堆疊不要與Java 中的堆疊混淆，他們兩個不是一回事，資料結構中的堆疊是一種受限制的線性表，堆疊具有先進後出、後進先出的特點，因為棧只允許存取最後一個資料項，也就是最後插入的資料項。也許你會有疑問，棧既然有這麼多限制，為什麼不用陣列或鍊錶而使用棧？在開發中，我們有特定的場景，根據特定的場景去選用資料結構，棧的適用場景非常多，例如瀏覽器的前進與後退、字串括號的合法性等，我們使用棧來實現就比較好，因為堆疊相對數組、鍊錶來說對外提供的介面要少很多，介面少了，出錯的機率就減少了，對風險的可控性就提高了。
推薦教學：PHP影片教學
#實作一個棧
從棧的定義可以看出，棧主要有兩個操作，一個是新增一條數據，我們叫做入棧，另一個是獲取一條數據，稱為出棧，下面兩張圖是入棧出棧示意圖。
棧的實作有兩種方式，一種是基於陣列實作的，我們叫作順序棧，另一種是基於鍊錶實作的，我們叫作鍊式棧。下面是兩個堆疊的實作程式碼
基於陣列的順序堆疊
/**
* 基于数组的顺序栈
*/
public class ArrayStack { // 栈最大容量
private int maxSzie; // 存放内容
private String[] array; // 栈顶元素
private int top;
public ArrayStack(int size){
this.maxSzie = size;
this.array = new String[this.maxSzie];
this.top = 0;
}
/**
* 入栈操作
*
* @param data 数据
* @return 0：入栈失败 1：入栈成功
*/
public int push(String data) {
if (top == maxSzie) return 0;
array[top] = data;
top++;
return 1;
}
/**
* 出栈操作
*
* @return
*/
public String pop() {
if (top == 0) return null;
return array[--top];
}
/**
* 获取栈顶元素
*
* @return
*/
public String peek() {
return array[top - 1];
}
/**
* 判断栈是否为空
* @return
*/
public boolean isEmpty() {
return top == 0;
}
}登入後複製
##基於鍊錶的鍊式堆疊
/**
* 基于链表的链式栈
*/public class LinkStack { // 始终指向栈的第一个元素
private Node top = null;
/**
* 压栈
*
* @param data
* @return
*/
public int push(String data) {
Node node = new Node(data);
if (top == null) {
top = node;
} else {
node.next = top;
top = node;
}
return 1;
}
/**
* 出栈
*
* @return
*/
public String pop() {
if (top == null) return null;
String data = top.getData();
top = top.next;
return data;
}
/**
* 节点信息
*/
private static class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
this.next = null;
}
public String getData() {
return this.data;
}
}
}登入後複製
棧的實作比較簡單，因為堆疊涉及的操作不多，主要就入棧和出棧兩個操作。
堆疊的應用
#偵測字串括號的合法性
我們有時候需要偵測字串括號的合法性，也就是一個左括號需要符合一個右括號，這個我們可以使用堆疊來實作。我們可以從一個合法的括號來理解為什麼要使用棧？如果括號使用合法，最後一個左括號跟第一個右括號是匹配的，倒數第二個左括號和第二個右括號匹配的，以此類推，這符合我們棧的特性先進後出。
假設我們有三種括號：圓括號 ()、方括號 [] 和花括號{}，我們使用堆疊來偵測括號的合法性。我們將左括號全部壓棧，當出現右括號時，我們就進行匹配，這時候有如下三種情況：
●棧為空，說明沒有左括號，括號使用不合法
●棧中取出來的左括號跟右括號不匹配，括號使用不合法
●棧中取出的左括號跟右括號匹配，括號使用暫時合法
當整個字串都掃描完成後，偵測堆疊中是否還有值，如果棧為空，則表示括號使用合法，反正，則括號使用不合法。
實作程式碼
public static boolean BracketChecker(String data) {
char[] chars = data.toCharArray();
ArrayStack stack = new ArrayStack(chars.length);
for (char ch : chars) {
switch (ch){
case '{':
case '[':
case '(':
stack.push(ch);
break;
case '}':
case ']':
case ')':
if (!stack.isEmpty()){
char ch1 = stack.pop();
if ((ch=='}' && ch1 !='{')
||(ch==']' && ch1 !='[')
||(ch==')' && ch1 !='(')
){
return false;
}
}else {
return false;
}
break;
default:
break;
}
}
return stack.isEmpty();
}登入後複製
瀏覽器前進、後退功能
我們使用瀏覽器都知道，瀏覽器可以前進、後退功能，瀏覽器的前進後退也符合棧的特點，我們最先訪問的網頁肯定要最後才能倒回去。我們一起來看看棧怎麼實現這個功能？
我們需要定義兩個棧，我們將首次訪問的頁面壓棧到第一個棧中，當點擊後退時，從第一個棧中取出資料放入到第二個棧，當點擊前進按鈕時，從第二個棧取出資料放入第一個棧。當第一個棧沒有資料時，表示沒有頁面可以點擊後退了，當第二個棧沒有資料時，表示沒有頁面可以點擊前進了。這樣我們就透過棧實現了瀏覽器前進、後退功能。
以上是程式設計師，你該知道的資料結構之棧的詳細內容。更多資訊請關注PHP中文網其他相關文章！
