?歡迎來到資料結構專欄，一起學習，一起進步?

一、堆疊是什么？

堆疊是一種特殊的線性表，它只允許在固定的一端進行插入和洗掉，并把這一端叫堆疊頂，另一端叫做堆疊底，堆疊中元素的進、出遵循先進后出的原則，

不了解線性表是同學可以看看我之前寫的線性表的文章，鏈接放到下方：
線性表及順序表講解+手撕代碼

說到這里可能大家還有一些抽象，來給大家舉一些現實生活中的例子，

1、子彈上膛就是一種堆疊的應用：先上上去的子彈放到彈夾的底部，最后上的子彈最先打出去，

2、米缸也是一種堆疊的應用，最先倒進米缸的米，最后才吃得到，而最后放進去的米，最先吃，

堆疊的兩種操作：

1、壓堆疊：將元素放進堆疊中就叫做壓堆疊/入堆疊/進堆疊，入資料在堆疊頂，

2、出堆疊：堆疊中元素的洗掉操作叫出堆疊，出資料在堆疊頂，

二、集合框架中的堆疊

Java當中的堆疊Stack繼承自Vector，它的底層是一個陣列，Vector又繼承了Deque，然后一路繼承到collection，

三、堆疊方法的處使用

3.1、初次使用Stack堆疊的方法

1、打開idea，匯入Stack的包，并實體化出一個stack物件

//導包
import java.util.Stack;

public class MyOwnStack {
    public static void main(String[] args) {
    //new一個Stack物件，里面存放整形元素，
        Stack<Integer> stack=new Stack<>();
        
    }
}

2、查看Java當中堆疊的原始碼

在idea中，按住 Ctrl，旋轉Stack，再點擊滑鼠左鍵，就進入到堆疊的原始碼了，可以在串列的左側看到，堆疊包含5個方法，和一個構造方法，我們下面來嘗試使用堆疊的方法，

3.2、 堆疊的push方法

也就是入堆疊操作，每次將一個元素插入到堆疊中，

 public static void main(String[] args) {
        Stack<Integer> stack=new Stack<>();
        //堆疊的插入
          stack.push(1);
          stack.push(2);
          stack.push(3);
        System.out.println(stack);
    }

運行結果：

3.3、 堆疊的pop方法

彈出當前堆疊的堆疊頂元素，每次一個

 //彈出堆疊頂元素，一次一個
        stack.pop();
        System.out.print("pop后堆疊當中的元素： ");
        System.out.println(stack);

運行效果：

3.4、 堆疊的peek方法

得到堆疊頂元素，但是不洗掉改元素，僅僅是得到！

  //得到堆疊頂元素
        int peekNum=stack.peek();
        System.out.println("得到堆疊頂元素:  "+peekNum);

運行結果：

3.5 堆疊的empty方法

判斷當前堆疊是否為空，回傳ture，或false，

  //判斷當前堆疊是否為空
        System.out.println("當前堆疊為空嗎？  "+stack.empty());

運行結果：

3.6 查找元素

輸入要查找的元素值，回傳在堆疊中的位置下標，

/**查找元素
        當前堆疊的元素是 1,2,3，
         1是先入的，所以堆疊的實際順序是，  3  ，2  ，1
         所以呼叫search方法找1的話應該是在3位置，
         **/
        System.out.println("1在堆疊中的位置"+stack.search(1));

運行結果：

3.7 Stack的isEmpty方法

和empty一樣，判斷是否為空，回傳ture或者false

四、實作一個堆疊

上面學習了，Java當中的堆疊的那些方法，接下來我們自己通過陣列來實作一個自己的堆疊，在實作上面那些方法，

既然是陣列實作的，就包含了下標的特性，我們在堆疊中也使用這個特性，創建一個參考top，top代表當前陣列的下標，

4.1、初始化堆疊

我們需要一個陣列，top下標，在這里目的還是為了實作堆疊的方法，所以堆疊的大小暫且初始化為10，滿了再擴容就行，因為是陣列，所以可以直接使用Arrays.copyOf擴容，

初始化代碼：

public class MyOwnStack {
      private  int []elem;//用于實作堆疊的陣列
      private int top;//下標->堆疊頂指標
      //不帶引數的構造方法
    public  MyOwnStack(){
        this.elem=new int[10];
    }

    }

假設當前有一組資料，12，28，45，77，9待入堆疊，陣列elem是模擬堆疊的，top代表可以存放元素的下標，當沒有任何元素入堆疊是top的位置就是0，

當我們將待入堆疊元素12入堆疊后，相應的top就指向了1號下標，當28入堆疊后，top就指向2號下標，依次類推，

4.2、push方法

push方法需要考慮一個問題就是當前堆疊是否已經滿了，如果沒滿那直接插入資料就行，那如果滿了呢？給陣列進行擴容就行，

push方法三步走：
1、判斷當前堆疊是不是滿了？
2、沒滿->直接插入資料
3、滿了->陣列擴容在插入資料

判滿方法 isFull代碼如下：

思路是判斷陣列長度和top的大小，

  public  boolean isFull(){
    //如果top直到堆疊頂當然堆疊就滿了
       return  this.elem.length==this.top;
    }

push方法整個代碼

   /**
     *   入堆疊操作
     * @param item 需要入堆疊的元素
     * @return
     */
    public  void push(int item){
     //1、判斷當前堆疊是否是滿的,沒有滿的話進行第二步
    if(isFull()){
        //滿了就擴容
        this.elem= Arrays.copyOf(this.elem, 2*this.elem.length);
    }
    //2、elem[top]=item  top++;
     elem[top]=item;
     top++;
    }

4.3、empty方法

由于top記錄了當前可以存放資料位置的下標，所以可以判斷top是不是等于0即可，

   /**
     * 判空
     * @return
     */
    public  boolean empty(){
   return  this.top==0;
    }

4.4、pop方法

和push方法類似，需要判斷當前堆疊的元素情況，只不過不同的是，push方法是判斷是不是滿了，而pop方法是判斷是不是當前堆疊一個元素都沒有，如果沒有元素，當然就不能彈出堆疊頂元素了，

pop方法三步走
1、判斷堆疊是不是空的
2、空的->拋出一個例外，表示堆疊是空的，并列印
3、不為空-> 創建一個ret接受堆疊頂元素，并將top減一，回傳ret，

舉一個例子：
需要把2號下標的45彈出去，讓ret接收45，并讓top向下移動一個位置，因為top是記錄當前可以存放資料元素的下標，堆疊中的元素少了一個，top當然就要減一啦，

pop前：

pop后：

上代碼：

   /**
     * 出堆疊，洗掉堆疊頂元素
     * @return
     */
    public  int pop(){
    if(empty()){
        throw  new UnsupportedOperationException("堆疊為空");
    }
    int ret=this.elem[this.top-1];
    this.top--;//真正的改變了top的值
    return  ret;
    }

4.5、peek方法

和上面的pop方法不同的是pop是不僅要獲取堆疊頂元素，還要洗掉他，而peek就需要獲取就行了，所以他們直接代碼差別就在對top的改動上，

上代碼：

  /**
     * 得到堆疊頂元素，并且不洗掉
     * @return
     */
    public  int peek(){
     if(empty()){
         throw  new UnsupportedOperationException("堆疊為空");
     }
     return  this.elem[this.top-1];
    }

五、牛客OJ習題

光說不練假把式，我們來一道牛客網的中等難度的題來挑戰一下，做不出來沒關系，關鍵是你敢去做，

鏈接：
堆疊的壓入、彈出序列