重學數據結構（二、棧）
@
1、棧的定義和特點
棧(Stack)又稱堆棧， 是限制在表的一端進行插入和刪除運算的線性表。
如果要拿一個東西對比，羽毛球筒比較合適。
棧遵循後進先出（ Last-in-first-out，LIFO）的原則。
比如上面的羽毛球筒，只能將最頂端的羽毛球移出，也只能將新的羽毛球放到最頂端——這兩種操作分別稱作入棧（ Push）和出棧（ Pop）。入棧和出棧的示意圖如下：
最頂端的羽毛球叫棧頂棧頂 (top),最底端的羽毛球稱為棧底 (bottom)。
2、棧的基本操作
棧的基本操作除了入棧和出棧外， 還有棧的初始化、 棧空的判定， 以及取棧頂元素等。
根據這些操作，我們定義一個介面：
/**
* @Author 三分惡
* @Date 2020/8/26
* @Description 棧介面
*/
public interface Stack {
public int getSize(); //返回棧中元素數目
public boolean isEmpty(); //判空
public Object top(); //取棧頂元素但不刪除
public void push(Object element); //入棧
public Object pop(); //出棧
}
線性表有順序和鏈式兩種實現，棧同樣有兩種實現。
3、順序棧
這裡我們通過一個可擴容的數組來實現。
/**
* @Author 三分惡
* @Date 2020/8/26
* @Description 順序棧--數組實現
*/
public class ArrayStack implements Stack{
private static int defaultSize=15; //默認容量
private int size; //實際容量：實際存儲元素個數
private Object[] data; //存放元素的數組
/**
* 無參構造方法：按默認容量構造元素數組
*/
public ArrayStack() {
data=new Object[defaultSize];
size=0;
}
/**
* 有參構造方法：指定元素數組容量
* @param size
*/
public ArrayStack(int size){
data=new Object[size];
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size==0;
}
/**
* 取棧頂元素:不刪除棧頂元素
* @return
*/
public Object top() {
if (isEmpty())
throw new RuntimeException("棧空");
size--;
return data[size-1];
}
/**
* 入棧
* @param element
*/
public void push(Object element) {
//數組已滿，擴容
if (size==data.length){
//擴容兩倍的新數組
Object [] newData=new Object[size<<1];
//拷貝數組
System.arraycopy(data,0,newData,0,size);
data=newData;
}
//棧頂上插入新元素
data[size]=element;
size++;
}
/**
* 出棧
* @return
*/
public Object pop() {
if (isEmpty())
throw new RuntimeException("棧空");
Object top=data[size-1];
data[size-1]=null;
size--;
return top;
}
}
時間複雜度分析：
- getSize()：O(1)
- isEmpty()：O(1)
- top()：O(1)
- push()：平均O(1)，最壞（擴容）O(n)
- pop(): O(1)
3、鏈棧
鏈棧指的是鏈式存儲結構實現的棧。在前面的學習中，我們已經完成了單向鏈表的實現，程式碼如下，具體說明可查看上一篇內容：
現在我們通過單向鏈表來實現鏈棧：
/**
* @Author 三分惡
* @Date 2020/8/26
* @Description
*/
public class ListStack implements Stack{
//單向鏈表
private SinglyLinkedList list;
/**
* 構造函數：初始化單向鏈表
*/
public ListStack(){
list=new SinglyLinkedList();
}
/**
* 獲取棧的容量
* @return
*/
public int getSize() {
return list.getSize();
}
public boolean isEmpty() {
return list.getSize()==0;
}
/**
* 取棧頂元素
* @return
*/
public Object top() {
//取列表的尾節點
return list.get(list.getSize()-1);
}
/**
* 入棧
* @param element
*/
public void push(Object element) {
//隊列尾插入
list.addTail(element);
}
/**
* 出棧
* @return
*/
public Object pop() {
int topIndex=list.getSize()-1;
//列表為節點
Object top=list.get(topIndex);
//刪除尾結點
list.remove(topIndex);
return top;
}
}
時間複雜度分析：
- getSize()：O(1)
- isEmpty()：O(1)
- top()：O(1)
- push()：O(1)
- pop(): O(1)
4、java中的棧
在Java中有一個java.util.Stack類，它實現了棧的結構。
它是Vector的子類，也自定義了一些作為棧的方法。
java.util.Stack類是Vector的子類，實際上並不建議使用它。
在Java中還有另外一個集合，可以作為棧使用，它就是LinkedList。LinkedList中實現了push、pop方法。具體可以查看LinkedList源碼閱讀筆記。
源碼地址：//gitee.com/LaughterYoung/data-structure-learn.git
上一篇：重學數據結構（一、線性表）
本文為學習筆記類部落格，主要資料來源如下！
參考：
【1】：鄧俊輝 編著. 《數據結構與演算法》
【2】：王世民 等編著 . 《數據結構與演算法分析》
【3】： Michael T. Goodrich 等編著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》
【4】：嚴蔚敏、吳偉民 編著 . 《數據結構》
【5】：程傑 編著 . 《大話數據結構》
【6】：Java Stack 類
