重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 開篇
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 復(fù)雜度分析(一)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 復(fù)雜度分析(二)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 數(shù)組
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 鏈表(一)
重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 鏈表(二)
叨叨兩句
說好的盡量日更o(╥﹏╥)o~，太懶了，最后兩個(gè)練習(xí)題一直沒敲，拖了兩天才更，啪 啪~ 打臉！
什么是棧
本章介紹一種“操作受限”的數(shù)據(jù)結(jié)構(gòu)，它僅支持：
- 添加操作（入棧 - push）
- 刪除操作（出棧 - pop）
并具備“先進(jìn)后出，后進(jìn)先出”特點(diǎn)：
圖中，正在裝填的彈匣就是典型的棧結(jié)構(gòu)，先裝入的子彈被壓入了底部，后裝入的在頂部，當(dāng)使用時(shí)優(yōu)先使用頂部子彈。那么，在內(nèi)存中給予這種模式存儲(chǔ)數(shù)據(jù)的容器，稱之為：棧。
棧的實(shí)現(xiàn)
根據(jù)定義，很容抽象出一個(gè)只能新增、刪除的操作接口來：
public interface Stack<T> {
//壓棧
boolean push(T item);
//彈棧
T pop();
// 返回棧頂數(shù)據(jù)，不彈棧
T peek();
//是否為空
boolean isEmpty();
//棧中數(shù)據(jù)的數(shù)量
int size();
//清空
void clear();
}
有了操作標(biāo)準(zhǔn)，拿什么來存儲(chǔ)實(shí)際數(shù)據(jù)？
- 數(shù)組 ？
- 鏈表 ？
細(xì)想一下，無論是使用數(shù)組還是鏈表存儲(chǔ)數(shù)據(jù)，只要出棧、入棧規(guī)則滿足“先進(jìn)后出、后進(jìn)先出”，那它就是我們想要的棧型結(jié)構(gòu)，當(dāng)然不同數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的棧，底層肯定還是具備其本身的數(shù)據(jù)結(jié)構(gòu)特性的，例如數(shù)組實(shí)現(xiàn)的棧型結(jié)構(gòu)內(nèi)存是連續(xù)的，鏈表則是不連續(xù)的，我們把數(shù)組實(shí)現(xiàn)的棧，稱之：順序棧 ； 鏈表實(shí)現(xiàn)則為：鏈?zhǔn)綏?/strong>。
下面以數(shù)組為例，實(shí)現(xiàn)一個(gè)棧容器：
public class ArrayStack<T> implements Stack<T> {
private static final int DEFAULT_SIZE = 10;
// 棧中數(shù)據(jù)數(shù)量
private int count;
// 棧中數(shù)據(jù)（數(shù)組實(shí)現(xiàn)）
private Object[] items;
private Object curItem;
// 當(dāng)前棧能存儲(chǔ)的最大容量
private int maxSize;
public ArrayStack() {
this(DEFAULT_SIZE);
}
public ArrayStack(int initSize) {
this.items = new Object[initSize];
this.maxSize = initSize;
}
@Override
public boolean push(T item) {
// 入棧
if (count == maxSize) {
//擴(kuò)容
grow();
}
items[count] = item;
++count;
curItem = item;
return true;
}
private void grow() {
Object[] temp = items;
items = new Object[temp.length * 2];
for (int i = 0; i < temp.length; i++) {
items[i] = temp[i];
}
maxSize = items.length;
}
@Override
public T pop() {
// 出棧
if (count == 0) return null;
T item = (T) items[count - 1];
items[count - 1] = null;
--count;
if (count == 0) {
curItem = null;
} else {
curItem = items[count - 1];
}
return item;
}
@Override
public T peek() {
return (T) curItem;
}
@Override
public boolean isEmpty() {
return count == 0;
}
@Override
public int size() {
return count;
}
@Override
public void clear() {
if (isEmpty()) return;
for (int i = 0; i < size(); i++) {
items[i] = null;
}
count = 0;
}
public void print() {
for (int i = 0; i < count; i++) {
System.out.print(items[i] + "\t");
}
System.out.println();
}
}
測(cè)試：
ArrayStack<String> stack = new ArrayStack<>();
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");
stack.push("5");
stack.print();
String item1 = stack.pop();
System.out.println(item1);
String item2 = stack.pop();
System.out.println(item2);
stack.print();
輸出：
1 2 3 4 5
5
4
1 2 3
-
時(shí)間復(fù)雜度：
最好時(shí)間復(fù)雜度：空間夠用，直接入棧，復(fù)雜度 O(1)
最壞時(shí)間復(fù)雜度：空間不足，動(dòng)態(tài)擴(kuò)容，復(fù)雜度 O(n)
平均時(shí)間復(fù)雜度：還記得復(fù)雜度分析(二)中提到的平攤分析法嗎？隨著數(shù)據(jù)的改變，算法出現(xiàn)某種固定規(guī)律，這里明顯當(dāng)執(zhí)行完n次O(1)插入操作后，都需要進(jìn)行一次O(n)的數(shù)據(jù)位移，正好可以把這n次搬運(yùn)平攤給前面各自1次的插入操作，得到平攤時(shí)間復(fù)雜度：O(1)
-
空間復(fù)雜度：
注意，這里存儲(chǔ)數(shù)據(jù)需要一個(gè)大小為 n 的數(shù)組，并不是說空間復(fù)雜度就是 O(n)。因?yàn)?，這 n 個(gè)空間是必須的，無法省掉。我們說空間復(fù)雜度的時(shí)候，是指除了原本的數(shù)據(jù)存儲(chǔ)空間外，算法運(yùn)行還需要額外的存儲(chǔ)空間。所以棧的插入操作空間復(fù)雜度是：O(1)
棧 - 練習(xí)1：運(yùn)算表達(dá)式
要求給出一個(gè)運(yùn)算表達(dá)式字符串，計(jì)算出表達(dá)式結(jié)果。
輸入字符串： 3 + 2 * 5 - 4 / 2
輸出 ：11
思路：
- 1、利用兩個(gè)棧，一個(gè)用來保存數(shù)字，另一個(gè)用來保存運(yùn)算符，從左向右遍歷表達(dá)式；
- 2、當(dāng)遇到數(shù)字，我們就直接壓入數(shù)字棧；
- 3、當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較，若比運(yùn)算符棧頂元素優(yōu)先級(jí)高，就將當(dāng)前運(yùn)算符壓入棧；
- 4、若比運(yùn)算符棧頂元素的優(yōu)先級(jí)低或者相同，從運(yùn)算符棧中取出棧頂運(yùn)算符，從操作數(shù)棧頂取出2個(gè)操作數(shù)，然后進(jìn)行計(jì)算，把計(jì)算完的結(jié)果壓入數(shù)字棧；
- 5、重復(fù)第3步的操作，繼續(xù)比較棧頂操作符。
private static void computeExp(String exp) {
ArrayStack<String> numStack = new ArrayStack<>();
ArrayStack<String> opStack = new ArrayStack<>();
char[] chars = exp.toCharArray();
String preItem = null;
for (int i = 0; i < chars.length; i++) {
String item = String.valueOf(chars[i]);
if (isOp(item)) {
// 操作符
while (true) {
if (opStack.isEmpty()) {
// 直接入棧
opStack.push(item);
break;
}
// 比較優(yōu)先級(jí)
String preOp = opStack.pop();
if (opLv(item) > opLv(preOp)) {
// 大于
opStack.push(preOp);
opStack.push(item);
break;
} else {
// 小于等于 ， 取出2個(gè)數(shù)，和棧頂操作符進(jìn)行運(yùn)算
String num1 = numStack.pop();
String num2 = numStack.pop();
int result = compute(num2, num1, preOp);
numStack.push(String.valueOf(result));
}
}
} else {
// 數(shù)字
if (!numStack.isEmpty() && !isOp(preItem)) {
// 前一個(gè)也是數(shù)字，拼接后入數(shù)字棧
preItem = numStack.pop();
item = preItem + item;
}
// 入數(shù)字棧
numStack.push(item);
}
preItem = item;
}
// 清空棧，計(jì)算最終結(jié)果
int len = opStack.size();
for(int i = 0 ; i < len ; i++){
String num1 = numStack.pop();
String num2 = numStack.pop();
String op = opStack.pop();
int result = compute(num2 , num1 , op);
numStack.push(String.valueOf(result));
}
System.out.println( exp + " = " + numStack.pop());
}
private static int compute(String num2, String num1, String op) {
int n2 = Integer.parseInt(num2);
int n1 = Integer.parseInt(num1);
switch (op) {
case "+":
return n2 + n1;
case "-":
return n2 - n1;
case "*":
return n2 * n1;
case "/":
return n2 / n1;
default:
throw new RuntimeException("no op");
}
}
private static boolean isOp(String item) {
if (item == null) return false;
return item.matches("[+\\-*/]");
}
private static int opLv(String op) {
switch (op) {
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
default:
throw new RuntimeException("no op");
}
}
測(cè)試：
computeExp("3+10*5-8/2");
computeExp("4+8*5/4-7");
computeExp("50/2-3*7+1");
輸出：
3+10*5-8/2 = 49
4+8*5/4-7 = 7
50/2-3*7+1 = 5
時(shí)間復(fù)雜度：O(n2)
空間復(fù)雜度：O(1)
棧 - 練習(xí)2：模擬瀏覽器前進(jìn)后退功能
思路：
利用兩個(gè)棧，X棧用于存儲(chǔ)新打開的頁面，Y棧存儲(chǔ)后退頁面
當(dāng)點(diǎn)擊后退時(shí)，將X出棧一個(gè)頁面，并存入Y棧
當(dāng)點(diǎn)擊前進(jìn)時(shí)，將Y出棧一個(gè)頁面，并存入X棧
當(dāng)打開新頁面時(shí)，入X棧，清空Y棧
private static void go(ArrayStack<String> goStack, ArrayStack<String> backStack) {
// 當(dāng)點(diǎn)擊前進(jìn)時(shí)，將Y出棧一個(gè)頁面，并存入X棧
if(backStack.isEmpty()) {
System.out.println("go：" + goStack.peek());
return;
}
String page = backStack.pop();
goStack.push(page);
System.out.println("go：" + goStack.peek());
}
private static void back(ArrayStack<String> goStack, ArrayStack<String> backStack) {
// 當(dāng)點(diǎn)擊后退時(shí)，將X出棧一個(gè)頁面，并存入Y棧
String page = goStack.pop();
backStack.push(page);
System.out.println("back：" + goStack.peek());
}
private static void open(String page, ArrayStack<String> goStack, ArrayStack<String> backStack) {
// 當(dāng)打開新頁面時(shí)，入X棧，清空Y棧
goStack.push(page);
backStack.clear();
System.out.println("open：" + goStack.peek());
}
測(cè)試：
ArrayStack<String> goStack = new ArrayStack<>();
ArrayStack<String> backStack = new ArrayStack<>();
open("頁面1", goStack, backStack);
open("頁面2", goStack, backStack);
open("頁面3", goStack, backStack);
open("頁面4", goStack, backStack);
open("頁面5", goStack, backStack);
back(goStack, backStack);
back(goStack , backStack);
go(goStack, backStack);
go(goStack, backStack);
go(goStack, backStack);
輸出：
open：頁面1
open：頁面2
open：頁面3
open：頁面4
open：頁面5
back：頁面4
back：頁面3
go：頁面4
go：頁面5
go：頁面5
時(shí)間復(fù)雜度：O(1)
空間復(fù)雜度：O(1)
