《Java数据结构跟算法》第二版 Robert lafore 编程作业 第四章

《Java数据结构和算法》第二版 Robert lafore 编程作业 第四章

《Java数据结构和算法》第二版 Robert lafore  编程作业 第四章

4.1 为queue.java 程序（清单4.4）的Queue类中写一个方法，显示队列的 内容。注意这并不是要简单的显示出数组的内容。它要求按数据项插入的队 列的顺序，从第一个插入的数据项到最后一个插入的数据项显示出来。不要 输出因为在数组末端回绕而折成两半的样子。注意无论front和rear在什么 位置上，都要正确显示出一个数据项和没有数据项的情况。

4.2 根据本章里对双端队列的讨论编写一个Deque类，它应该包括 insertLeft()、insertRight()、removeLeft()、removeRight()、 isEmpty()、isFull()方法。要求像队列那样支持在数据末端的回绕。

4.3 编写一个基于上机作业4.2的Deque类的栈类。这个栈类应该与 stack.java程序（清单4.1）中的StackX类具有机同的方法和功能。

4.4 清单4.6中展示的优先级队列能够快速地删除最高优先级的数据项，但是 插入数据项较慢。还要包括一个显示优先级队列内容的方法，要求和上机作 业4.1中一样。

4.5 队列通用于模拟人、汽车、飞机、业务等等的流动情况。应用queue.java 程序（清单4.4）的Queue类，编写一个程序模拟超市的收款队列。可以用上机 作业4.1的display()方法，显示出顾客的几条队列。可以通过敲击一个键插入 一个新的顾客。为顾客选择在哪一个队列上。收银员为每个顾客服务的时间是 随机的（可假定为按照顾客买了多少东西而定）。一旦结完账，就从队列中删 除该顾客。为了简单起见，通过敲击键模拟时间的流逝。可能每点击一下键表 示时间过去了1分钟。（当然，java有更复杂的方式来处理时间。）

/* 编程作业 4.1 为queue.java 程序（清单4.4）的Queue类中写一个方法，显示队列的 内容。注意这并不是要简单的显示出数组的内容。它要求按数据项插入的队 列的顺序，从第一个插入的数据项到最后一个插入的数据项显示出来。不要 输出因为在数组末端回绕而折成两半的样子。注意无论front和rear在什么 位置上，都要正确显示出一个数据项和没有数据项的情况。 4.2 根据本章里对双端队列的讨论编写一个Deque类，它应该包括 insertLeft()、insertRight()、removeLeft()、removeRight()、 isEmpty()、isFull()方法。要求像队列那样支持在数据末端的回绕。 4.3 编写一个基于上机作业4.2的Deque类的栈类。这个栈类应该与 stack.java程序（清单4.1）中的StackX类具有机同的方法和功能。 4.4 清单4.6中展示的优先级队列能够快速地删除最高优先级的数据项，但是 插入数据项较慢。还要包括一个显示优先级队列内容的方法，要求和上机作 业4.1中一样。 4.5 队列通用于模拟人、汽车、飞机、业务等等的流动情况。应用queue.java 程序（清单4.4）的Queue类，编写一个程序模拟超市的收款队列。可以用上机 作业4.1的display()方法，显示出顾客的几条队列。可以通过敲击一个键插入 一个新的顾客。为顾客选择在哪一个队列上。收银员为每个顾客服务的时间是 随机的（可假定为按照顾客买了多少东西而定）。一旦结完账，就从队列中删 除该顾客。为了简单起见，通过敲击键模拟时间的流逝。可能每点击一下键表 示时间过去了1分钟。（当然，java有更复杂的方式来处理时间。） */package chap04;// Queue.java// demonstrates queue// to run this program: C>java QueueApp////////////////////////////////////////////////////////////////class Queue {private int maxSize;private long[] queArray;private int front;private int rear;private int nItems;// --------------------------public Queue(int s) // constructor{maxSize = s;queArray = new long[maxSize];front = 0;rear = -1;nItems = 0;}// --------------------------public void insert(long j) // put item at rear of queue{if (rear == maxSize - 1) // deal with wraparoundrear = -1;queArray[++rear] = j; // increment rear and insertnItems++; // one more item}// --------------------------public long remove() // take item from front of queue{long temp = queArray[front++]; // get value and incr frontif (front == maxSize) // deal with wraparoundfront = 0;nItems--; // one less itemreturn temp;}// --------------------------public long peekFront() // peek at front of queue{return queArray[front];}// --------------------------public boolean isEmpty() // true if queue is empty{return (nItems == 0);}// --------------------------public boolean isFull() // true if queue is full{return (nItems == maxSize);}// --------------------------public int size() // number of items in queue{return nItems;}// --------------------------// ===========================================================// 编程作业 4.1public void display() {System.out.print("队列为：");if (nItems == 0) {System.out.println("空。");return;}if (rear >= front) {for (int i = front; i <= rear; i++) {System.out.print(queArray[i] + " ");}} else {for (int i = front; i < maxSize; i++) {System.out.print(queArray[i] + " ");}for (int i = 0; i <= rear; i++) {System.out.print(queArray[i] + " ");}}System.out.println();}// ===========================================================} // end class Queue// //////////////////////////////////////////////////////////////public class QueueApp {public static void main(String[] args) {Queue theQueue = new Queue(5); // queue holds 5 itemstheQueue.display();theQueue.insert(10); // insert 4 itemstheQueue.insert(20);theQueue.insert(30);theQueue.insert(40);theQueue.remove(); // remove 3 itemstheQueue.remove(); // (10, 20, 30)theQueue.remove();theQueue.insert(50); // insert 4 more itemstheQueue.insert(60); // (wraps around)theQueue.insert(70);theQueue.insert(80);// =========================================theQueue.display();// =========================================while (!theQueue.isEmpty()) // remove and display{ // all itemslong n = theQueue.remove(); // (40, 50, 60, 70, 80)System.out.print(n);System.out.print(" ");}System.out.println("");} // end main()} // end class QueueApp// //////////////////////////////////////////////////////////////

