queue data structure c with illustration
그림과 함께 C ++의 대기열에 대한 간략한 소개.
큐는 스택과 같은 기본 데이터 구조입니다. LIFO 방식을 사용하는 스택과 달리 대기열은 FIFO (선입 선출) 방식을 사용합니다. 이 방법을 사용하면 대기열에 추가되는 첫 번째 항목이 대기열에서 제거되는 첫 번째 항목입니다. Stack과 마찬가지로 큐도 선형 데이터 구조입니다.
Windows 7 용 암호 크래킹 도구
실제 비유에서 우리는 승객이 줄이나 줄에서 버스를 기다리는 버스 줄을 상상할 수 있습니다. 선의 첫 번째 승객은 먼저 버스에 탔습니다.
=> 여기에서 인기있는 C ++ 교육 시리즈를 읽어보십시오.
학습 내용 :
C ++의 대기열
소프트웨어 측면에서 큐는 아래와 같이 요소의 집합 또는 컬렉션으로 볼 수 있습니다. 요소는 선형으로 배열됩니다.
우리는 대기열의 '앞'과 '뒤'의 두 끝을 가지고 있습니다. 큐가 비어 있으면 두 포인터가 모두 -1로 설정됩니다.
'후면'끝 포인터는 요소가 대기열에 삽입되는 위치입니다. 큐에 요소를 추가 / 삽입하는 작업을 '인큐'라고합니다.
'앞'끝 포인터는 요소가 큐에서 제거되는 위치입니다. 큐에서 요소를 제거 / 삭제하는 작업을 '대기열 제거'라고합니다.
뒤쪽 포인터 값이 크기 1이면 대기열이 가득 찼습니다. 앞면이 널이면 큐가 비어 있습니다.
기본 작동
큐 데이터 구조에는 다음 작업이 포함됩니다.
- EnQueue : 대기열에 항목을 추가합니다. 대기열에 항목을 추가하는 작업은 항상 대기열의 뒤쪽에서 수행됩니다.
- DeQueue : 대기열에서 항목을 제거합니다. 항목은 항상 대기열의 맨 앞에서 제거되거나 대기열에서 제거됩니다.
- 비었다: 큐가 비어 있는지 확인합니다.
- 가득: 대기열이 가득 찼는 지 확인합니다.
- 몰래 엿보다: 큐를 제거하지 않고 큐의 맨 앞에있는 요소를 가져옵니다.
대기열에 넣기
이 프로세스에서는 다음 단계가 수행됩니다.
- 대기열이 가득 찼는 지 확인하십시오.
- 가득 찬 경우 오버플로 오류를 생성하고 종료합니다.
- 그렇지 않으면 '후면'을 증가시킵니다.
- '후면'이 가리키는 위치에 요소를 추가합니다.
- 성공을 반환하십시오.
대기열에서 빼기
대기열에서 빼기 작업은 다음 단계로 구성됩니다.
- 대기열이 비어 있는지 확인하십시오.
- 비어 있으면 언더 플로 오류를 표시하고 종료합니다.
- 그렇지 않으면 액세스 요소는 '전면'으로 표시됩니다.
- 액세스 할 수있는 다음 데이터를 가리 키도록 '앞면'을 늘립니다.
- 성공을 반환하십시오.
다음으로 대기열의 삽입 및 삭제 작업에 대한 자세한 그림을 볼 수 있습니다.
삽화
이것은 빈 대기열이므로 rear 및 empty를 -1로 설정했습니다.
다음으로 대기열에 1을 추가하면 뒤쪽 포인터가 한 위치 앞으로 이동합니다.
다음 그림에서는 뒤쪽 포인터를 다른 증분만큼 앞으로 이동하여 요소 2를 대기열에 추가합니다.
다음 그림에서 요소 3을 추가하고 뒤쪽 포인터를 1만큼 이동합니다.
이 시점에서 후면 포인터는 값 2를 가지며 전면 포인터는 0에 있습니다.일위치.
다음으로 앞쪽 포인터가 가리키는 요소를 삭제합니다. 앞쪽 포인터가 0에 있으므로 삭제되는 요소는 1입니다.
따라서 대기열에 입력 된 첫 번째 요소, 즉 1이 대기열에서 제거 된 첫 번째 요소가됩니다. 결과적으로 첫 번째 대기열에서 빼기 후에 앞쪽 포인터는 이제 다음 위치 인 1 인 t0 앞으로 이동합니다.
대기열에 대한 어레이 구현
C ++를 사용하여 큐 데이터 구조를 구현해 보겠습니다.
#include #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue(MAX_SIZE), front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< 'Queue is full!!'; } else { if(front == -1) front = 0; rear++; myqueue(rear) = value; cout << value << ' '; } } int deQueue(){ int value; if(isEmpty()){ cout << 'Queue is empty!!' <= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl < ' << value << ' from myqueue'; return(value); } } /* Function to display elements of Queue */ void displayQueue() { int i; if(isEmpty()) { cout << endl << 'Queue is Empty!!' << endl; } else { cout << endl << 'Front = ' << front; cout << endl << 'Queue elements : '; for(i=front; i<=rear; i++) cout << myqueue(i) << ' '; cout << endl << 'Rear = ' << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<'Queue created:'< queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>removes 10 myq.deQueue(); //queue after dequeue myq.displayQueue(); return 0; }산출:
대기열이 비어 있습니다 !!
생성 된 대기열 :
10 20 30 40 50
대기열이 가득 찼습니다 !!
전면 = 0
대기열 요소 : 10 20 30 40 50
후면 = 4
myqueue에서 삭제 => 10
전면 = 1
대기열 요소 : 20 30 40 50
후면 = 4
위의 구현은 배열로 표현 된 큐를 보여줍니다. 배열의 max_size를 지정합니다. 또한 대기열에 넣기 및 대기열에서 빼기 작업과 isFull 및 isEmpty 작업을 정의합니다.
다음은 큐 데이터 구조의 Java 구현입니다.
// A class representing a queue class Queue { int front, rear, size; int max_size; int myqueue(); public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int(this.max_size); } //if size = max_size , queue is full boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // size = 0, queue is empty boolean isEmpty(Queue queue) { return (queue.size == 0); } // enqueue - add an element to the queue void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue(this.rear) = item; this.size = this.size + 1; System.out.print(item + ' ' ); } // dequeue - remove an elment from the queue int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue(this.front); this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // move to front of the queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.front); } // move to the rear of the queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.rear); } } // main class class Main { public static void main(String() args) { Queue queue = new Queue(1000); System.out.println('Queue created as:'); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println('
Element ' + queue.dequeue() + ' dequeued from queue
'); System.out.println('Front item is ' + queue.front()); System.out.println('Rear item is ' + queue.rear()); } } 산출:
다음으로 생성 된 대기열 :
10 20 30 40
대기열에서 요소 10이 제거되었습니다.
전면 항목은 20입니다.
후면 항목은 40입니다.
위의 구현은 C ++ 구현과 유사합니다.
다음으로 연결 목록을 사용하여 C ++로 큐를 구현해 보겠습니다.
대기열에 대한 연결 목록 구현 :
#include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<'Queue is empty!!'next; cout<<'Element deleted from queue is : ' 산출:
생성 된 대기열 :
10 20 30 40 50
대기열에서 삭제 된 요소 : 10
삭제 후 대기열 :
20 30 40 50
외장 하드 드라이브 용 무료 백업 소프트웨어
스택 대. 열
스택과 큐는 데이터를 저장하는 데 사용할 수있는 보조 데이터 구조입니다. 배열 및 연결 목록과 같은 기본 데이터 구조를 사용하여 프로그래밍 할 수 있습니다. 두 데이터 구조를 자세히 논의 했으므로 이제이 두 데이터 구조의 주요 차이점에 대해 논의 할 차례입니다.
스택 대기열 LIFO (Last in, First Out) 접근 방식을 사용합니다. FIFO (선입 선출) 방식을 사용합니다. 항목은 스택의 '상단'이라는 한쪽 끝에서만 추가되거나 삭제됩니다. 항목은 대기열의 '뒤'끝에서 추가되고 대기열의 '앞'에서 제거됩니다. 스택의 기본 작업은 '푸시'및 '팝'입니다. 대기열에 대한 기본 작업은 '대기열에 넣기'및 '대기열 제거'입니다. 스택의 맨 위에 액세스 할 수있는 포인터를 하나만 유지하여 스택에서 모든 작업을 수행 할 수 있습니다. 대기열에서 우리는 두 개의 포인터를 유지해야합니다. 하나는 대기열의 앞쪽에 액세스하고 다른 하나는 대기열의 뒤쪽에 액세스하는 것입니다. 스택은 주로 재귀 문제를 해결하는 데 사용됩니다. 대기열은 주문 처리와 관련된 문제를 해결하는 데 사용됩니다.
대기열의 응용
아래에서 큐 데이터 구조의 다양한 애플리케이션에 대해 설명하겠습니다.
- 큐 데이터 구조는 다양한 CPU 및 디스크 스케줄링에 사용됩니다. 여기에는 동시에 CPU 또는 디스크가 필요한 여러 작업이 있습니다. CPU 또는 디스크 시간은 대기열을 사용하는 각 작업에 대해 예약됩니다.
- 대기열은 인쇄 작업 수가 대기열에 배치되는 인쇄 스풀링에도 사용할 수 있습니다.
- 실시간 시스템에서 인터럽트 처리는 큐 데이터 구조를 사용하여 수행됩니다. 인터럽트는 도착한 순서대로 처리됩니다.
- 다음 레벨로 이동하기 전에 트리의 인접 노드를 순회하는 폭 우선 검색은 구현을 위해 큐를 사용합니다.
- 콜센터 전화 시스템은 서비스 담당자가 응답 할 때까지 대기열을 사용하여 통화를 보류합니다.
일반적으로 큐 데이터 구조는 리소스 또는 항목이 도착한 순서대로 서비스되어야 할 때마다 사용됩니다 (예 : 선입 선출).
결론
큐는 스케줄링이 필요한 리소스에서 주로 사용되는 FIFO (선입 선출) 데이터 구조입니다. 두 개의 끝에는 앞뒤에 두 개의 포인터가 있으며 이들은 각각 요소를 삽입하고 큐에서 요소를 제거하는 데 사용됩니다.
다음 자습서에서는 우선 순위 대기열 및 순환 대기열과 같은 대기열 확장에 대해 알아 봅니다.
=> 전체 C ++ 자습서 목록을 탐색하려면 여기를 참조하십시오.
추천 도서