數(shù)據(jù)結(jié)構(gòu)-棧
定義
棧（英語：stack）又稱為堆棧或堆疊裹赴，棧作為一種數(shù)據(jù)結(jié)構(gòu)，它按照先進后出的原則存儲數(shù)據(jù)延都，先進入的數(shù)據(jù)被壓入棧底睛竣，最后的數(shù)據(jù)在棧頂射沟，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。
由于堆疊數(shù)據(jù)結(jié)構(gòu)只允許在一端進行操作幽污，因而按照后進先出（LIFO, Last In First Out）的原理運作距误。棧也稱為后進先出表
棧的應(yīng)用場景
undo操作（撤銷）
- 例如：將操作的每組數(shù)據(jù)存入棧中扁位，如果想要撤銷，只需要彈出棧頂元素刑然，就可以恢復(fù)上一步操作了暇务。
程序調(diào)用的系統(tǒng)棧
- 例如：A方法調(diào)用B方法得到返回值垦细，B調(diào)用C得到返回值，A操作走到了B方法腻豌，這個時候可以將A的代碼位置存儲到棧中嘱能，然后走到B方法惹骂，B操作走到了C方法，這個時候可以將B的代碼位置存儲到棧中兜叨。最后C執(zhí)行完成，根據(jù)棧的結(jié)構(gòu)開始彈出數(shù)據(jù)，一步一步再走回A方法茫死。
判斷括號是否有效跪但。下文會有代碼實現(xiàn)（詳細規(guī)則描述可以參考leetcode第20題）
- 開括號必須用同一類型的括號閉合。
- 開方括號必須按正確順序閉合峦萎。
- 例如：正確的:{[()]} [{()}] ({[]}) 等 屡久。錯誤的：[{(})] [}{()] 等。
自定義棸疲基類的代碼實現(xiàn)
- 棧在java.util有一個工具類被环，先不用，自定義實現(xiàn)一個
創(chuàng)建一個接口详幽，用來統(tǒng)一規(guī)范所有棧實現(xiàn)
package com.datastructure.stack;
public interface Stack<E> {
/**
* 向棧插入元素
* @param e
*/
public void push(E e);
/**
* 取出最上面的元素筛欢，并且返回
* @return
*/
public E pop();
/**
* 獲取棧的大小
* @return
*/
public int getSize();
/**
* 判斷棧是否為空
* @return
*/
public boolean isEmpty();
/**
* 獲取棧最上面的元素
* @return
*/
public E peek();
}
用基于數(shù)組的方式來實現(xiàn)一個棧（上文所寫的自定義數(shù)組）
package com.datastructure.stack;
import com.datastructure.array.Array;
/**
* @program: test
* @description:
* @author: Mr.Yang
* @create: 2019-05-02 15:27
**/
public class ArrayStack<E> implements Stack<E>{
Array<E> array;
public ArrayStack(int capacity){
array=new Array<E>(capacity);
}
public ArrayStack(){
array=new Array<E>();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop() {
return array.removeLast();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public E peek() {
return array.getLast();
}
/**
* 獲取容量值
* @return
*/
public int getCapacity(){
return array.getCapacity();
}
@Override
public String toString(){
StringBuffer sb = new StringBuffer();
sb.append("stack: ");
sb.append("[");
for(int i=0;i<array.getSize();i++){
sb.append(array.get(i));
if(i!=array.getSize()-1){
sb.append(", ");
}
}
sb.append("] right value is stack top");
return sb.toString();
}
}
測試代碼
package com.datastructure.stack;
/**
* @program: test
* @description:
* @author: Mr.Yang
* @create: 2019-05-02 16:11
**/
public class StackTest {
public static void main(String[] args) {
ArrayStack<Integer> integerArrayStack = new ArrayStack<>();
for(int i=0;i<5;i++){
integerArrayStack.push(i);
System.out.println(integerArrayStack);
}
Integer pop = integerArrayStack.pop();
System.out.println("----移除上級元素----value is "+pop);
System.out.println("-------------移除之后的棧打印------------------");
System.out.println(integerArrayStack);
}
}
測試結(jié)果
stack: [0] right value is stack top
stack: [0, 1] right value is stack top
stack: [0, 1, 2] right value is stack top
stack: [0, 1, 2, 3] right value is stack top
stack: [0, 1, 2, 3, 4] right value is stack top
----移除上級元素----value is 4
-------------移除之后的棧打印------------------
stack: [0, 1, 2, 3] right value is stack top
leetCode第20題唇聘，花括號正確閉合
思路
- 根據(jù)棧的數(shù)據(jù)結(jié)構(gòu)特點版姑，我們可以先將所有左括號‘[{(’放進棧中，然后判斷當前字符如果是‘)]}’這種的右括號迟郎，但是棧頂?shù)睦ㄌ枀s不匹配剥险，返回false
- 注意控制判斷
- 這里使用java自帶的棧工具類來實現(xiàn)
- leetcode給的測試例子：
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 輸入例子 | () | ()[]{} | (] | ([)] | {[]} |
代碼實現(xiàn)
package com.datastructure.stack;
import java.util.Stack;
/**
* @program: test
* @description:
* @author: Mr.Yang
* @create: 2019-05-02 16:59
**/
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.isValid("{\"name\": \"網(wǎng)站\",\"num\": 3,\"sites\": [ \"Google.com\", \"Taobao.com\", \"Waibo.wang\" ]}"));
}
public boolean isValid(String s) {
Stack<Character> characters = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '{' || c == '[' || c == '(') {
characters.push(c);
} else {
if(characters.isEmpty()){
return false;
}
Character peek = characters.pop();
switch (c) {
case '}':
if (!peek.equals('{')) {
return false;
}
continue;
case ']':
if (!peek.equals('[')) {
return false;
}
continue;
case ')':
if (!peek.equals('(')) {
return false;
}
continue;
}
}
}
return characters.isEmpty();
}
/*public boolean isValid(String s) {
Stack<Character> characters = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '{' || c == '[' || c == '(') {
characters.push(c);
} else {
if(characters.isEmpty()){
return false;
}
Character toChar = characters.pop();
if(c == ')' && toChar != '('){
return false;
}
if(c == '}' && toChar != '{'){
return false;
}
if(c == ']' && toChar != '['){
return false;
}
}
}
return characters.isEmpty();
}*/
}
如果想實現(xiàn)更多字符串關(guān)于括號的匹配，如JSON等等宪肖，可以根據(jù)棧的特點來實現(xiàn)
代碼例子GIT地址：https://git.dev.tencent.com/yangxiaojie123/designPattern.git
項目簡介：
這個項目是我做測試表制，學(xué)習(xí)的主要項目，目前里面包含了：
- 一些設(shè)計模式的demo（抽象工程模式控乾，適配器模式么介，外觀模式，命令模式阱持，裝飾者模式等等）
- 即將學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)demo夭拌，數(shù)組，棧衷咽，后續(xù)還會持續(xù)更新數(shù)據(jù)結(jié)構(gòu)鸽扁，可能會有隊列，鏈表镶骗，遞歸桶现，紅黑樹，線段樹等等一系列鼎姊，如果感興趣骡和，歡迎留言相赁。
