|
 # 順序棧與鏈?zhǔn)綏５膱D解與實(shí)現(xiàn)
如上圖所示，對棧的增刪操作都只能在末端也就是棧頂操作， 棧既然是線性表那么就存在表頭和表尾，不過在棧結(jié)構(gòu)中，對其都進(jìn)行限制改造，表尾用來輸入數(shù)據(jù)也叫做棧頂（top）,相應(yīng)的 表頭就是棧底（bottom），棧頂和棧頂是兩個指針用來表示這個棧 與線性表類似，棧也是又順序表示和鏈?zhǔn)奖硎荆謩e稱作順序棧和鏈棧
棧的基本操作如何通過棧這個后進(jìn)先出的線性表，來實(shí)現(xiàn)增刪查呢？ 初始時，棧內(nèi)沒有數(shù)據(jù)，即空棧。此時棧頂就是棧底。 當(dāng)存入數(shù)據(jù)時，最先放入的數(shù)據(jù)會進(jìn)入棧底。接著加入的數(shù)據(jù)都會放入到棧頂?shù)奈恢谩?/p> 如果要刪除數(shù)據(jù)，也只能通過訪問棧頂?shù)臄?shù)據(jù)并刪除。對于棧的新增操作，通常也叫作 push 或壓棧。 對于棧的刪除操作，通常也叫作 pop或出棧。對于壓棧和出棧，我們分別基于順序棧和鏈棧來分析
順序棧順序棧即就是順序存儲元素的，通常順序棧我們可以通過數(shù)組來實(shí)現(xiàn)，將數(shù)組的首元素放在棧底，最后一個元素放在棧頂，之后指定一個 top 指針指向棧頂元素的位置 當(dāng)棧中只有一個元素是，此時 top=0 ，一般以 top 是否為 -1 來判定是否為空棧，當(dāng)定義了棧的最大容量時，則棧頂 top 必須小于最大容量值 下面我們通過 Java 代碼實(shí)現(xiàn)一個順序棧,非常簡單如下：
/**
* @url: i-code.online
* @author: 云棲簡碼
* @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;
}
}對于查找操作，棧沒有額外的改變，跟線性表一樣，它也需要遍歷整個棧來完成基于某些條件的數(shù)值查找,上述代碼中并未去實(shí)現(xiàn)該功能
鏈棧
/**
* @url: i-code.online
* @author: 云棲簡碼
* @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;
}
}
}對于查找操作，相對鏈表而言，鏈棧沒有額外的改變，它也需要遍歷整個棧來完成基于某些條件的數(shù)值查找。
棧的案例有效括號給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。有效字符串需滿足：左括號必須與相同類型的右括號匹配，左括號必須以正確的順序匹配。例如，{ [ ( ) ( ) ] } 是合法的，而{ ( [ ) ] }是非法的。 這個問題很適合采用棧來處理。原因是，在匹配括號是否合法時，左括號是從左到右依次出現(xiàn)，而右括號則需要按照“后進(jìn)先出”的順序依次與左括號匹配。因此，實(shí)現(xiàn)方案就是通過棧的進(jìn)出來完成。 具體的實(shí)現(xiàn)思路，我們可以遍歷字符串從左起，當(dāng)遇到左括號時進(jìn)行壓榨操作，而到遇到右括號時則繼續(xù)出棧，判斷出棧的括號是否與當(dāng)前的右括號是一對，如果不是則非法，如果一致則繼續(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é)棧繼承了線性表特性，是一個特殊的線性表 棧只允許數(shù)據(jù)從棧頂進(jìn)出，即棧的特性先進(jìn)后出 不管是順序棧還是鏈?zhǔn)綏?，它們對于?shù)據(jù)的新增操作和刪除操作的時間復(fù)雜度都是 O(1)。而在查找操作中，棧和線性表一樣只能通過全局遍歷的方式進(jìn)行，也就是需要 O(n) 的時間復(fù)雜度 當(dāng)我們面臨頻繁增刪節(jié)點(diǎn)，同時數(shù)據(jù)順序有后來居上的特點(diǎn)時棧就是個不錯的選擇。例如，瀏覽器的前進(jìn)和后退，括號匹配等問題
|
