目錄

一定義.

入棧

出棧

二.棧與線性表的關系

三.棧的實現方式

四.鏈表實現棧

1.結點的API設計

2.棧的API設計

2.1棧的初始化設計

2.2元素入棧

2.3元素出棧

五.括號匹配問題

完整代碼展示

答案

---

一定義.

棧是一種基于先進后出（FILO）的數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進后出的原則存儲數據，先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最后一個數據被第一個讀出來）。
●我們稱數據進入到棧的動作為壓棧，數據從棧中出去的動作為彈棧。

●棧（stack）又被稱為堆棧，它是一種只允許在一端（一般是表尾）進行插入和刪除操作的線
性表。
●作為一種特殊的數據結構，由于棧被限定只能在尾進行插入和刪除操作。

入棧

出棧

二.棧與線性表的關系

棧是一種特殊的線性表，它同樣由一系列數據元素組成，但是棧的操作受到限制，只允許在一端（稱為棧頂）進行插入（壓棧，push）和刪除（彈棧，pop）操作。棧遵循后進先出（LIFO，Last In First Out）的原則。

三.棧的實現方式

? ? ? ? 棧通過以下兩種方式實現：

? ? ? ? 1.順序表實現

? ? ? ? 2.鏈表實現

? ? ? ? 我們今天講第二種方式。

四.鏈表實現棧

鏈表使用節點來存儲數據元素。每個節點包含數據部分和指向下一個節點的引用。在鏈表實
現棧時，我們通常將鏈表的頭節點作為棧頂。

1.結點的API設計

2.棧的API設計

2.1棧的初始化設計

class StackResult<T>
{//結點類class  Node{T data;//存儲數據Node next;//下一個結點public Node(T data, Node next) {this.data = data;this.next = next;}}//記錄首結點private Node head;//元素個數private int N;// 構造方法public StackResult(){//初始化頭結點this.head =new Node(null,null);this.N =0;//s初始元素個數為0}
}

2.2元素入棧

思路分析：根據前面的入棧流程圖，我們可以簡單分為4步

1.找到頭結點指向棧頂的值

2.創建一個新結點，為新棧頂

3.讓頭結點指向新棧頂的值

4.讓新結點指向原來的棧頂

 //把元素入棧public void push(T data){//找到頭結點指向棧頂的值Node oldFirst=head.next;//創建新結點Node newFirst=new Node(data,null);//讓頭結點指向新結點head.next=newFirst;//讓新結點指向原來的棧頂newFirst.next=oldFirst;N++;}

2.3元素出棧

思路分析：

根據前面的出棧流程圖，我們可以分為

1.找到原來頭結點指向棧頂的值

2.讓頭結點指向原來棧頂指向下一個結點的值

 //元素出棧public T pop(){//找到頭結點指向棧頂的的值Node oldFirst=head.next;//檢查是否為空if(oldFirst==null){return null;}//讓頭結點指向原來棧頂指向下一個結點的值head.next=oldFirst.next;N--;return oldFirst.data;}

五.括號匹配問題

問題描述：判斷字符串”(a+b）*（c-d)”字符串中的括號是否匹配

 //括號匹配public static boolean  isMatch(String str ){//創建一個存儲字符串的棧StackResult<Character> stack=new StackResult<>();//遍歷字符串for(int i=0;i<str.length();i++){char ch=str.charAt(i);if(ch=='('){stack.push(ch);//當遇到字符（時，將其入棧}else if (ch==')')//遇到字符串）時，先檢查棧是否為空{if(stack.isEmpty()){return false;//為空返回false}stack.pop();//不為空將其出棧}}return stack.isEmpty();//檢查棧是否為空，為空則說明全部匹配成功，反之失敗}

完整代碼展示

class StackResult<T>
{//結點類class  Node{T data;//存儲數據Node next;//下一個結點public Node(T data, Node next) {this.data = data;this.next = next;}}//記錄首結點private Node head;//元素個數private int N;// 構造方法public StackResult(){//初始化頭結點this.head =new Node(null,null);this.N =0;//s初始元素個數為0}//其他方法---------------------------------------------------//判斷當前棧中的元素個數是否為0public boolean isEmpty(){return N==0;}//獲取棧中的元素個數public int size(){return N;}//把元素入棧public void push(T data){//找到頭結點指向棧頂的值Node oldFirst=head.next;//創建新結點Node newFirst=new Node(data,null);//讓頭結點指向新結點head.next=newFirst;//讓新結點指向原來的棧頂newFirst.next=oldFirst;N++;}//元素出棧public T pop(){//找到頭結點指向棧頂的的值Node oldFirst=head.next;//檢查是否為空if(oldFirst==null){return null;}//讓頭結點指向原來棧頂指向下一個結點的值head.next=oldFirst.next;N--;return oldFirst.data;}//括號匹配public static boolean  isMatch(String str ){//創建一個存儲字符串的棧StackResult<Character> stack=new StackResult<>();//遍歷字符串for(int i=0;i<str.length();i++){char ch=str.charAt(i);if(ch=='('){stack.push(ch);//當遇到字符（時，將其入棧}else if (ch==')')//遇到字符串）時，先檢查棧是否為空{if(stack.isEmpty()){return false;//為空返回false}stack.pop();//不為空將其出棧}}return stack.isEmpty();//檢查棧是否為空，為空則說明全部匹配成功，反之失敗}
}
public class StudentMs3
{public static void main(String[] args){String str ="(a+b)*(c-d)";boolean result = StackResult.isMatch(str);System.out.println(result);}
}

答案