데이터 구조: 대기 열의 개념 과 실현

포함:
대열 의 개념
2. 순서 저장 구조 와 체인 저장 구조의 대기 열의 실현
대열 의 개념
        대기 열 은 표 의 한 끝 에 삽입 하고 표 의 다른 한 끝 에서 삭제 합 니 다.삭 제 된 한 끝 을 팀 머리 나 팀 머리 라 고 하고 삽 입 된 한 끝 을 팀 꼬리 라 고 합 니 다.요 소 를 삽입 하 는 것 을 입 대 또는 입 대 라 고 하고 요 소 를 삭제 하 는 것 을 출 대 라 고 합 니 다.특징: 먼저 시 계 를 낸다.대기 열의 저장 구 조 는 순서 저장 구조 와 체인 저장 구조 로 나 뉜 다. 
2. 순서 저장 구조 와 체인 저장 구조의 대기 열의 실현
순차 저장 구조의 대기 열 구현:
        하나의 배열 과 두 개의 포인터 가 필요 합 니 다 (예 를 들 어 front). rear) 는 배열 을 이용 하여 모든 요 소 를 저장 하고 두 개의 지침 을 이용 하여 각각 팀 의 머리 와 팀 의 꼬리 를 가리 키 며 공간 을 충분히 사용 하기 위해 보통 링 대기 열, 즉 팀 의 머리 와 팀 의 꼬리 를 연결 합 니 다.팀 끝 에 요 소 를 삽입 할 때 rear = (rear + 1)% MaxSize 를 진행 합 니 다.마찬가지 로 팀 에서 요 소 를 삭제 할 때 도 front = (front + 1)% MaxSize; 이때 팀 의 빈 칸 과 팀 이 모두 rear = = front 인 것 을 발견 할 수 있 습 니 다. 팀 의 빈 칸 과 팀 이 꽉 찬 것 을 구별 하기 위해 보통 하나의 요 소 를 적 게 사용 합 니 다. 즉, (rear + 1)% MaxSize = = front 는 가득 찬 것 이 라 고 생각 하고 빈 칸 에 대한 판단 조건 은 변 하지 않 습 니 다. front = rear.
다음은 순차 저장 구조의 대기 열의 간단 한 실현 이다.

public class SelfQueueImpl {
	private static int dataLength = 2;

	public static void main(String[] args) {
		SqQueue sqQueue = new SqQueue();
		
		sqQueue.enQueue(1);
		sqQueue.enQueue(2);
		sqQueue.enQueue(3);
		
		System.out.println(sqQueue.deQueue());
		System.out.println(sqQueue.deQueue());
		System.out.println(sqQueue.deQueue());
	}
	
	static class SqQueue{
		
		private Object data[] = new Object[dataLength];
		private int front;
		private int rear;
		//  
		public void enQueue(Object element){
			if(queueIsFull()){
				System.out.println("Queue is full, enQueue failed!.");
			} else {
				data[rear] = element;
				rear ++;
				resetRear(rear);
				System.out.println("enQueue success. data[" + (rear-1) + "] = " + data[rear-1] );
			}
		}

		private void resetRear(int rear) {
			if(rear == dataLength){
				this.rear = 0;
			}
		}
		
		private boolean queueIsFull() {
			return (rear + 1) % dataLength == front;
		}
                //  
		public Object deQueue(){
			if(queueIsEmpty()){
				System.out.println("Queue is empty, deQueue failed!.");
				return null;
			} else {
				Object object = data[front];
				front ++;
				resetFront(front);
				return object;
			}
		}

		private void resetFront(int front) {
			if(front == dataLength){
				this.front = 0;
			}
		}

		private boolean queueIsEmpty() {
			return rear == front;
		}
		
	}
}

출력:

enQueue success. data[0] = 1
Queue is full, enQueue failed!.
Queue is full, enQueue failed!.
1
Queue is empty, deQueue failed!.
null
Queue is empty, deQueue failed!.
null

링크 저장 구조의 대기 열 구현:
        링크 저장 구조 에 대해 순환 링크 의 개념 도 없고 팀 이 꽉 찬 개념 도 없다.팀 이 비어 있 는 것 에 대해 서 는 프런트 와 rear 를 유지 하기 때문에 그 중 하나 가 비어 있 는 지 판단 하면 됩 니 다.
다음은 체인 저장 구조의 간단 한 실현 이다.

public class SelfQueueImpl_List {

	public static void main(String[] args) {
		SqQueue sqQueue = new SqQueue();
		
		sqQueue.enQueue(1);
		sqQueue.enQueue(2);
		sqQueue.enQueue(3);
		
		System.out.println(sqQueue.deQueue());
		System.out.println(sqQueue.deQueue());
		System.out.println(sqQueue.deQueue());
		System.out.println(sqQueue.deQueue());
		
	}
	
	static class SqQueue{
		
		private QNode front;
		private QNode rear;
		
		//  
		public void enQueue(Object object){
			
			if(QueueIsEmpty()){
				insert1(object);
			} else{
				insert2(object);
			}
			System.out.print("enQueue success. Queue is ");
			printQueue();
		}

		private void printQueue() {
			QNode flag = this.front;
			while(flag != null ){
				System.out.print(" " + flag.getObject());
				flag = flag.getNext();
			}
			System.out.print("
");
		}

		private void insert1(Object object) {
			QNode qNode = new QNode(object);
			this.front = qNode;
			this.rear = qNode;
		}

		private void insert2(Object object) {
			rear.setNext(new QNode(object));
			rear = rear.getNext();
		}

		private boolean QueueIsEmpty() {
			return this.front == null;
		}
		
		//  
		public Object deQueue(){
			if(QueueIsEmpty()){
				System.out.println("Queue is empty, deQueue failed!.");
				return null;
			} else {
				Object object = front.getObject();
				front = front.next;
				return object;
			}
		}
	}

	static class QNode{
		private Object object;
		private QNode next;
		
		public QNode(Object object){
			this.object = object;
		}
		
		public Object getObject(){
			return this.object;
		}
		
		public QNode getNext(){
			return this.next;
		}
		public void setNext(QNode qNode){
			this.next = qNode;
		}
	}
}

출력:

enQueue success. Queue is  1
enQueue success. Queue is  1 2
enQueue success. Queue is  1 2 3
1
2
3
Queue is empty, deQueue failed!.
null

다음 편 에 서 는 자바 의 대기 열 시스템 구 조 를 소개 합 니 다.
참고: 자바 큐 에서 remove / poll, add / offer, element / peek 차이