package chap04;//======================================================================//编程作业 4.2class DuQueue {private int maxSize;private long[] queArray;private int front;private int rear;private int nItems;public DuQueue(int size) {maxSize = size;queArray = new long[maxSize];front = 0;rear = -1;nItems = 0;}public void insertLeft(long value) {if (front == 0) {front = maxSize;}queArray[--front] = value;nItems++;}public void insertRight(long value) {if (rear == maxSize - 1) {rear = -1;}queArray[++rear] = value;nItems++;}public long removeLeft() {long temp = queArray[front++];if (front == maxSize) {front = 0;}nItems--;return temp;}public long removeRight() {long temp = queArray[rear--];if (rear == -1) {rear = maxSize - 1;}nItems--;return temp;}public long peekLeft() {return queArray[front];}public long peekRight() {return queArray[rear];}public boolean isEmpty() {return nItems == 0;}public boolean isFull() {return nItems == maxSize;}public int size() {return nItems;}public void display() {System.out.print("队列为：");if (nItems == 0) {System.out.println("空。");return;}if (rear >= front) {for (int i = front; i <= rear; i++) {System.out.print(queArray[i] + " ");}} else {for (int i = front; i < maxSize; i++) {System.out.print(queArray[i] + " ");}for (int i = 0; i <= rear; i++) {System.out.print(queArray[i] + " ");}}System.out.println();}}// ======================================================================public class DuQueueApp {public static void main(String[] args) {DuQueue theQueue = new DuQueue(5); // queue holds 5 itemsSystem.out.println("队例是否为空：" + theQueue.isEmpty());System.out.println("队例是否为满：" + theQueue.isFull());System.out.println("队列的大小为：" + theQueue.size());theQueue.display();theQueue.insertRight(10); // insert 4 itemstheQueue.insertRight(20);theQueue.insertRight(30);theQueue.insertRight(40);System.out.println("队列的大小为：" + theQueue.size());theQueue.display();theQueue.removeLeft(); // remove 3 itemstheQueue.removeLeft(); // (10, 20, 30)theQueue.removeLeft();System.out.println("队列的大小为：" + theQueue.size());theQueue.display();theQueue.insertLeft(50); // insert 4 more itemstheQueue.insertLeft(60); // (wraps around)theQueue.insertLeft(70);theQueue.insertLeft(80);System.out.println("队例是否为空：" + theQueue.isEmpty());System.out.println("队例是否为满：" + theQueue.isFull());System.out.println("队列的大小为：" + theQueue.size());theQueue.display();theQueue.removeRight(); // remove 3 itemstheQueue.removeRight(); // (10, 20, 30)theQueue.removeRight();System.out.println("队列的大小为：" + theQueue.size());theQueue.display();} // end main()} // end class QueueApp

package chap04;//==========================================================//编程作业 4.3class StackY {private DuQueue stackQueue;public StackY(int size) {stackQueue = new DuQueue(size);}public void push(long value) {stackQueue.insertRight(value);}public long pop() {return stackQueue.removeRight();}public long peek() {return stackQueue.peekRight();}public boolean isEmpty() {return stackQueue.isEmpty();}public boolean isFull() {return stackQueue.isFull();}}// ==========================================================public class StackApp {public static void main(String[] args) {StackY theStack = new StackY(5); // make new stackSystem.out.println("Stack is Empty : " + theStack.isEmpty());System.out.println("Stack is Full : " + theStack.isFull());theStack.push(20); // push items onto stacktheStack.push(40);theStack.push(60);theStack.push(80);theStack.push(90);System.out.println("Stack is Empty : " + theStack.isEmpty());System.out.println("Stack is Full : " + theStack.isFull());while (!theStack.isEmpty()) // until it's empty,{ // delete item from stacklong value = theStack.pop();System.out.print(value); // display itSystem.out.print(" ");} // end whileSystem.out.println("");} // end main()} // end class StackApp

