《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 wraparound
			rear = -1;
		queArray[++rear] = j; // increment rear and insert
		nItems++; // one more item
	}

	// --------------------------
	public long remove() // take item from front of queue
	{
		long temp = queArray[front++]; // get value and incr front
		if (front == maxSize) // deal with wraparound
			front = 0;
		nItems--; // one less item
		return 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.1
	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();
	}
	// ===========================================================
} // end class Queue
// //////////////////////////////////////////////////////////////

public class QueueApp {
	public static void main(String[] args) {
		Queue theQueue = new Queue(5); // queue holds 5 items
		theQueue.display();
		theQueue.insert(10); // insert 4 items
		theQueue.insert(20);
		theQueue.insert(30);
		theQueue.insert(40);

		theQueue.remove(); // remove 3 items
		theQueue.remove(); // (10, 20, 30)
		theQueue.remove();

		theQueue.insert(50); // insert 4 more items
		theQueue.insert(60); // (wraps around)
		theQueue.insert(70);
		theQueue.insert(80);

		// =========================================
		theQueue.display();
		// =========================================

		while (!theQueue.isEmpty()) // remove and display
		{ // all items
			long 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.2
class 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 items
		System.out.println("队例是否为空：" + theQueue.isEmpty());
		System.out.println("队例是否为满：" + theQueue.isFull());
		System.out.println("队列的大小为：" + theQueue.size());
		theQueue.display();
		theQueue.insertRight(10); // insert 4 items
		theQueue.insertRight(20);
		theQueue.insertRight(30);
		theQueue.insertRight(40);
		System.out.println("队列的大小为：" + theQueue.size());
		theQueue.display();

		theQueue.removeLeft(); // remove 3 items
		theQueue.removeLeft(); // (10, 20, 30)
		theQueue.removeLeft();
		System.out.println("队列的大小为：" + theQueue.size());
		theQueue.display();

		theQueue.insertLeft(50); // insert 4 more items
		theQueue.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 items
		theQueue.removeRight(); // (10, 20, 30)
		theQueue.removeRight();
		System.out.println("队列的大小为：" + theQueue.size());
		theQueue.display();

	} // end main()
} // end class QueueApp

package chap04;

//==========================================================
//编程作业 4.3
class 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 stack
		System.out.println("Stack is Empty : " + theStack.isEmpty());
		System.out.println("Stack is Full : " + theStack.isFull());
		theStack.push(20); // push items onto stack
		theStack.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 stack
			long value = theStack.pop();
			System.out.print(value); // display it
			System.out.print(" ");
		} // end while
		System.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-1
	private int maxSize;
	private long[] queArray;
	private int nItems;

	// -------------------------
	public PriorityQ(int s) // constructor
	{
		maxSize = s;
		queArray = new long[maxSize];
		nItems = 0;
	}

	// -------------------------
	// ==============================================================
	// 编程作业 4.4
	public void insert(long item) // insert item
	{
		queArray[nItems++] = item; // insert at 0
	} // end insert()

	// ==============================================================
	// 编程作业 4.4
	public 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 while
		System.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();
	}

}