|
 # 順序棧與鏈?zhǔn)綏５膱D解與實(shí)現(xiàn)
如上圖所示，對(duì)棧的增刪操作都只能在末端也就是棧頂操作， 棧既然是線性表那么就存在表頭和表尾，不過(guò)在棧結(jié)構(gòu)中，對(duì)其都進(jìn)行限制改造，表尾用來(lái)輸入數(shù)據(jù)也叫做棧頂（top）,相應(yīng)的 表頭就是棧底（bottom），棧頂和棧頂是兩個(gè)指針用來(lái)表示這個(gè)棧 與線性表類似，棧也是又順序表示和鏈?zhǔn)奖硎?，分別稱作順序棧和鏈棧
棧的基本操作如何通過(guò)棧這個(gè)后進(jìn)先出的線性表，來(lái)實(shí)現(xiàn)增刪查呢？ 初始時(shí)，棧內(nèi)沒(méi)有數(shù)據(jù)，即空棧。此時(shí)棧頂就是棧底。 當(dāng)存入數(shù)據(jù)時(shí)，最先放入的數(shù)據(jù)會(huì)進(jìn)入棧底。接著加入的數(shù)據(jù)都會(huì)放入到棧頂?shù)奈恢谩?/p> 如果要?jiǎng)h除數(shù)據(jù)，也只能通過(guò)訪問(wèn)棧頂?shù)臄?shù)據(jù)并刪除。對(duì)于棧的新增操作，通常也叫作 push 或壓棧。 對(duì)于棧的刪除操作，通常也叫作 pop或出棧。對(duì)于壓棧和出棧，我們分別基于順序棧和鏈棧來(lái)分析
順序棧順序棧即就是順序存儲(chǔ)元素的，通常順序棧我們可以通過(guò)數(shù)組來(lái)實(shí)現(xiàn)，將數(shù)組的首元素放在棧底，最后一個(gè)元素放在棧頂，之后指定一個(gè) top 指針指向棧頂元素的位置 當(dāng)棧中只有一個(gè)元素是，此時(shí) top=0 ，一般以 top 是否為 -1 來(lái)判定是否為空棧，當(dāng)定義了棧的最大容量時(shí)，則棧頂 top 必須小于最大容量值 下面我們通過(guò) Java 代碼實(shí)現(xiàn)一個(gè)順序棧,非常簡(jiǎn)單如下：
/**
* @url: i-code.online
* @author: 云棲簡(jiǎn)碼
* @time: 2020/12/8 16:48
*/
public class Stack<T> {
private Object[] stack;
private int stackSize;
private int top = -1;
public Stack(int size){
stackSize = size;
stack = new Object[size];
}
public void push(T value){
if (top < stackSize-1){
top++;
stack[top] = value;
return;
}
throw new ArrayIndexOutOfBoundsException(top +"越界");
}
public T pop(){
if (top > -1){
top--;
return (T) stack[top+1];
}
throw new ArrayIndexOutOfBoundsException(top +"越界");
}
public boolean empty(){
return top == -1;
}
}對(duì)于查找操作，棧沒(méi)有額外的改變，跟線性表一樣，它也需要遍歷整個(gè)棧來(lái)完成基于某些條件的數(shù)值查找,上述代碼中并未去實(shí)現(xiàn)該功能
鏈棧
在鏈?zhǔn)綏Ｖ羞M(jìn)行刪除操作時(shí)，只能在棧頂進(jìn)行操作。因此，將棧頂?shù)?top 指針指向棧頂元素的 next 指針即可完成刪除。對(duì)于鏈?zhǔn)綏?lái)說(shuō)，新增刪除數(shù)據(jù)元素沒(méi)有任何循環(huán)操作，其時(shí)間復(fù)雜度均為 O(1)。 通過(guò)代碼簡(jiǎn)單實(shí)現(xiàn)棧的操作，如下：
/**
* @url: i-code.online
* @author: 云棲簡(jiǎn)碼
* @time: 2020/12/8 20:57
*/
public class LinkedList<E> {
private Node<E> top = new Node<>(null,null);
public void push(E e){
Node<E> node = new Node<>(e,top.next);
top.next = node;
}
public E pop(){
if (top.next == null){
throw new NoSuchElementException();
}
final Node<E> next = top.next;
top.next = next.next;
return next.item;
}
private static class Node<E>{
E item;
Node<E> next;
public Node(E item, Node<E> next){
this.item = item;
this.next = next;
}
}
}對(duì)于查找操作，相對(duì)鏈表而言，鏈棧沒(méi)有額外的改變，它也需要遍歷整個(gè)棧來(lái)完成基于某些條件的數(shù)值查找。
棧的案例有效括號(hào)給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。有效字符串需滿足：左括號(hào)必須與相同類型的右括號(hào)匹配，左括號(hào)必須以正確的順序匹配。例如，{ [ ( ) ( ) ] } 是合法的，而{ ( [ ) ] }是非法的。 這個(gè)問(wèn)題很適合采用棧來(lái)處理。原因是，在匹配括號(hào)是否合法時(shí)，左括號(hào)是從左到右依次出現(xiàn)，而右括號(hào)則需要按照“后進(jìn)先出”的順序依次與左括號(hào)匹配。因此，實(shí)現(xiàn)方案就是通過(guò)棧的進(jìn)出來(lái)完成。 具體的實(shí)現(xiàn)思路，我們可以遍歷字符串從左起，當(dāng)遇到左括號(hào)時(shí)進(jìn)行壓榨操作，而到遇到右括號(hào)時(shí)則繼續(xù)出棧，判斷出棧的括號(hào)是否與當(dāng)前的右括號(hào)是一對(duì)，如果不是則非法，如果一致則繼續(xù)遍歷直到結(jié)束 代碼如下：
public boolean isValid(String s) {
Stack stack = new Stack();
for(int i =0;i<s.length();i++){
char curr = s.charAt(i);
if (isLeft(curr)) {
stack.push(curr);
}else {
if (stack.empty())
return false;
if (!isPair(curr,(char)stack.pop())){
return false;
}
}
}
if (stack.empty()){
return true;
}else {
return false;
}
}
public boolean isPair(char curr,char expt){
if ((expt == '[' && curr == ']') || (expt == '{' && curr == '}') || (expt == '(' && curr == ')'))
return true;
return false;
}
public boolean isLeft(char c){
if (c == '{' || c == '[' || c == '(')
return true;
return false;
}總結(jié)棧繼承了線性表特性，是一個(gè)特殊的線性表 棧只允許數(shù)據(jù)從棧頂進(jìn)出，即棧的特性先進(jìn)后出 不管是順序棧還是鏈?zhǔn)綏?，它們?duì)于數(shù)據(jù)的新增操作和刪除操作的時(shí)間復(fù)雜度都是 O(1)。而在查找操作中，棧和線性表一樣只能通過(guò)全局遍歷的方式進(jìn)行，也就是需要 O(n) 的時(shí)間復(fù)雜度 當(dāng)我們面臨頻繁增刪節(jié)點(diǎn)，同時(shí)數(shù)據(jù)順序有后來(lái)居上的特點(diǎn)時(shí)棧就是個(gè)不錯(cuò)的選擇。例如，瀏覽器的前進(jìn)和后退，括號(hào)匹配等問(wèn)題
|
