데이터 구조 - 배열 시 뮬 레이 션 링 대기 열

본 고 는 이전 박문 에 이 어 계속 확장 되 었 으 며, 이번 에는 배열 시 뮬 레이 션 링 대기 열 을 이야기 하 였 다.https://blog.csdn.net/Hello_ChenLiYan/article/details/107273124
1. 배열 로 대기 열 을 모 의 할 때 재 활용 효 과 를 고려 하여 링 대기 열 로 표시 합 니 다.
2. 배열 시 뮬 레이 션 링 대기 열 에 데이터 방향 을 추가 합 니 다.

대기 열 이 만 료 되 었 는 지 먼저 판단 한다. (rear+1) % maxSize = front

데 이 터 를 대기 열 에 추가 합 니 다. arr[rear]=n

팀 의 꼬리 지침 을 뒤로 옮 기 고 rear 는 모델 링 을 해 야 한다. rear = (rear+1) % maxSize

3. 대기 열 에서 데이터 방향 을 추출 합 니 다.

대기 열 이 비어 있 는 지 먼저 판단 한다. rear == front

front 위치의 값 을 임시 변수 에 저장 합 니 다. int value = arr[front]

팀 의 첫 번 째 지침 을 앞으로 옮 기 고 모형 을 뽑 아야 한다. front = (front+1)%maxSize

임시 변 수 를 되 돌려 줍 니 다. return value

4. 대기 열 유효 데이터 개수 (rear + maxSize - front) % maxSize5. 대기 열의 모든 데 이 터 를 표시 합 니 다.

대기 열 이 비어 있 는 지 먼저 판단 하고 비어 있 으 면 데이터 가 없 음

대기 열의 모든 데 이 터 를 front 로 시작 하여 front + 대기 열의 유효한 데이터 개수 까지 옮 겨 다 니 기

for (int i = front; i < front+size(); i++) {
	System.out.printf("      arr[%d] = %d
",(i % maxSize),arr[(i % maxSize)]);

6. 코드 구현 front: 대기 열 첫 번 째 위치 rear: 대기 열의 마지막 데이터 의 다음 위치

package com.queue;

import java.util.Scanner;

import javax.management.RuntimeErrorException;

public class CircleArrayQueueDemo {

	public static void main(String[] args) {
		CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4);
		char key = ' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		while(loop) {
			System.out.println("s(show):        ");
			System.out.println("a(add):       ");
			System.out.println("g(get):       ");
			System.out.println("h(head):       ");
			System.out.println("e(exit):    ~");
			key = scanner.next().charAt(0);
			switch (key) {
			case 's':
				circleArrayQueue.showQueue();
				break;

			case 'a':
				System.out.println("             ");
				int n = scanner.nextInt();
				circleArrayQueue.addQueue(n);
				break;
			
			case 'g':
				try {
					int res = circleArrayQueue.getQueue();
					System.out.printf("        %d
",res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
			
				break;
				
			case 'h':
				try {
					int res = circleArrayQueue.headQueue();
					System.out.printf("       %d
",res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
				
			case 'e':
				scanner.close();
				loop = false;
				System.out.println("    ~");
				break;
			default:
				break;
			}
		}
		System.out.println("      ~~");
	}
}

class CircleArrayQueue {
	private int maxSize;//     
	private int front ;//  ，        
	private int rear ;//  ，         
	private int[] arr;//  
	
	public CircleArrayQueue (int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
		rear = 0;
		front = 0;
	}
	
	//        
	public boolean isEmpty() {
		return rear == front;
	}
	
	//       
	public boolean isFull() {
	    // rear：       ，            
		return (rear+1) % maxSize == front;
	}
	
	//       
	public void addQueue(int n) {
		if (isFull()) {
			System.out.println("    ，       ~~");
			return ;
		}
		//       
		arr[rear]=n;
		//rear  ，rear：       
		rear = (rear+1) % maxSize;
	}
	
	//       ，   
	public int getQueue() {
		if (isEmpty()) {
			throw new RuntimeErrorException(null,"    ，     ");
		}
		// front            
		int value = arr[front];
		//front   ，   
		front = (front+1)%maxSize;
		//      
		return value;
	}
	
	//       
	public int headQueue() {
		if (isEmpty()) {
			throw new RuntimeErrorException(null,"    ，     ");
		}
		//front         
		return arr[front];
	}
	
	//        
	public void showQueue() {
		if (isEmpty()) {
			System.out.println("    ，    ");
			return;
		}
		for (int i = front; i < front+size(); i++) {
			System.out.printf("      arr[%d] = %d
",(i % maxSize),arr[(i % maxSize)]);
		}
	}
	
	//         
	public int size() {
	    //rear = 1
	    //front = 0
	    //maxSize = 4
		return (rear + maxSize - front) % maxSize;	
	}	
}

7. 배열 시 뮬 레이 션 링 대기 열 은 재 활용 효과 에 달 했 고 데 이 터 를 꺼 낸 후에 대기 열 에 데 이 터 를 추가 할 수 있 으 며 front 와 rear 도 동태 적 으로 변화 할 수 있 습 니 다.