怎么修改自己的网站,品牌设计公司介绍,怎么用wordpress建微博,移动电商网站一#xff1a;面试经典 1. 如何设计一个括号匹配的功能#xff1f;比如给你一串括号让你判断是否符合我们的括号原则#xff0c; 栈 力扣 2. 如何设计一个浏览器的前进和后退功能#xff1f; 思想#xff1a;两个栈#xff0c;一个栈存放前进栈面试经典 1. 如何设计一个括号匹配的功能比如给你一串括号让你判断是否符合我们的括号原则 栈 力扣 2. 如何设计一个浏览器的前进和后退功能 思想两个栈一个栈存放前进栈一个存放后退栈刚开始连续点击三个页面都存放到前进栈里当点击后退时就出栈顶然后放入后退栈中以此重复。 3. 简单的四则运算311*28-15/5 思想两个栈来实现一个放数字 一个放符号。 解决思路我们从头开始遍历这个算术表达式 1.遇到是数字 我们就直接入栈到数字栈里面去。 2.遇到是符号 就把符号栈的栈顶拿出来做比较。如果说他比栈顶符号的优先级高就直接入栈如果比符号栈顶的优先级低或者相同就从符号栈里面取栈顶进行计算从数字栈中取栈顶的2个数计算完的结果还要再放入到数字栈中。 二 栈 1.如何理解栈 比如我们在放盘子的时候都是从下往上一个个放拿的时候是从上往下一个个的那不能从中间抽这种其实就是一个典型的栈型数据结构。后进先出即Last In First Out LIFO。 2.栈如何实现 其实它是一个限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶相对地把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈它是把新元素放到栈顶元素的上面使之成为新的栈顶元素从一个栈删除元素又称作出栈或退栈它是把栈顶元素删除掉使其相邻的元素成为新的栈顶元素。 栈其实就是一个特殊的链表或者数组。 既然栈也是一个线性表那么我们肯定会想到数组和链表而且栈还有这么多限制那为什么我们还要使用这个数据结构呢不如直接使用数组和链表来的更直接么数组和链表暴露太多的接口实现上更灵活了有些技术理解不到位的人员就可能出错。所以在某些特定场景下最好是选择栈这个数据结构。 三栈的分类
3.栈的分类 1基于数组的栈——以数组为底层数据结构时通常以数组头为栈底数组头到数组尾为栈顶的生长方向 2基于单链表的栈——以链表为底层的数据结构时以链表头为栈顶便于节点的插入与删除压栈产生的新节点将一直出现在链表的头部 最大的区别就是扩容链表天然支持动态扩容。栈溢出。 四栈的实现
public interface MyStackItem {MyStackItem push(Item item); //入栈Item pop(); //出栈int size(); // 大小boolean isEmpty();
}public class ArrayStackItem implements MyStackItem{private Item [] a (Item[]) new Object[1]; //最好就是开始的时候就设置大小private int n 0; //大小 初始的元素个数public ArrayStack(int cap) {a (Item[]) new Object[cap];}public MyStackItem push(Item item) { //入栈就完成了 //时间复杂度 O(1)judgeSize();a[n] item;return null;}private void judgeSize(){if(n a.length){ //元素个数已经超出了数组的个数resize(2 * a.length); //10*2*240个大小了我出栈了20个了只剩下20了吧。}else if(n 0 n a.length / 2){resize(a.length / 2);}}private void resize(int size){ //扩容OnItem[] temp (Item[]) new Object[size];for(int i 0 ; i n; i ){temp[i] a[i];}a temp;}public Item pop() { //出栈 O(1)if(isEmpty()){return null;}//item[n--]//item[--n]Item item a[--n]; //n不是已经--了么 --n和n-- --n是先把n减了在用n--先用了在减a[n] null; //为什么要这一步return item;}public int size() {return n;}public boolean isEmpty() {return n 0;}}注意主要是栈入栈出的核心代码以及扩容的说明栈入是n而栈出为n--同时还要把这个元素的空间释放掉n为栈存储的元素个数。
