网站二维码可以做长按识别吗,网络推广公司怎么报税,网站建设税收编码,网页生成视频利用栈实现队列
上一节中说明了栈的特点 后进先出#xff0c;我们用数组的方式实现了栈的基本操作api#xff0c;因此我们对栈的操作是不考虑排序的#xff0c;每个api的操作基本都是O(1)的世界#xff0c;因为不考虑顺序#xff0c;所以找最大#xff0c;最小值#x…利用栈实现队列
上一节中说明了栈的特点 后进先出我们用数组的方式实现了栈的基本操作api因此我们对栈的操作是不考虑排序的每个api的操作基本都是O(1)的世界因为不考虑顺序所以找最大最小值需要O(n)时间还有与栈相对于的一种数据结构那就是队列了队列特点是先进先出即第一个进去队列的元素会第一个出来栈和队列虽然特点上相反当他们也有相互联系我们利用栈解决如下队列的问题
问题
用两个栈实现一个队列队列的声明如下实现两个函数appenddel分别完成队尾插入节点 队列头部删除节点的功能。队列对象定义
/*** author liaojiamin* Date:Created in 11:37 2021/3/9*/
public class MyQueue {private MyStackInteger myStack1;private MyStackInteger myStack2;private boolean isAdd;public MyQueue(){myStack1 new MyStack();myStack2 new MyStack();isAdd false;}public boolean isAdd() {return isAdd;}public void setAdd(boolean add) {isAdd add;}public MyStackInteger getMyStack1() {return myStack1;}public void setMyStack1(MyStackInteger myStack1) {this.myStack1 myStack1;}public MyStackInteger getMyStack2() {return myStack2;}public void setMyStack2(MyStackInteger myStack2) {this.myStack2 myStack2;}
}分析
我们需要通过stack1与stack2实现先进先出的队列MyQueue我们用一个实际案例来分析首先add 一个元素a到stack1中在接着bc还是到stack1中此时stack1 中有{a,b,c}stack2是空的如下图此时我们需要删除一个元素。按队列先进先出原则a需要比bc先出去但是此时stack1中c是在栈顶。我们需要反转stacl1如上分析我们将stack1 中所有元素弹出并依次加入stack2那么就完成反转的功能在弹出stack2 中第一个元素。实现删除功能继续删除我们还是直接操作stack2即可这时候再来添加操作因为需要添加到队尾此时不能添加到stack2我们只能再次反转添加到stack1 中。总结每次add操作或者del操作之前判断上次操作是add还是del如果是不同操作则反转在对非空栈进行操作如果是相同操作类型则直接对非空栈进行操作无需反转 代码实现
/*** 利用两个栈实现队列* author liaojiamin* Date:Created in 11:35 2021/3/9*/
public class StackImpleQueue {private MyQueue myQueue new MyQueue();/*** 添加元素到队列* */public void append(Integer item){if(isEmpty()){myQueue.getMyStack1().push(item);return;}//上次是append无需changeboolean needChange !myQueue.isAdd();MyStackInteger notEmpty change(needChange);notEmpty.push(item);}/*** 从队列中删除位置* */public Integer del(){if(isEmpty()){return -1;}//上次是add则需要changeMyStackInteger notEmpty change(myQueue.isAdd());return notEmpty.pop();}/*** 队列是否为空*/public boolean isEmpty(){return myQueue.getMyStack1().isEmpty() myQueue.getMyStack2().isEmpty();}/*** 将非空栈中数据弹出并添加到另一个栈* */public MyStackInteger change(boolean needChange){if(isEmpty()){return myQueue.getMyStack1();}MyStackInteger emptyStack myQueue.getMyStack1().isEmpty() ? myQueue.getMyStack1() : myQueue.getMyStack2();MyStackInteger notEmptyStack myQueue.getMyStack1().isEmpty() ? myQueue.getMyStack2() : myQueue.getMyStack1();if(needChange){while (!notEmptyStack.isEmpty()){emptyStack.push(notEmptyStack.pop());}//切换操作标记位myQueue.setAdd(!myQueue.isAdd());return emptyStack;}return notEmptyStack;}public static void main(String[] args) {StackImpleQueue stackImpleQueue new StackImpleQueue();stackImpleQueue.append(1);stackImpleQueue.append(2);stackImpleQueue.append(3);System.out.println(stackImpleQueue.del());System.out.println(stackImpleQueue.del());stackImpleQueue.append(4);System.out.println(stackImpleQueue.del());System.out.println(stackImpleQueue.del());}}上一篇数据结构与算法–简单栈实现及其应用 下一篇数据结构与算法–链表实现以及应用
