1.棧的特點：
棧也是一種線性結(jié)構(gòu)；
相比數(shù)組，棧所對應(yīng)的操作是數(shù)組的子集；
棧只能從一端添加元素，也只能從這一端取出元素，這一端通常稱之為"棧頂"；
向棧中添加元素的過程，稱之為"入棧"，從棧中取出元素的過程稱之為"出棧"；
棧的形象化描述如下圖：
image.png
"入棧"的順序若為1-2-3-4，那么出棧的順序只能為4-3-2-1，即，棧是一種"后進先出"（Last In First Out）的數(shù)據(jù)結(jié)構(gòu)；
從用戶的角度，只能看到棧頂元素，其它元素對用戶是不可見的；
在計算機世界里，"棧"有著不可思議的作用；
2.簡單舉例"棧"的應(yīng)用
應(yīng)用程序中的"撤銷"(Undo)操作的底層原理就是通過"棧"來實現(xiàn)的；
程序調(diào)用的系統(tǒng)棧，通過下圖簡單示例：
image.png
image.png
image.png
- 棧的實現(xiàn)
任務(wù)目標如下：
Stack<E>
·void push(E) //入棧
·E pop() // 出棧
·E peek() // 查看棧頂元素
·int getSize() // 查看棧中共有多少元素
·boolean isEmpty() // 查看棧是否為空
需要提一下，從用戶的角度來看，只要實現(xiàn)上述操作就好，具體底層實現(xiàn)，用戶并不關(guān)心，實際上，底層確實有多種實現(xiàn)方式。
我們準備在之前實現(xiàn)的動態(tài)數(shù)組基礎(chǔ)上，來實現(xiàn)"棧"這種數(shù)據(jù)結(jié)構(gòu)。
先定義一個接口Interface，如下：
public interface Stack<E> { // 支持泛型
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
}
然后實現(xiàn)一個ArrayStack類，如下：
public class ArrayStack<E> implements Stack<E> {
Array<E> array;
//構(gòu)造函數(shù)
public ArrayStack(int capacity) {
array = new Array<>(capacity);
}
//無參數(shù)構(gòu)造函數(shù)
public ArrayStack() {
array = new Array<>();
}
//實現(xiàn)getSize方法
@Override
public int getSize() {
return array.getSize();
}
//實現(xiàn)isEmpty方法
@Override
public boolean isEmpty() {
return array.isEmpty();
}
//實現(xiàn)getCapacity方法
public int getCapacity() {
return array.getCapacity();
}
//實現(xiàn)push方法
@Override
public void push(E e) {
array.addLast(e);
}
//實現(xiàn)pop方法
@Override
public E pop() {
return array.removeLast();
}
//實現(xiàn)peek方法
public E peek() {
return array.getLast();
}
//方便打印測試
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append('[');
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1) {
res.append(", ");
}
}
res.append("] top");
return res.toString();
}
}
Array類的業(yè)務(wù)邏輯如下：
public class Array<E> {
private E[] data; //設(shè)置為private，不希望用戶從外部直接獲取這些信息，防止用戶篡改數(shù)據(jù)
private int size;
//構(gòu)造函數(shù)，傳入數(shù)組的容量capacity構(gòu)造Array
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
//無參數(shù)構(gòu)造函數(shù)，默認數(shù)組容量capacity=10
public Array() {
this(10); //這里的capacity是IDE自動添加的提示信息，實際不存在
}
//獲取數(shù)組中的元素個數(shù)
public int getSize() {
return size;
}
//獲取數(shù)組的容量
public int getCapacity() {
return data.length;
}
//判斷數(shù)組是否為空
public boolean isEmpty() {
return size == 0;
}
//向數(shù)組末尾添加一個新元素e
public void addLast(E e) {
add(size, e);
}
//向數(shù)組開頭添加一個新元素e
public void addFirst(E e) {
add(0, e);
}
//在index位置插入一個新元素e
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
}
if (size == data.length) {
resize(2 * size); //擴大為原容量的2倍
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
//獲取index位置的元素
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
//獲取最后一個元素
public E getLast() {
return get(size - 1);
}
//獲取開頭的元素
public E getFirst() {
return get(0);
}
//修改index位置的元素為e
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed. Index is illegal.");
}
data[index] = e;
}
//查找數(shù)組中是否存在元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
//查看數(shù)組中元素e的索引，若找不到元素e，返回-1
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
//刪除掉index位置的元素，并且返回刪除的元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--; //data[size]會指向一個類對象，這部分空間不會被釋放loitering objects
data[size] = null;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2); //被利用的空間等于總空間的一半時，將數(shù)組容量減少一半
}
return ret;
}
//刪除掉數(shù)組開頭的元素，并返回刪除的元素
public E removeFirst() {
return remove(0);
}
//刪除掉數(shù)組末尾的元素，并返回刪除的元素
public E removeLast() {
return remove(size - 1);
}
//如果數(shù)組中有元素e，那么將其刪除，否則什么也不做
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
@Override
public String toString() { //覆蓋父類的toString方法
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size=%d, capacity=%d\n", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1) {
res.append(", ");
}
}
res.append(']');
return res.toString();
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}
- 對我們實現(xiàn)的棧進行測試：
public class Main {
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>();
//測試入棧push
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println(stack);
}
//測試出棧
stack.pop();
System.out.println(stack);
}
}
輸出結(jié)果如下：
Stack: [0] top
Stack: [0, 1] top
Stack: [0, 1, 2] top
Stack: [0, 1, 2, 3] top
Stack: [0, 1, 2, 3, 4] top
Stack: [0, 1, 2, 3] top
5.棧的時間復(fù)雜度分析
Stack<E>
·void push(E) O(1) 均攤
·E pop() O(1) 均攤
·E peek() O(1)
·int getSize() O(1)
·boolean isEmpty() O(1)
- 棧的另外一個應(yīng)用——括號匹配
業(yè)務(wù)邏輯如下：
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char topChar = stack.pop();
if (topChar == '(' && c != ')') {
return false;
}
if (topChar == '[' && c != ']') {
return false;
}
if (topChar == '{' && c != '}') {
return false;
}
}
}
return stack.isEmpty(); //這里很巧妙
}
//測試
public static void main(String[] args){
System.out.println((new Solution()).isValid("()"));
System.out.println((new Solution()).isValid("()[]}{"));
System.out.println((new Solution()).isValid("({[]})"));
System.out.println((new Solution()).isValid("({)}[]"));
}
}
