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

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

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

대기열 표현

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

스택에서와 마찬가지로 대기열은 배열, 연결 목록, 포인터 및 구조를 사용하여 구현할 수도 있습니다. 단순성을 위해 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;
}

대기열에 넣기 작업

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

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

  • 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 프로그래밍 언어로 된 전체 큐 프로그램을 보려면 여기 를 클릭하십시오 .