安徽制作网站的公司哪家好,做网站图片处理问题,网站平台多少钱,国外网站建站1-栈的结构和特点
先进后出#xff0c;后进先出 是栈的特点#xff1b; 从图中#xff0c;我们看到A入栈先放入底部#xff0c;然后依次B和C#xff1b;出栈的顺序依次是C-B-A#xff1b;这种结构只能在一端操作。所以当某个数据集合只涉及在一端插入和删除数据#xf…
1-栈的结构和特点
先进后出后进先出 是栈的特点 从图中我们看到A入栈先放入底部然后依次B和C出栈的顺序依次是C-B-A这种结构只能在一端操作。所以当某个数据集合只涉及在一端插入和删除数据并且满足后进先出last-in-first-out(LIFO) 、先进后出的特性我们就应该首选“栈”这种数据结构。 2-栈的实现
我们可以使用数组和链表来实现栈下面我们基于数组来现实一个基础功能的栈。
Getter
Setter
public class MyArrayStack {private Object[] elementData;//存储元素的数组private int elementCount;//元素的个数private int capacity;//容量public MyArrayStack(int capacity) {this.elementData new Object[capacity];this.capacity capacity;this.elementCount 0;}// 入栈操作public boolean push(Objectitem) {if (elementCount capacity) return false;elementData[elementCount] item;elementCount;return true;}// 出栈操作public Object pop() {if (elementCount 0) return null;Object tmp elementData[elementCount-1];--elementCount;return tmp;}
}Slf4j
public class TestStack {public static void main(String[] args) {MyArrayStack stacknew MyArrayStack(3);log.info(push1{},stack.push(hello));log.info(push2{},stack.push(java));log.info(push3{},stack.push(world));log.info(push4{},stack.push(china));log.info(pop1{},stack.pop());log.info(pop2{},stack.pop());log.info(pop3{},stack.pop());log.info(pop4{},stack.pop());}
}控制台输出
10:19:38.417 [main] INFO c.y.d.statck.TestStack - push1true 10:19:38.423 [main] INFO c.y.d.statck.TestStack - push2true 10:19:38.423 [main] INFO c.y.d.statck.TestStack - push3true 10:19:38.424 [main] INFO c.y.d.statck.TestStack - push4false 10:19:38.424 [main] INFO c.y.d.statck.TestStack - pop1world 10:19:38.424 [main] INFO c.y.d.statck.TestStack - pop2java 10:19:38.424 [main] INFO c.y.d.statck.TestStack - pop3hello 10:19:38.424 [main] INFO c.y.d.statck.TestStack - pop4null
当然上面代码是简易的栈实现还有优化的空间比如支持泛型支持扩容等功能可以自行实现。
入栈、出栈只涉及栈顶个别数据的操作所以时间复杂度都是O(1)。
如何基于数组实现一个可以支持动态扩容的栈呢当数组空间不够时我们就重新申请一块更大的内存将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组。Java中也有栈Stack实现的代码支持泛型和扩容。 3-栈的使用LeetCode
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 第20题判断有效括号就可以使用栈这种结构来解决。
