簡單談談棧
一、前言
計算機程式離不開演算法和資料結構,資料結構這門學科就是為了讓計算機能夠以更加高效,簡單,便捷的方式來儲存和使用資料而產生的。本文簡單介紹棧(Stack)和佇列(Queue)的實現
二、圖解
三、線性表
1、 順序儲存結構:用一段地址連續的儲存單元依次儲存線性表的資料元素
2、 鏈式儲存結構:用一組任意的儲存單元儲存線性表的資料元素,這組儲存單元可以連續,也可以不連續,空間與記憶體沒有線性關係
四、棧
棧
1、只允許在一端進行插入和刪除操作的線性表
2、 實現的功能
- push:在最頂層加入資料。
- pop:返回並移除最頂層的資料。
- peek:返回最頂層資料的值,但不移除它。
- empty:返回一個布林值,表示當前stack是否為空棧。
2-1、初始化
private int[] arr; //常量用大寫 private final static int SIZE = 1; //棧的當前指標 private int index; //構造器沒有引數的 public StackDemo() { arr = new int[SIZE]; index = -1; }
2-2、push
//入棧 private void push(int target){ if (index == SIZE){ thrownewStackOverflowError(); }else { //剛開始為-1,要前加 arr[++index] = target; } }
2-3、peek
//返回棧頂元素 private int peek(){ if (index == -1){ throw new StackOverflowError(); }else { return arr[index]; } }
2-4、empty
//判空 private boolean empty(){ if (index == -1){ return true; } return false; }
3、程式碼實現
import java.util.Arrays; /** * * @author buer * @date 2019/1/20 */ public class StackDemo { private int[] arr; //常量用大寫 private final static int SIZE = 1; //棧的當前指標 private int index; //構造器沒有引數的 public StackDemo() { arr = new int[SIZE]; index = -1; } //入棧 private void push(int target){ if (index == SIZE){ thrownewStackOverflowError(); }else { //剛開始為-1,要前加 arr[++index] = target; } } //出棧 private int pop(){ if (index == -1){ throw new StackOverflowError(); }else { return arr[index--]; } } //返回棧頂元素 private int peek(){ if (index == -1){ throw new StackOverflowError(); }else { return arr[index]; } } //判空 private boolean empty(){ if (index == -1){ return true; } return false; } public static void main(String[] args) { StackDemo stackDemo = new StackDemo(); stackDemo.push(1); System.out.println(stackDemo.toString()); stackDemo.pop(); System.out.println(stackDemo.toString()); } @Override public String toString() { return "StackDemo{" + "arr=" + Arrays.toString(arr) + ", index=" + index + '}'; } }
應用
1、括號匹配
2、中綴表示式(人類的思考)和字尾表示式(計算機的計算)
3、遞迴
4、瀏覽器的前進後退功能