package chap04;// priorityQ.java// demonstrates priority queue// to run this program: C>java PriorityQApp////////////////////////////////////////////////////////////////class PriorityQ {// array in sorted order, from max at 0 to min at size-1private int maxSize;private long[] queArray;private int nItems;// -------------------------public PriorityQ(int s) // constructor{maxSize = s;queArray = new long[maxSize];nItems = 0;}// -------------------------// ==============================================================// 编程作业 4.4public void insert(long item) // insert item{queArray[nItems++] = item; // insert at 0} // end insert()// ==============================================================// 编程作业 4.4public long remove() // remove minimum item{int highPriority = 0;for (int i = 1; i < nItems; i++) {if (queArray[i] < queArray[highPriority]) {highPriority = i;}}long temp = queArray[highPriority];for (int i = highPriority; i < nItems - 1; i++) { // 数组后面部份往前移queArray[i] = queArray[i + 1];}nItems--;return temp;}// ==============================================================// 编程作业 4.4 //题目有 歧义// 方法一 ：如果按插入的顺序显示public void display() {System.out.print("队列为：");for (int i = 0; i < nItems; i++) {System.out.print(queArray[i] + " ");}System.out.println();}// 方法二：如果按按优先级顺序显示public void display1() {long[] temp = new long[nItems];// 临时表System.arraycopy(queArray, 0, temp, 0, nItems); // 复制到临时表int out, in;for (out = 1; out < nItems; out++) {in = out;long t = temp[out];while (in > 0 && t < temp[in - 1]) {temp[in] = temp[in - 1];in--;}temp[in] = t;}System.out.print("队列为：");for (int i = 0; i < nItems; i++) {System.out.print(temp[i] + " ");}System.out.println();}// ==============================================================// -------------------------public long peekMin() // peek at minimum item{return queArray[nItems - 1];}// -------------------------public boolean isEmpty() // true if queue is empty{return (nItems == 0);}// -------------------------public boolean isFull() // true if queue is full{return (nItems == maxSize);}// -------------------------} // end class PriorityQ// //////////////////////////////////////////////////////////////public class PriorityQApp {public static void main(String[] args) {PriorityQ thePQ = new PriorityQ(5);thePQ.insert(30);thePQ.insert(50);thePQ.insert(10);thePQ.insert(40);thePQ.insert(20);thePQ.display();//thePQ.display1();while (!thePQ.isEmpty()) {long item = thePQ.remove();System.out.print(item + " "); // 10, 20, 30, 40, 50} // end whileSystem.out.println("");} // end main()// -------------------------} // end class PriorityQApp// //////////////////////////////////////////////////////////////

package chap04;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Utility {public static String getString() throws IOException {// 接受键盘输入字符串InputStreamReader in = new InputStreamReader(System.in);BufferedReader bf = new BufferedReader(in);String s = bf.readLine();return s;}}// ===============================================================// 编程作业 4.5 没有完全按照题目要求public class SuperMarket {private Queue[] queue = { null, new Queue(20), new Queue(20), new Queue(20), new Queue(20) }; // 4个顾客队列// 模拟收银public void simulate() throws IOException {long id = 0; // 顾客编号boolean flag = true;while (flag) {System.out.println("请选择事件：");System.out.print("0.有顾客进入某个队列。");System.out.print("1.有顾客离开第1个队例。");System.out.print("2.有顾客离开第2个队例。");System.out.print("3.有顾客离开第3个队例。");System.out.print("4.有顾客离开第4个队例。");System.out.println("q.表示程序退出！");String s = Utility.getString();if (s.length() == 0) {// 直接输入回车continue;}char ch = s.charAt(0);switch (ch) {case '0':id++;insertQueue(id); // 顾客进入队列displayQueue(); // 显示队列break;case '1':removeQueue(1); // 顾客离开队列displayQueue(); // 显示队列break;case '2':removeQueue(2);displayQueue();break;case '3':removeQueue(3);displayQueue();break;case '4':removeQueue(4);displayQueue();break;case 'q': // 退出程序flag = false;System.out.println("byebye!");break;default:break;}}}// 从队列中删除顾客private void removeQueue(int queueId) {if (queue[queueId].size() == 0) {return;}long id = queue[queueId].remove();System.out.println("顾客" + id + "离开第" + queueId + "个队列！");}// 把顾客插入到队列public void insertQueue(long id) {int queueId = getMinQueueId();queue[queueId].insert(id);System.out.println("顾客" + id + "进入第" + queueId + "个队例");}// 得到最小队列的编号private int getMinQueueId() {int min = 1;for (int i = 2; i < 5; i++) {if (queue[i].size() < queue[min].size()) {min = i;}}return min;}// 打印显示四条队列public void displayQueue() {for (int i = 1; i < 5; i++) {System.out.print("第" + i + "个");queue[i].display();}System.out.println();}public static void main(String[] args) throws IOException {SuperMarket sm = new SuperMarket();sm.simulate();}}