wordpress网站缓存安装,织梦cms是什么,注册公司名字查询系统,淘客二级域名网站免费建设1. 栈(Stack) 1.1 概念 栈 #xff1a;一种特殊的线性表#xff0c;其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO #xff08; Last In First Out #xff09;的原…1. 栈(Stack) 1.1 概念 栈 一种特殊的线性表其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFO Last In First Out 的原则。 压栈栈的插入操作叫做进栈 / 压栈 / 入栈 入数据在栈顶 。 出栈栈的删除操作叫做出栈。 出数据在栈顶 。 如图所示 进栈进栈顺序是ABCD,A先压入栈底B压在A上,如此依次压栈最后的D就是栈顶数据 出栈只能从一端出所以栈顶数据先出出栈顺序就为DCBA,D最先出A最后出 现实生活也有很多像栈一样的结构如枪里的子弹最先打出去的是最后装的子弹羽毛球桶最先拿出来的羽毛球是最后放进去的都符合栈的后进先出LIFOLast In First Out的原则。 1.2栈的常用方法 2. 队列(Queue) 2.1 概念 队列 只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为 队尾 Tail/Rear 出队列进行删除操作的一端称为 队头 Head/Front 2.2 队列的实现
如图我们可以知道队列是一个接口接口不能实例化但可以通过实现了该接口的类来实例化所以 Queue可以通过ArrayListLinkedListPriorityQueue等来实例化该接口 public static void main ( String [] args ) { Queue Integer q new LinkedList (); Queue Integer q1 new ArrayList (); Queue Integer q2 new PriorityQueue (); } 3 循环队列 如何区分空与满 1. 通过添加 size 属性记录 2. 保留一个位置 3. 使用标记 通过1方法来模拟实现k长度的循环队列 class MyCircularQueue {int[] elem;int front;int rear;int size;public MyCircularQueue(int k) {elemnew int[k];frontrear0;}public boolean enQueue(int value) {if(isFull()){return false;}else{elem[rear]value;rear(rear1)% elem.length;size;return true;}}public boolean deQueue() {if(isEmpty()){return false;}else{front(front1)%elem.length;size--;return true;}}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int rear1(rear0)?elem.length-1:rear-1;//rear0的时候比较特殊return elem[rear1];}public boolean isEmpty() {return size0;}public boolean isFull() {return sizeelem.length;}
} 通过2方法来模拟实现k长度的循环队列 class MyCircularQueue {int[] elem;int front;int rear;public MyCircularQueue(int k) {elemnew int[k1];//浪费一个空间来判断循环队列的队满frontrear0;}public boolean enQueue(int value) {if(isFull()){return false;}else{elem[rear]value;rear(rear1)% elem.length;return true;}}public boolean deQueue() {if(isEmpty()){return false;}else{front(front1)%elem.length;return true;}}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int rear1(rear0)?elem.length-1:rear-1;//rear0的时候比较特殊return elem[rear1];}public boolean isEmpty() {return frontrear;}public boolean isFull() {return (rear1)% elem.lengthfront;}
} 4.栈和队列的相互转化 4.1用队列实现栈 栈先进后出 队列先进先出 进栈的实现两队列都空就放数据到队列1里否则就哪个队列为空就放哪里 出栈的实现将有不为空的队列里的size-1个元素方到另一个队列里然后就将只剩下一个元素的队列出队列就实现的出栈 class MyStack { QueueInteger queue1; QueueInteger queue2; public MyStack() { queue1new LinkedList(); queue2new LinkedList(); } public void push(int x) { if(!queue1.isEmpty()){ queue1.add(x); }else if(!queue2.isEmpty()){ queue2.add(x ); }else{ queue1.add(x); } } public int pop() { if(empty()){ return -1; } if (queue1.isEmpty()){ int size queue2.size(); for (int i 0; i size-1; i) { int valqueue2.poll(); queue1.add(val); } return queue2.poll(); } else { int size queue1.size(); for (int i 0; i size-1; i) { int val queue1.poll(); queue2.add(val); } return queue1.poll(); } } public int top() { if(empty()){ return -1; } if (queue1.isEmpty()){ int size queue2.size(); for (int i 0; i size-1; i) { int valqueue2.poll(); queue1.add(val); } int val2 queue2.peek(); queue1.add(queue2.poll()); return val2; } else { int size queue1.size(); for (int i 0; i size-1; i) { int val queue1.poll(); queue2.add(val); } int val2 queue1.peek(); queue2.add(queue1.poll()); return val2; } } public boolean empty() { return (queue2.isEmpty()queue1.isEmpty()); } } 注意 问题观察上图发现只是实例化queue接口的类不一样其余代码一样那为什么结果会不一样呢
解答
优先级队列 是会自动按照升序排序的 也就是每次push进来一个元素 都会自动排成升序 所以stack中从栈底到栈顶分别是 1 2 2 3 4因此结果是4 4 3 而双向链表是没有排序这个性质 从栈底到栈顶分别是 1 2 3 4 2 因此结果是 2 2 4 4.1用栈实现栈队列
栈先进后出
队列先进先出
进队的模拟实现
stack1专门用来放元素都为空的时候就将元素加入stack1中stack1不为空就直接push为空就将stack2中的元素全部放入stack1中
出队的模拟实现
stack2专门用来出元素进行出对操作时将元素放入stack2中出元素即可 class MyQueue { StackInteger stack1; StackInteger stack2; public MyQueue() { stack1new Stack(); stack2new Stack(); } public void push(int x) { if(!stack1.isEmpty()) { stack1.push(x); }else if(!stack2.isEmpty()){ int sizestack2.size(); for (int i 0; i size; i) { int valstack2.pop(); stack1.push(val); } stack1.push(x); }else{ stack1.push(x); } } public int pop() { if(empty()){ return -1; } if(stack2.isEmpty()){ int sizestack1.size(); for (int i 0; i size; i) { stack2.push(stack1.pop()); } return stack2.pop(); }else{ return stack2.pop(); } } public int peek() { if(empty()){ return -1; } if(stack2.isEmpty()){ int sizestack1.size(); for (int i 0; i size; i) { stack2.push(stack1.pop()); } return stack2.peek(); }else{ return stack2.peek(); } } public boolean empty() { return stack1.isEmpty()stack2.isEmpty(); } }
