데이터 구조 및 알고리즘-대기열

큐는 스택과 다소 유사한 추상 데이터 구조입니다. 스택과 달리 대기열은 양쪽 끝에서 열려 있습니다. 한쪽 끝은 항상 데이터를 삽입 (대기열)하는 데 사용되고 다른 쪽 끝은 데이터를 제거 (대기열에서 빼기)하는 데 사용됩니다. 대기열은 선입 선출 방식을 따릅니다. 즉, 먼저 저장된 데이터 항목이 먼저 액세스됩니다.

대기열의 실제 예는 차량이 먼저 진입하고 먼저 나가는 단일 차선 일방 통행 도로 일 수 있습니다. 더 많은 실제 사례는 매표소와 버스 정류장의 대기열로 볼 수 있습니다.

대기열 표현

이제 대기열에서 이해했듯이 서로 다른 이유로 양쪽 끝에 액세스합니다. 아래에 주어진 다음 다이어그램은 큐 표현을 데이터 구조로 설명하려고 시도합니다.

스택에서와 마찬가지로 대기열은 배열, 연결 목록, 포인터 및 구조를 사용하여 구현할 수도 있습니다. 단순성을 위해 1 차원 배열을 사용하여 큐를 구현합니다.

기본 작동

대기열 작업에는 대기열을 초기화하거나 정의하고이를 활용 한 다음 메모리에서 완전히 삭제하는 작업이 포함될 수 있습니다. 여기서 우리는 대기열과 관련된 기본 작업을 이해하려고 노력할 것입니다.

enqueue() − 대기열에 항목을 추가 (저장)합니다.
dequeue() − 대기열에서 항목을 제거 (접근)합니다.

위에서 언급 한 대기열 작업을 효율적으로 수행하려면 더 많은 기능이 필요합니다. 이것들은-

peek() − 큐를 제거하지 않고 큐의 맨 앞에있는 요소를 가져옵니다.
isfull() − 대기열이 가득 찼는 지 확인합니다.
isempty() − 대기열이 비어 있는지 확인합니다.

대기열에서 우리는 항상 다음이 가리키는 데이터를 대기열에서 빼거나 액세스합니다. front 포인터를 사용하고 대기열에 데이터를 넣거나 저장하는 동안 도움을받습니다. rear 바늘.

먼저 대기열의 지원 기능에 대해 알아 보겠습니다.

몰래 엿보다()

이 기능은 front대기열의. peek () 함수의 알고리즘은 다음과 같습니다.

Algorithm

begin procedure peek
   return queue[front]
end procedure

C 프로그래밍 언어로 peek () 함수 구현-

Example

int peek() {
   return queue[front];
}

가득()

큐를 구현하기 위해 단일 차원 배열을 사용하고 있으므로 후면 포인터가 MAXSIZE에 도달하는지 확인하여 큐가 가득 찼는 지 확인합니다. 순환 연결 목록에서 대기열을 유지하는 경우 알고리즘이 다릅니다. isfull () 함수의 알고리즘-

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

C 프로그래밍 언어로 isfull () 함수 구현-

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

비었다()

isempty () 함수의 알고리즘-

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

값이 front MIN 또는 0보다 작 으면 큐가 아직 초기화되지 않았으므로 비어 있음을 나타냅니다.

다음은 C 프로그래밍 코드입니다.

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

대기열에 넣기 작업

큐는 두 개의 데이터 포인터를 유지합니다. front 과 rear. 따라서 그 작업은 스택보다 구현하기가 비교적 어렵습니다.

데이터를 큐에 넣 (삽입)하려면 다음 단계를 수행해야합니다.

Step 1 − 대기열이 가득 찼는 지 확인하십시오.
Step 2 − 대기열이 가득 차면 오버플로 오류가 발생하고 종료됩니다.
Step 3 − 대기열이 꽉 차 있지 않으면 rear 다음 빈 공간을 가리키는 포인터.
Step 4 − 뒤쪽이 가리키는 대기열 위치에 데이터 요소를 추가합니다.
Step 5 − 성공을 반환합니다.

때로는 예기치 않은 상황을 처리하기 위해 대기열이 초기화되었는지 여부도 확인합니다.

대기열에 넣기 작업을위한 알고리즘

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

C 프로그래밍 언어로 enqueue () 구현-

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

대기열에서 빼기 작업

대기열에서 데이터에 액세스하는 것은 두 가지 작업의 프로세스입니다. front액세스 후 데이터를 가리키고 제거합니다. 수행하기 위해 다음 단계가 수행됩니다.dequeue 작동-

Step 1 − 대기열이 비어 있는지 확인하십시오.
Step 2 − 대기열이 비어 있으면 언더 플로 오류가 발생하고 종료됩니다.
Step 3 − 대기열이 비어 있지 않은 경우 데이터에 액세스합니다. front 가리키고 있습니다.
Step 4 − 증분 front 사용 가능한 다음 데이터 요소를 가리키는 포인터.
Step 5 − 성공을 반환합니다.

대기열에서 빼기 작업을위한 알고리즘

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

C 프로그래밍 언어로 dequeue () 구현-

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

C 프로그래밍 언어로 된 전체 큐 프로그램을 보려면 여기 를 클릭하십시오 .