一：概述
????由圖我們可看成棧只能從棧頂存取元素，同時先進入的元素反而是后出嘿期，而棧頂永遠指向棧內最頂部的元素品擎。到此可以給出棧的正式定義：棧(Stack)是一種有序特殊的線性表，只能在表的一端(稱為棧頂备徐，top萄传，總是指向棧頂元素)執(zhí)行插入和刪除操作，最后插入的元素將第一個被刪除蜜猾，因此棧也稱為后進先出(Last In First Out,LIFO)或先進后出(First In Last Out FILO)的線性表秀菱。棧的基本操作創(chuàng)建棧振诬，判空，入棧衍菱，出棧赶么，獲取棧頂元素等，注意棧不支持對指定位置進行刪除梦碗，插入禽绪，其接口Stack聲明如下：
public interface Stack<T> {
// 棧是否為空
boolean isEmpty();
// 入棧
void push(T data);
// 取出棧頂元素蓖救，不出棧
T peek();
// 出棧
T pop();
}
二：順序棧的設計與實現(xiàn)
????順序棧洪规，顧名思義就是采用順序表實現(xiàn)的的棧，順序棧的內部以順序表為基礎循捺，實現(xiàn)對元素的存取操作斩例，當然我們還可以采用內部數(shù)組實現(xiàn)順序棧，在這里我們使用內部數(shù)據(jù)組來實現(xiàn)棧：
public class SeqStack<T> implements Stack<T>{
//棧頂索引从橘，-1代表空棧
private int top = -1;
//默認容量大小
private int capacity = 10;
//存放數(shù)據(jù)的數(shù)組
private T[] arr;
//棧的實際使用量
private int size;
public SeqStack() {
arr = (T[]) new Object[capacity];
}
//是否是空棧的判斷依據(jù)是top是否為-1;如果大于等于0念赶，說明棧中有元素
@Override
public boolean isEmpty() {
return top == -1;
}
//獲取棧頂元素，本例基于數(shù)組來實現(xiàn)棧恰力，所以棧頂元素叉谜，就是數(shù)組的最后一個元素
@Override
public T peek() {
//如果是空棧就拋出異常
if(isEmpty()) {
new EmptyStackException();
}
//返回數(shù)組的最后一個元素
return arr[top];
}
//獲取棧頂元素并出棧
@Override
public T pop() {
//國際慣例，空棧拋出異常
if(isEmpty()) {
new EmptyStackException();
}
size --;
//需要注意的是踩萎，這里不會將數(shù)組的最后一個元素置空停局，因為top的值已經修改
//下次再push的時候只是把原來的數(shù)組元素的值進行了修改，因為一旦pop后香府，
//top的值減小了董栽，原來的數(shù)組的元素永遠訪問不到，完全沒有必要置空.
return arr[top--];
}
//入棧
@Override
public void push(T data) {
//如果棧已滿企孩，那么擴容
if(size == arr.length) {
ensureCapacity(size*2+1);
}
//先將棧頂指針+1锭碳，然后將元素放入top + 1那個位置
arr[++top] = data;
size++;
}
//擴容的思路很簡單，創(chuàng)建一個新的數(shù)組勿璃，然后將原來數(shù)組的數(shù)據(jù)復制到新數(shù)組
private void ensureCapacity(int capacity) {
//以防萬一
if(capacity > size) {
return;
}
T[] old = arr;
arr = (T[]) new Object[capacity];
for(int i = 0 ; i < old.length ; i++) {
arr[i] = old[i];
}
}
}
????測試代碼：
public static void main(String[] args) {
SeqStack<String> stack = new SeqStack<>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
int l = stack.size;
System.out.println("size : " + l + " , top index : " + stack.top +
" , top : " + stack.peek());
for(int i = 0 ; i < l; i ++) {
stack.pop();
}
//此處拋出異常
System.out.println("size : " + l + " , top : " + stack.peek());
}
????測試結果：
push A , size : 1
push B , size : 2
push C , size : 3
push D , size : 4
size : 4 , top index : 3 , top : D
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at teststack.SeqStack.peek(SeqStack.java:58)
at teststack.SeqStack.main(SeqStack.java:42)
????從上面可以看出擒抛，順序棧的邏輯很簡單，就是操作底層的數(shù)組而已补疑，所有的入棧和出棧操作歧沪，都是往數(shù)組添加和刪除元素，然后改變top指針的位置癣丧。
????以上就是順序棧的實現(xiàn)槽畔，簡單。
三：鏈式棧的設計與實現(xiàn)
public class LinkStack<T> implements Stack<T>{
//棧頂元素
private Node<T> top;
private int size;
public LinkStack() {
top = new Node<T>();
}
//如果棧頂元素為空斧拍，或者棧頂元素的數(shù)據(jù)為空雀扶，一律視為空棧
@Override
public boolean isEmpty() {
return top == null || top.data == null;
}
@Override
public void push(T data) {
if (data == null) {
try {
throw new Exception("data can\'t be null");
} catch (Exception e) {
e.printStackTrace();
}
}
//如果棧頂節(jié)點是空的話，那么創(chuàng)建一個新的節(jié)點當做棧頂節(jié)點
if (top == null) {
top = new Node<>(data);
//如果棧頂節(jié)點的數(shù)據(jù)為空的話肆汹，那么將數(shù)據(jù)賦值給該節(jié)點
} else if (top.data == null) {
top.data = data;
//如果棧頂節(jié)點和數(shù)據(jù)都不為空愚墓，說明不是空棧，這時候需要創(chuàng)建一個
//新的節(jié)點昂勉，將它賦值給棧頂節(jié)點浪册，同時將它的next指向當前的棧頂節(jié)點
} else {
Node<T> p = new Node<T>(data, this.top);
top = p;
}
size++;
}
// 獲取棧頂元素，我們一直持有棧頂節(jié)點的引用岗照，直接返回好了
@Override
public T peek() {
if (isEmpty()) {
new EmptyStackException();
}
return top.data;
}
//出棧村象，就是將棧頂節(jié)點的下一個節(jié)點當做新的棧頂節(jié)點，
//實質上就是移除鏈表中的頭結點谴返，很簡單
@Override
public T pop() {
if (isEmpty()) {
new EmptyStackException();
}
T data = top.data;
top = top.next;
size--;
return data;
}
//節(jié)點
class Node<T> {
public T data;
public Node<T> next;
public Node() {
}
public Node(T data) {
this.data = data;
}
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
????測試代碼：
public static void main(String[] args) {
LinkStack<String> sl = new LinkStack<>();
sl.push("A");
sl.push("B");
sl.push("C");
int length = sl.size;
for (int i = 0; i < length; i++) {
System.out.println("sl.pop->" + sl.pop() + " , size : " + sl.size);
}
sl.push("T");
System.out.println("sl.pop->" + sl.peek() + " , size : " + sl.size);
}
????測試結果：
sl.pop->C , size : 2
sl.pop->B , size : 1
sl.pop->A , size : 0
sl.pop->T , size : 1
????綜上可知煞肾，棧的實現(xiàn)還是很簡單的，下面講下棧的應用場景嗓袱。
四：棧的應用
????棧是一種很重要的數(shù)據(jù)結構籍救，在計算機中有著很廣泛的應用，如下一些操作都應用到了棧：
????符號匹配
????中綴表達式轉換為后綴表達式
????計算后綴表達式
????實現(xiàn)函數(shù)的嵌套調用
????HTML和XML文件中的標簽匹配
????網頁瀏覽器中已訪問頁面的歷史記錄
????符號匹配：
????在編寫程序的過程中渠抹，我們經常會遇到諸如圓括號“()”與花括號“{}”蝙昙，這些符號都必須是左右匹配的，這就是我們所說的符合匹配類型梧却，當然符合不僅需要個數(shù)相等奇颠，而且需要先左后右的依次出現(xiàn)，否則就不符合匹配規(guī)則放航，如“)(”烈拒，明顯是錯誤的匹配，而“()”才是正確的匹配。有時候符合如括號還會嵌套出現(xiàn)荆几，如“9-(5+(5+1))”,而嵌套的匹配原則是一個右括號與其前面最近的一個括號匹配吓妆，事實上編譯器幫我檢查語法錯誤是也是執(zhí)行一樣的匹配原理，而這一系列操作都需要借助棧來完成吨铸，接下來我們使用棧來實現(xiàn)括號”()”是否匹配的檢測行拢。
????判斷原則如下（str=”((5-3)*8-2)”）：
????a.設置str是一個表達式字符串，從左到右依次對字符串str中的每個字符char進行語法檢測诞吱，如果char是舟奠，左括號則入棧，如果char是右括號則出棧(有一對匹配就可以去匹配一個左括號房维，因此可以出棧)沼瘫，若此時出棧的字符char為左括號，則說明這一對括號匹配正常握巢，如果此時棧為空或者出棧字符不為左括號晕鹊，則表示缺少與char匹配的左括號松却，即目前不完整暴浦。
????b.重復執(zhí)行a操作，直到str檢測結束晓锻，如果此時棧為空歌焦，則全部括號匹配，如果棧中還有左括號砚哆，是說明缺少右括號独撇。
????接著我們用棧作為存儲容器通過代碼來實現(xiàn)這個過程
public class CheckExpression {
public static String isValid(String expstr){
//創(chuàng)建棧
LinkedStack<String> stack = new LinkedStack<>();
int i = 0 ;
//遍歷字符串，挨個取出每個字符
while(i < expstr.lenght()){
char c = expstr.charAt(i);
i++;
switch (ch){
//如果該字符是左括號躁锁，那么放入棧中
case '(' :
stack.push(ch + "");
break;
//如果是右括號纷铣，那么將左括號出棧
case ")" :
if(stack.isEmpty() || !stack.pop().equals("(")) {
return "FAILURE";
}
}
}
//經過這么一輪循環(huán)，如果棧為空战转，說明每個左括號都有
//右括號和他匹配搜立，這時候校驗通過，否則不通過
if(stack.isEmpty()) {
return "PASS";
}else {
return "FAILURE";
}
}
}
????測試代碼：
String expstr="((5-3)*8-2)";
System.out.println(expstr + " check " + check(expstr));
String expstr1="((5-3)*8-2";
System.out.println(expstr1 + " check " + check(expstr1));
????測試結果：
((5-3)*8-2) check PASS
((5-3)*8-2 check FAILURE
摘自：https://blog.csdn.net/javazejian/article/details/53362993
