JAVA第17天——队列（一）——队列的基础

（一） 、队的数据结构，C语言表示

（1）. 定义

• 和栈相反，队列（queue）是一种先进先出的线性表。
• 它只允许在表的一端进行插入，在另一端进行删除。
• 特点：FIFO
• 队列有两种储存方式：顺序表，和链表，我这只介绍链表，所以叫链队列

（2）. 图例

（3）. 链队列的数据结构

1. 单链队列的定义及初始

typedef struct QNode {
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
	QueuePtr front;
	QueuePtr rear;
}linkQueue;
Status InitQueue(linkQueue &Q) {
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if(!Q.front) return -2;
	Q.front->next = NULL;
	
	return OK; 
} //构造一个空队列 Q 

2. 队列 Q 是否为空队列

Status QueueEmpty(linkQueue &Q) {
	if(Q.front == Q.rear) return true;
	else return false;
} // 队列 Q 是否为空队列

3. 销毁 Q

Status DestroyQueue(linkQueue &Q) {
	while(Q.front) {
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	
	return OK;
} // 销毁 Q

4. 入队

Status EnQueue(linkQueue &Q, QElemType e) {
	QueuePtr *p;
	p = (QueuePtr)malloc(sizeof(QNode));
	if(!p) return -2;
	p->data = e; p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	
	return OK;
} // 插入e,为Q的新的队尾元素

5. 出队

Status DeQueue(linkQueue &Q, QElemType &e) {
	if(Q.front == Q.rear) return ERROR;
	QueuePtr p;
	p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if(Q.rear == p) Q.rear = Q.front;
	free(p);
	
	return OK; 
} // 删除Q的对头元素，并用e返回其值 

（二） 、队的实现，Java语言表示

1. 链表的结点,成员变量data,next

	
	class QNode {
		int data;
		QNode next;
		
		QNode(int QElemType) {
			data = QElemType;
			next = null;
		}// of the constructor for QNode
	}// of class QNode

2. 队是否为空

	
	public boolean QueueEmpty() {
		//if(head == tail) return true;
		if(head.next == null) return true;
		else return false;
	}

3. 入队 EnQueue

	
	public boolean EnQueue(int elem) {
		QNode tempNode = new QNode(elem);
		tail.next = tempNode;
		tail = tempNode;
		
		return true;
	}

4. 出队

	
	public int DeQueue() {
		if(head == tail) {
			System.out.println("Queue is Empty");
			return -1;
		} //of if for EmptyQueue
		
		int tempValue;
		tempValue = head.next.data;
		head.next = head.next.next;
		if(head.next == null) {
			tail = head;
		}
		
		return tempValue;
	}

5. 重写toString

	
	public String toString() {
		String tempString = "";
		if(head.next == null) {
			return "Queue is Empty";
		}
		
		QNode tempNode = head.next;
		while(tempNode!=null) {
			tempString += tempNode.data + " ";
			tempNode = tempNode.next;
		}
		
		return tempString;
	}

• linkQueue源码：

package cbb;

public class linkQueue {
	
	class QNode {
		int data;
		QNode next;
		
		QNode(int QElemType) {
			data = QElemType;
			next = null;
		}// of the constructor for QNode
	}// of class QNode
	
	
	QNode head;
	QNode tail;
	
	linkQueue() {
		head = new QNode(-1);
		tail = head;
	}//of the constructor for linkQueue
	
	
	public boolean QueueEmpty() {
		//if(head == tail) return true;
		if(head.next == null) return true;
		else return false;
	}
	
	public boolean EnQueue(int elem) {
		QNode tempNode = new QNode(elem);
		tail.next = tempNode;
		tail = tempNode;
		
		return true;
	}
	
	public int DeQueue() {
		if(head == tail) {
			System.out.println("Queue is Empty");
			return -1;
		} //of if for EmptyQueue
		
		int tempValue;
		tempValue = head.next.data;
		head.next = head.next.next;
		if(head.next == null) {
			tail = head;
		}
		
		return tempValue;
	}
	
	public String toString() {
		String tempString = "";
		if(head.next == null) {
			return "Queue is Empty";
		}
		
		QNode tempNode = head.next;
		while(tempNode!=null) {
			tempString += tempNode.data + " ";
			tempNode = tempNode.next;
		}
		
		return tempString;
	}
}

• 测试类：Test_linkQueue

package cbb;

public class Test_linkQueue {

	public static void main(String[] args) {
		//test1
		linkQueue Q = new linkQueue();
		System.out.println(Q.QueueEmpty());
		System.out.println(Q.toString());
		//test2
		Q.EnQueue(1);
		Q.EnQueue(2);
		Q.EnQueue(3);
		System.out.println(Q.QueueEmpty());
		System.out.println(Q.toString());
		//test3
		Q.DeQueue();
		System.out.println(Q.toString());
	}

}