码不停题第一天--栈与队列

1、​​剑指 Offer 09. 用两个栈实现队列​​

题目

分析

栈的主要特点是：​​先进后出​​队列的主要特点是：​​先进先出​​两个栈，一个栈实现插入操作，一个栈实现删除操作先往第一个栈里面进行插入元素，第一个插入的元素在栈的底部，最后插入的在栈的顶部，当第一个栈要删除的时候，把第一个栈要删除的元素依次插入第二个栈中（第二个栈为空），第二个栈中的元素就是待删除的元素顺序，依次弹出第二个栈中的元素即可！

实现

class CQueue { //定义两个栈 Deque stack1; Deque stack2; public CQueue() { stack1 = new LinkedList(); stack2 = new LinkedList(); } //第一个栈插入元素 public void appendTail(int value) { stack1.push(value); } //第二个栈删除元素 public int deleteHead() { if (stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } //当第二个栈不为空时，依次弹出第二个栈中元素 if(stack2.isEmpty()){ return -1; }else{ int item = stack2.pop(); return item; } }}

2、​​包含min函数的栈​​

题目

分析

**思路一：**新建一个栈B来存储栈中的最小元素栈A每次push元素后，判断栈B中元素是否为空或者B栈顶元素是否大于新元素，如是，则Bpush该元素pop()出栈，则需要保持A、B的一致性，A出栈则是A.pop()，若是A出栈的元素.equals(B出栈的元素)，则B也需要出栈这样做的原因：若是只有A出栈，B不出栈的话，则无法保证A与B元素的同步A栈顶的元素则是A.peek()最小的元素则是B.peek()

实现

//思路一：class MinStack { // stack1存储元素，stack2存储stack1中最小的元素 Stack stack1,stack2; /** initialize your data structure here. */ public MinStack() { stack1 = new Stack<>(); stack2 = new Stack<>(); } public void push(int x) { stack1.add(x); if(stack2.isEmpty() || stack2.peek() >= x){ stack2.push(x); } } public void pop() { if (stack1.peek().equals(stack2.peek())){ stack2.pop(); } stack1.pop(); } public int top() { return stack1.peek(); } public int min() { return stack2.peek(); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。