队列
队列的使用场景
介绍
实现方式
数组
代码实现
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
| class ArrayQueue{ private int maxSize; private int front; private int rear; private int[] arr;
public ArrayQueue(int arrMaxSize){ maxSize = arrMaxSize; arr = new int[arrMaxSize]; front = -1; rear = -1; }
private boolean isFull(){ return rear == maxSize -1; }
private boolean isEmpty(){ return rear == front; }
private void addQueue(int n){ if (isFull()){ System.out.println("队列满了。。。"); return; } arr[rear++] = n; }
private int getQueue(){ if (isEmpty()){ throw new RuntimeException("队列是空的"); } return arr[front++]; }
private void showQueue(){ if (isEmpty()){ System.out.println("队列是空的。。。"); return; } for (int i = 0; i < arr.length; i++) { System.out.printf("arr[%d]=%d\n",i,arr[i]); } }
public int headQueue(){ if (isEmpty()){ System.out.println("队列是空的。。。"); throw new RuntimeException("队列是空的"); } return arr[front + 1]; } }
|
测试代码
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
| public static void main(String[] args) { ArrayQueue queue = new ArrayQueue(3); char key = ' '; Scanner scanner = new Scanner(System.in); boolean boo = true; while (boo){ key = scanner.next().charAt(0); switch (key){ case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': try { int queue1 = queue.getQueue(); System.out.println("取出的数据是:" +queue1); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'h': try { int queue1 = queue.headQueue(); System.out.println("头数据是:" +queue1); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'e': scanner.close(); boo = false; break; default: break; }
} }
|
存在问题及分析优化
- 目前数组使用一次就不能再次使用了,没有达到复用的效果。
- 将这个数组使用算法,改进成一个环形数组。
数组模拟环形队列
对前面的数组模拟队列的优化,充分利用数组,因此将数组看做是一个环形的。(通过取模的方式来实现即可)
思路分析
代码实现
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 101 102
| class CircleQueue{
private int maxSize; private int front; private int rear; private int[] arr;
public CircleQueue(int arrMaxSize){ maxSize = arrMaxSize; arr = new int[maxSize]; }
private boolean isFull(){ return (rear + 1) % maxSize == front; }
private boolean isEmpty(){ return rear == front; }
public void addQueue(int n){ if (isFull()){ System.out.println("队列满了。。。"); return; } arr[rear] = n; rear = (rear + 1) % maxSize; }
public int getQueue(){ if (isEmpty()){ throw new RuntimeException("队列是空的"); } int value = arr[front]; front = (front + 1) % maxSize; return value; }
public void showQueue(){ if (isEmpty()){ System.out.println("队列是空的。。。"); return; } for (int i = front; i < front + size(); i++) { System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]); } }
public int size(){ return (rear + maxSize - front) % maxSize; }
public int headQueue(){ if (isEmpty()){ System.out.println("队列是空的。。。"); throw new RuntimeException("队列是空的"); } return arr[front]; } }
|
测试一把
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
| public static void main(String[] args) { CircleQueue queue = new CircleQueue(4); char key = ' '; Scanner scanner = new Scanner(System.in); boolean boo = true; while (boo){ key = scanner.next().charAt(0); switch (key){ case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': try { int queue1 = queue.getQueue(); System.out.println("取出的数据是:" +queue1); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'h': try { int queue1 = queue.headQueue(); System.out.println("头数据是:" +queue1); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'e': scanner.close(); boo = false; break; default: break; }
} }
|