数据结构与算法基础入门——手写栈（三）

栈&＃xff08;stack&＃xff09;&＃xff0c;它是一种运算受限的线性表,后进先出(LIFO)

1. LIFO(last in first out)表示就是后进入的元素, 第一个弹出栈空间. 类似于自动餐托盘, 最后放上的托盘,
   往往先把拿出去使用.
2. 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶&＃xff0c;相对地&＃xff0c;把另一端称为栈底。
3. 向一个栈插入新元素又称作进栈、入栈或压栈&＃xff0c;它是把新元素放到栈顶元素的上面&＃xff0c;使之成为新的栈顶元素&＃xff1b;
4. 从一个栈删除元素又称作出栈或退栈&＃xff0c;它是把栈顶元素删除掉&＃xff0c;使其相邻的元素成为新的栈顶元素。
5. 时间复杂度&＃xff1a;出/入栈O(1),扩容O(n)

栈的分类&＃xff1a;

可以基于数组、单向链表实现。两者区别跟数组和链表一样。

public interface MyStack {MyStack push(Item item);Item pop();int size();boolean isEmpty();}


public class ArrayStack implements MyStack{private Item [] a;public int n &＃61; 0;public ArrayStack(int cap){a &＃61; (Item[]) new Object[cap];}/*** 2被扩容*/private void judgeSize(){if(n >&＃61; a.length ){resize(a.length * 2);}}/*** 扩容* &＃64;param size*/private void resize(int size){Item [] temp &＃61; (Item[]) new Object[size];for (int i &＃61; 0; i 0 && n <&＃61; a.length / 2){resize( a.length / 2);}}&＃64;Overridepublic MyStack push(Item item) {judgeSize();a[n&＃43;&＃43;] &＃61; item;return null;}&＃64;Overridepublic Item pop() {if(isEmpty()){return null;}Item item &＃61;a[--n];a[n] &＃61; null;shrink();return item;}&＃64;Overridepublic int size() {return n;}&＃64;Overridepublic boolean isEmpty() {return n&＃61;&＃61; 0;}public static void main(String[] args) {ArrayStack arrayStack &＃61; new ArrayStack(4);arrayStack.push("1");arrayStack.push("2");arrayStack.push("3");arrayStack.push("4");arrayStack.push("5");System.out.println(arrayStack.size());arrayStack.pop();arrayStack.pop();arrayStack.pop();System.out.println(arrayStack.size());}
}


拓展应用&＃xff1a;

1、基于栈&＃xff0c;实现符号匹配&＃xff1a;时间复杂度O(n)

public class KuoHaoStack {public static boolean isOk(String s){ArrayStack brackes &＃61; new ArrayStack<>(50);char[] c &＃61; s.toCharArray();Character top;for (char c1 : c) {switch (c1) {case &＃39;{&＃39;:case &＃39;(&＃39;:case &＃39;[&＃39;:brackes.push(c1);break;case &＃39;}&＃39;:top &＃61; brackes.pop();if(top!&＃61; null && top &＃61;&＃61; &＃39;{&＃39;){break;} else {return false;}case &＃39;)&＃39;:top &＃61; brackes.pop();if(top!&＃61; null && top &＃61;&＃61; &＃39;(&＃39;){break;} else {return false;}case &＃39;]&＃39;:top &＃61; brackes.pop();if(top!&＃61; null && top &＃61;&＃61; &＃39;[&＃39;){break;} else {return false;}default:break;}}return brackes.isEmpty();}public static void main(String[] args) {Scanner scanner &＃61; new Scanner(System.in);while (scanner.hasNext()){System.out.println("匹配结果&＃xff1a;"&＃43;isOk(scanner.next()));}}
}


2、基于栈&＃xff0c;实现简单的四则运算&＃xff1a;
1、声明 两个栈&＃xff0c;一个存数字&＃xff0c;一个存运算符
2、遇到数字&＃xff0c;直接入栈到数字栈里面
3、遇到符号就把符号栈的栈顶拿出来做比较&＃xff0c;如果它比栈顶符号的优先级高就直接入栈。如果比符号栈顶的优先级低或者相等&＃xff0c;就从符号栈顶里面取栈顶&＃xff08;数字栈中取栈顶的两个数&＃xff09;进行计算。计算完把新的计算术插入栈顶。举例&＃xff1a;1&＃43;3*4-5&＃61;8

3、java 函数调用&＃xff1a;a调a中的b方法&＃xff0c;b又调b中的c 方法。最后一次返回为c->b->a。
4、浏览器的前进和后退&＃xff1a;两个栈A,B 点击前进入A栈&＃xff0c;点后退出A栈入B栈。点前进出B栈入A栈。