最近也在逐步复习一些数据结构与算法的知识，发现学习过程中的代码都是很死板的，只是单纯解释了数据结构与算法的原理，代码的重用性、规范性、面向接口编程一点都没有体现出来。为此，我特地写一篇额外的博客，解析下数据结构与算法之面向对象写法。并顺便给大家一个我学习的笔记大礼包。
文章结构(完整Demo在文末链接给出)：面向接口编程之队列例子（顺序队列、链式队列以及循环队列）
队列例子（顺序队列、链式队列以及循环队列）：
先定接口：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//队列的基本行为在此 public interface Queue { //入队 public void append(Object obj); //出队 public Object delete(); //获得队头元素 public Object getHead(); //判断队列是否为空 public boolean isEmpty(); } |
顺序队列：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
//结点类 class DATA4 { String name; int age; } class SQType implements Queue{ static final int QUEUELEN = 15; // 队列大小 DATA4[] data = new DATA4[QUEUELEN]; // 队列数组 int head; // 队头 int tail; // 队尾 //队列初始化 SQType SQTypeInit() { SQType q; if ((q = new SQType()) != null) { // 创建对象，申请内存，申请成功就返回该对象 q.head = 0; // 设置队头 q.tail = 0; // 设置队尾 return q; } else { return null; // 返回空 } } //释放队列 void SQTypeFree(SQType q){ if(q!=null){ q=null; //在java的回收机制中，把队列对象至null，回收机制会把他至于弱引用状态，当系统垃圾回收机制运行就会回收他 } } // 判断空队列 @Override public boolean isEmpty() { return (head == tail);// 如果队头标志跟队尾标志相等就为空 } // 判断满队列 int SQTypeIsFull(SQType q) { int temp = 0; if (q.tail == QUEUELEN) { // 如果队列中没有多余的控件保存额外数据，就不可进行入队列操作 temp = 1; } return temp; } // 入队列 @Override public void append(Object data4) { if (tail == QUEUELEN) { System.out.print("队列已满！操作失败！\n"); // 如果队尾标志等于队列分配的大小 } else { data[tail++] = (DATA4) data4; // 如果队列没满，则插入到队尾中（队尾tail标记最后队列当前最后一个元素）。 } } //出队列操作 public Object delete(){ if(head==tail){ System.out.print("\n队列已空！操作失败！\n"); //先判断队头和队尾，如果相等则表示空队列 System.exit(0); }else{ //如果不相同，那就把数据在队头那里移出。在返回数据时，把队头那边返回的数据减一位 return data[head++]; } return null; } //读取结点数据，然而只可以读取队头的数据 public Object getHead(){ if(isEmpty()==true){ System.out.print("\n空队列!\n"); return null; }else{ return data[head]; } } //计算队列长度 int SQType(SQType q){ int temp; temp=q.tail-q.head; return (temp); } } |
链式队列：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
class LinkQueue implements Queue{ Node head; Node tail; int count;//结点数量记录 public LinkQueue() { init(); } //初始化队列 public void init() { head = tail = null; count = 0; } // 插入队列 @Override public void append(Object obj) { Node node = new Node(obj, null); // 如果当前队列不为空。 if (tail != null) { tail.next = node;// 队尾结点指向新结点 } tail = node;// 设置队尾结点为新结点 if (head == null) { head = node; } count++; } // 删除队头结点： @Override public Object delete() { if (isEmpty() == true) { System.out.println("队列为空！！"); return null; } Node node = head; head = head.next;//把头结点给到下一个结点，先进先出原则 count--; return node; } //拿到头结点： @Override public Object getHead() { if (isEmpty() == true) { System.out.println("队列为空！！"); return null; } else { return head.getElement();//直接往头结点拿数据域 } } // 判空 @Override public boolean isEmpty() { return count == 0; } } //结点类： class Node { Object element; // 数据域 Node next; // 指针域 // 头结点的构造方法 public Node(Node nextval) { this.next = nextval; } // 非头结点的构造方法 public Node(Object obj, Node nextval) { this.element = obj; this.next = nextval; } // 获得当前结点的后继结点 public Node getNext() { return this.next; } // 获得当前的数据域的值 public Object getElement() { return this.element; } // 设置当前结点的指针域 public void setNext(Node nextval) { this.next = nextval; } // 设置当前结点的数据域 public void setElement(Object obj) { this.element = obj; } public String toString() { return this.element.toString(); } } |
循环队列：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// tail可能比head大，也可能比head小，所以我们必须处理好这个关系！！那就是巧妙利用取余！ class CircleQueue implements Queue{ static final int defaultSize = 10; // 默认队列的长度 int head; int tail; int count;// 统计元素个数的计数器 int maxSize; // 队的最大长度 Object[] queue; // 队列 public CircleQueue() { init(defaultSize); } public void init(int size) { maxSize = size; head = tail = 0; count = 0; queue = new Object[size]; } // 插入队列 @Override public void append(Object obj) { //这里打印队列已满，只是为了说明一下而已！！！还是会继续用覆盖去存储！！ if (count > 0 && head == tail) { System.out.println("队列已满！！"); } queue[tail] = obj; // 这样做的意思是：如果(tail+1)%maxSize与head所指示的是相同位置，则说明队列已满。 // 因此，我们不断把指针往后移动一个位置，到最后就转到数组头部。 tail = (tail + 1) % maxSize; count++; } // 删除队头结点： @Override public Object delete() { if (isEmpty()) { System.out.println("队列为空！！"); } Object obj = queue[head]; head = (head + 1) % maxSize;// 将head指针往后移动一个位置，如果到了最后了就转到数组头部。 count--; return obj; } // 拿到队列的头 @Override public Object getHead() { if (isEmpty() == true) { System.out.println("队列为空！！"); return null; } else { return queue[head]; } } // 判空 @Override public boolean isEmpty() { return count == 0; // 还有一个计算长度的方法：(tail-head+maxSize)%maxSize } } |
源码下载：学习笔记大礼包以及即将推出的初阶题进阶题
本博客讲的例子的demo也在里面。
好了，数据结构与算法-面向对象之队列（里含学习笔记大礼包以及即将推出的初阶题进阶题）讲完了。本博客又是一个新的系列，不过这个以我以前的笔记为主，囊括数据结构与常见算法，此外，不久后会不断推出初阶题以及进阶题，我会逐渐出给大家，分享经验给大家。欢迎在下面指出错误，共同学习！！你的点赞是对我最好的支持！！
更多内容，可以访问JackFrost的博客
码字很辛苦，转载请注明来自JackFrost的《数据结构与算法-面向对象之队列（里含学习笔记大礼包以及即将推出的初阶题进阶题java描述）》
Leave a Reply