公共空间设计网站,wordpress如何代码高亮,深圳做网站哪家最好,网络游戏工作室引言
自己实现简单的队列、栈的逻辑结构。
队列都包含头和尾两个指针#xff0c;简单的单向队列只能在一端#xff08;如#xff1a;head端#xff09;入列#xff0c;在另一端#xff08;如#xff1a;tail 端#xff09;出列#xff1b;双端队列可以在 head 进出简单的单向队列只能在一端如head端入列在另一端如tail 端出列双端队列可以在 head 进出也可以在 tail 进出。
栈的模型更加简单它分为 top 和 bottom 两个指针只能在 top 端进出。
经典的模型结构包含几个主要方法进、出、isEmpty、size 等。
一、队列的实现
不论是单向队列还是双端队列始终都是在操作 head 和 tail 两个指针。它们的实现没有什么本质区别实际上掌握了双端队列单向队列就易如反掌。
在手动实现队列的时候需要在脑海中模拟出队列的构造左侧为 head 右侧为 tail 因此队列中一定需要两个特殊的成员变量head 和 tail。
其次由于队列和栈都属于逻辑结构因此我们必须考虑使用哪种底层数据结构来实现一般有两个最典型的结构可供使用双向链表、数组。
1.1 双端队列的实现
首先我们需要敲定队列中的节点的数据结构双向链表是个不错的选择它不受空间的约束这是相对于数组实现的一个明显的有点。
经典的双向链表结构 private static class NodeT {public T value;private NodeT prev;private NodeT next;public Node(T value) {this.value value;}Overridepublic String toString() {return value.toString();}}
建议把Node设计为私有静态内部类作为队列内部的存储对象 T 的容器它不需要被外界感知。
双端队列需要四个进出方法头进头出尾进尾出。
以头进为例当接收到一个入列对象时我们需要先封装为 Node 类型的 cur 然后判断队列是否为空即是否 head null如果为空那么当前元素即是 head 也是 tail
if (head null) {// 如果是第一个元素则头尾都指向curhead cur;tail cur;
}
如果不为空那么需要建立 cur 与 head 之间的链表关系即 cur.next headhead.prev cur。然后head角色变为 cur就完成了入列操作
else {// 如果不是第一个元素// cur在前head在后建立链表关系cur.next head;head.prev cur;// head更新head cur;
}
再以尾出为例返回值为泛型 T首先同样是要判断队列是否为空head null?如果空则直接返回null。若存在元素首先我们要拿到 tail 元素将它保存下来。
然后关键要判断是否队列中仅存在一个元素即 head tail如果只有一个元素那么取出后需要将 head 和 tail 都变为 null
if (head tail) {head null;tail null;
}
若不是最后一个那么和入列相反我们需要斩断 Node 之间的引用关系刚刚我们已经将原来的 tail 并保存到了一个新的 Node 局部变量里此时已经可以将其成功返回但除此之外还需要释放一些指针空间并改变 tail 的指向
else {// tail 前移tail tail.prev;// 释放空间cur.prev null;tail.next null;
}
return cur.value;
剩下的方法逻辑大同小异一定不要搞混 Node 节点的 prev 和 next与 head 和 tail明确并牢记这些概念的含义以及链表左头右尾的方向入列时要建立两个节点之间的对应关系出列时要切断两个节点之间的关系。以下是完整代码示例
/*** 使用链表实现的双端队列*/
public class MyDoubleEndsQueueT {private NodeT head;private NodeT tail;private int size 0;private static class NodeT {T value;NodeT prev;NodeT next;public Node(T value) {this.value value;}Overridepublic String toString() {return value.toString();}}public void addFromHead(T value) {size;NodeT cur new NodeT(value);if (head null) {// 如果是第一个元素则头尾都指向curhead cur;tail cur;} else {// 如果不是第一个元素// cur在前head在后建立链接关系cur.next head;head.prev cur;// head更新head cur;}}public void addFromTail(T value) {size;NodeT cur new Node(value);if (tail null) {head cur;tail cur;} else {tail.next cur;cur.prev tail;tail cur;}}public T popFromHead() {if (head null) return null;size--;NodeT cur head;if (head tail) {// 只有一个元素head null;tail null;} else {head head.next;cur.next null;head.prev null;}return cur.value;}public T popFromTail() {if (tail null) return null;size--;NodeT cur tail;if (head tail) {head null;tail null;} else {// tail 前移tail tail.prev;// 释放空间cur.prev null;tail.next null;}return cur.value;}public boolean isEmpty() {return head null;}public int size() {return size;}
}1.2 单向队列
1.2.1 双向链表实现
单向队列的实现可以建立在双端队列的基础之上直接调用其方法或使用相同的逻辑来完成实现完整代码如下
/*** 使用链表实现的单向队列*/
public class MyQueueT {private NodeT head;private NodeT tail;private int size 0;private static class NodeT {NodeT prev;T value;NodeT next;public Node(T value) {this.value value;}Overridepublic String toString() {return value.toString();}}/*** 头进** param t*/public void push(T t) {NodeT cur new Node(t);size;if (isEmpty()) {head cur;tail cur;} else {head.prev cur;cur.next head;head cur;}}/**** 尾出* return*/public T pop() {if (isEmpty()) return null;size--;NodeT cur tail;if (head tail) {head null;tail null;} else {tail tail.prev;cur.prev null;tail.next null;}return cur.value;}public boolean isEmpty() {return head null;}public int size() {return size;}
}1.2.2 数组实现队列
数组实现队列相对复杂一些由于数组是定长结构因此需要在创建之初设定大小且这一大小如果不涉及扩容在使用过程中是不可变更的。
另一方面由于数组的大小被限定因此必须循环使用数组空间如果数组满了再添加元素以及数组空了再取元素这两种情况都需要报错。
为了不陷入头尾追赶的怪圈逻辑在使用数组实现队列时需要特别小心不要去考虑收尾追击的问题只需要通过 size 来控制首尾自然不会出现“交叉”的情况。 /*** 环形数组队列*/
public class RingArrayQueueT {private T[] arr;private int pushIdx;private int popIdx;private int size;private final int limit;public RingArrayQueue(ClassT type, int limit) {this.arr (T[]) Array.newInstance(type, limit);this.pushIdx 0;this.popIdx 0;this.size 0;this.limit limit;}public void push(T t) {if (size limit)throw new RuntimeException(队列满了不能再加了);size;arr[pushIdx] t;pushIdx nextIndex(pushIdx);}public T pop() {if (size 0)throw new RuntimeException(队列空了);size--;T t (T) arr[popIdx];popIdx nextIndex(popIdx);return t;}public boolean isEmpty() {return size 0;}public int size() {return size;}// 如果现在的下标是i返回下一个位置private int nextIndex(int i) {return i limit - 1 ? i 1 : 0;}
}
二、栈的实现
有了双端队列的逻辑铺垫栈的实现完全可以照搬完整代码如下
/*** 使用链表实现的栈*/
public class MyStackT {private NodeT top;private NodeT bottom;private int size 0;private static class NodeT {NodeT prev;T value;NodeT next;public Node(T value) {this.value value;}Overridepublic String toString() {return value.toString();}}public void push(T t) {NodeT cur new Node(t);if (isEmpty()) {top cur;bottom cur;} else {top.next cur;cur.prev top;top cur;}}public T pop() {if (isEmpty()) {return null;}size--;NodeT cur top;if (top bottom) {top null;bottom null;} else {top top.prev;top.next null;cur.prev null;}return cur.value;}public boolean isEmpty() {return top null;}public int size() {return size;}
}三、测试
使用jdk自带的数据结构来对照测试自定义的队列和栈完整代码如下
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class Checker {public static void main(String[] args) {int oneTestDataNum 100;int value 10000;int testTimes 100000;for (int i 0; i testTimes; i) {MyStackInteger myStack new MyStack();MyQueueInteger myQueue new MyQueue();// 对照组StackInteger stack new Stack();QueueInteger queue new LinkedList();for (int j 0; j oneTestDataNum; j) {int nums (int) (Math.random() * value);if (stack.isEmpty()) {myStack.push(nums);stack.push(nums);} else {if (Math.random() 0.5) {myStack.push(nums);stack.push(nums);} else {if (!isEqual(myStack.pop(), stack.pop())) {System.out.println(oops!);}}}int numq (int) (Math.random() * value);if (stack.isEmpty()) {myQueue.push(numq);queue.offer(numq);} else {if (Math.random() 0.5) {myQueue.push(numq);queue.offer(numq);} else {if (!isEqual(myQueue.pop(), queue.poll())) {System.out.println(oops!);}}}}}System.out.println(finish!);}public static boolean isEqual(Object o1, Object o2) {if (o1 null) {return o1 o2;}return o1.equals(o2);}
}四、实现一个查找最小值的时间复杂度是 O(1) 的栈
设计思路使用一个单独的栈用于存储数据栈的最小值在每次push 的时候判断是否为最小值如果是则如 minStack如果不是则继续压入上一次的最小值。完整代码如下
import java.util.Stack;public class GetMinStack {public static class MyMinStack {private StackInteger dataStack;private StackInteger minStack;public MyMinStack() {this.dataStack new Stack();this.minStack new Stack();}public void push(Integer num) {if (minStack.isEmpty()) {minStack.push(num);} else if (getMin() num) {minStack.push(num);} else {minStack.push(getMin());}dataStack.push(num);}public Integer pop() {if (dataStack.isEmpty()) {return null;}minStack.pop();return dataStack.pop();}public Integer getMin() {if (minStack.isEmpty())return null;return minStack.peek();}}public static void main(String[] args) {MyMinStack stack1 new MyMinStack();stack1.push(3);System.out.println(stack1.getMin());stack1.push(4);System.out.println(stack1.getMin());stack1.push(1);System.out.println(stack1.getMin());System.out.println(stack1.pop());System.out.println(stack1.getMin());}}五、只使用栈实现队列
只使用栈实现队列和只使用队列实现栈在面试中还比较常见例如用栈来实现一个图的宽度优先遍历或用队列来实现图的深度优先遍历但图的宽度优先遍历一定需要用队列来实现而深度优先遍历也一定要用栈来实现因此我们可以通过栈与队列的转化来完成类似这样的面试题。
使用栈来实现队列的思路是用两个栈分别存储入栈的顺序和出栈的顺序因为栈的出栈顺序是入栈时的反向因此只要两个栈互倒就可以实现队列的结构。
互倒是一种思路还有一种思路是只从push 栈往 pop 栈倒这样的方式可以减少一定的性能开销但需要保证两个原则1、如果决定要倒数据必须一定倒完2、只要pop为空时才可以倒入。
以下是两种实现代码第一个是互倒的方式第二个是单向倒入的方式
import java.util.Stack;/*** 使用两个栈来实现队列*/
public class TwoStackQueueT {private StackT pushStack;private StackT popStack;public TwoStackQueue() {this.pushStack new Stack();this.popStack new Stack();}private synchronized void reverseStack(StackT from, StackT to) {while (!from.isEmpty()) {to.push(from.pop());}}public void push(T t) {if (!popStack.isEmpty()) {reverseStack(popStack, pushStack);}pushStack.push(t);}public T pop() {if (!pushStack.isEmpty())reverseStack(pushStack, popStack);if (!popStack.isEmpty())return popStack.pop();elsereturn null;}
}import java.util.Stack;/*** 单向倒入双栈队列*/
public class SingleDirTwoStackQueueT {private StackT pushStack;private StackT popStack;public SingleDirTwoStackQueue() {pushStack new Stack();popStack new Stack();}private void pushToPop() {// 两点原则// 1、pop栈必须为空时才倒入if (popStack.empty()) {// 2、要倒就一次性全倒完while (!pushStack.empty()) {popStack.push(pushStack.pop());}}}public void push(T t) {pushStack.push(t);pushToPop();}public T pop() {if (popStack.empty() pushStack.empty()) {return null;}pushToPop();return popStack.pop();}public T peek() {if (popStack.empty() pushStack.empty()) {return null;}pushToPop();return popStack.peek();}public static void main(String[] args) {SingleDirTwoStackQueueInteger queue new SingleDirTwoStackQueue();for (int i 0; i 100; i) {// 多存少取if (Math.random() 0.7) {queue.push(i);} else {System.out.print(queue.pop() \t);}}System.out.println(\n);while (true) {Integer tail queue.pop();if (tail null) break;System.out.print(tail \t);}}
}
六、只使用队列实现栈
使用经典的单向队列实现栈结构。
思路是使用两个队列masterQueue和slaveQueue放入的时候正常放入当要取出的时候循环将元素从master放入到slave中最后只留 1 个元素并返回然后将 slave 与 master 的引用互换。
完整代码如下
import java.util.LinkedList;
import java.util.Queue;/*** 双队列栈*/
public class TwoQueueStackT {private QueueT masterQueue;private QueueT slaveQueue;public TwoQueueStack() {this.masterQueue new LinkedList();this.slaveQueue new LinkedList();}public void push(T t) {masterQueue.offer(t);}public T poll() {while (masterQueue.size() 1)slaveQueue.offer(masterQueue.poll());T ans masterQueue.poll();QueueT tmp masterQueue;masterQueue slaveQueue;slaveQueue tmp;return ans;}public T peek() {while (masterQueue.size() 1)slaveQueue.offer(masterQueue.poll());T ans masterQueue.poll();// peek 与 poll的区别就是取出后再次放回slaveQueue.offer(ans);QueueT tmp masterQueue;masterQueue slaveQueue;slaveQueue tmp;return ans;}}
