Thực hiện một hàng đợi đơn giản sử dụng mảng

Question

Tôi không biết nhiều về mảng và hàng đợi và ngăn xếp. Tôi biết cách thực hiện một hàng đợi đơn giản.

#include <iostream> 
#include <queue> 

using namespace std; 

void main() 
{ 
    queue<char> queue1; 
    queue1.push('a'); 
    queue1.push('b'); 
    queue1.push('c'); 
    queue1.push('d'); 

    while(!queue1.empty()) 
    { 
     cout << queue1.front(); 
     queue1.pop(); 
     cout << endl; 
    } 

    system("pause"); 
} 

Làm thế nào tôi có thể thực hiện một hàng đợi đơn giản sử dụng một mảng?

Answer 1

Nếu hàng đợi của bạn được dựa trên một mảng, sau đó vì lợi ích của hiệu quả, tôi sẽ khuyên bạn nên tạo một giáp hoặc hàng đợi "tròn", trong đó tối đa kích thước của hàng đợi là cố định, và về cơ bản bạn có một cái đầu và đuôi con trỏ điểm đó đến vị trí "đầu tiên" và "cuối cùng" trong mảng của hàng đợi và khi đuôi trỏ (hoặc giá trị chỉ mục) di chuyển đến vị trí "quá khứ" ở cuối mảng, nó thực sự di chuyển trở lại phần đầu của mảng. Một hàng đợi vô biên dựa trên một mảng sẽ là khủng khiếp không hiệu quả, như bạn sẽ cần phải tiếp tục phân bổ lại bộ nhớ mỗi khi bạn lấp đầy tối đa kích thước của mảng, và/hoặc cố các yếu tố để tái shuffle xuống mảng khi bạn loại bỏ đầu tiên phần tử của hàng đợi.

Sử dụng không thể thiếu loại chỉ số mảng cho head và tail chứ không phải là loại con trỏ thực tế, cùng với một bộ đếm để xác định tổng số các mặt hàng trong hàng đợi của bạn, enqueue của bạn và chức năng dequeue có thể nhìn đơn giản như:

template<typename T> 
bool queue<T>::enqueue(const T& item) 
{ 
    if (count == array_size) 
     return false; 

    array[tail] = item; 

    tail = (tail + 1) % array_size; 
    count++; 

    return true; 
} 

template<typename T> 
bool queue<T>::dequeue(T& item) 
{ 
    if (!count) 
     return false; 

    item = array[head]; 

    head = (head + 1) % array_size; 
    count--; 

    return true; 
} 

bạn có thể mở rộng khái niệm này để bất cứ điều gì các chức năng khác mà bạn muốn, ví dụ, nếu bạn muốn có một chức năng riêng biệt như STL sử dụng để truy cập vào phần đầu của hàng đợi và thực sự "loại bỏ" một phần tử từ hàng đợi.

Answer 2

LƯU Ý: Trong khi mô phỏng một mảng (tuyến tính lưu trữ dữ liệu) như là một lưu trữ dữ liệu hình tròn và duy trì các thuộc tính của Queue, một tế bào sẽ luôn luôn được sử dụng. Do đó, dung lượng tối đa của mảng sẽ là 5 cho mảng có 6 ô. Mã C++ dưới đây là tự giải thích. Ngoài ra, hãy xem The Linked List Based Implementation của Hàng đợi.

/*Implementation of queue with basic operation using arrays */ 

#include<iostream>   
using namespace std;   
#define MAX 6    //to accomodate a maximum of 05 elements as 1 cell pointed by tail will always be vacant 

void ENQUE(int key);  // ~insertion 
int DEQUEUE();    // ~deletion 
void TRAVERSE(); 
bool isEmpty(); 
bool isFull(); 

int Q[MAX], head=0, tail=0; /* Note: head is the side facing cashier and new person joins the queue at tail. So, from cashier point of view tail~rear and head~front. 
           Q -> [h ][][][][][][][][][][t] 
           Q -> [h,t][][][][][][][][][][] : initial configuration*/ 



int main(){ 
    int choice,val,i; 
    char ch='y'; 

    do{ 
     cout<<"1. For Enqueue \n"; 
     cout<<"2. For Dequeue \n"; 
     cout<<"3. For Traverse \nYour Option : "; 
     cin>>choice; 

     switch(choice) 
     { 
      case 1 :  // insertion 
       if(isFull()){ 
        cout<<"\nQueue Full !!!\n"; 
        break; 
       } 
       cin>>val; 
       ENQUE(val); 
       TRAVERSE(); 
       break; 

      case 2 :  //deletion 
       if(isEmpty()){ 
        cout<<"\nQueue Empty !!!\n"; 
        break; 
       } 
       cout<<"\nDeleted element from Queue : "<<DEQUEUE()<<endl; 
       TRAVERSE(); 
       break; 

      case 3 :  //traversal 
       if(isEmpty()){ 
        cout<<"\nQueue Empty !!!\n"; 
        break; 
       } 
       TRAVERSE(); 
       break; 

      default : 
       cout<<"Please choose 1/2/3 !!! \n"; 
     } 
     cout<<"\nDo you want to continue(y/n):"; 
     cin>>ch; 

    }while(ch=='y'||ch=='Y'); //end of do loop 

    return 0; 
} 

void ENQUE(int x){ 

    Q[tail] = x; 
    tail =(tail+1)%MAX ;  //OR tail = (tail==MAX) ? 0 : tail+1 ; */ 
} 

int DEQUEUE(){ 

    int temp =Q[head]; 
    head =(head+1)%MAX ;  //OR head = (head==MAX) ? 0 : head+1 ; */ 
    return temp; 
} 

void TRAVERSE(){ 
    int i;        //simple case: Q -> [ ][ ][h7][8][9][5t][ ][ ][ ][ ][ ] 
    for(i=head; i!=tail; i=(i+1)% MAX) //complex case: Q -> [16][t][ ][ ][ ][h5][11][12][13][14][15] 
     cout<<Q[i]<<" "; 
    cout<<endl; 
} 

bool isEmpty(){ 
    if(head == tail) 
     return true; 
    else 
     return false; 
} 

bool isFull(){ 
    if((tail == MAX-1 && head == 0) || (head == tail + 1) ) 
     return true; 
    else 
     return false; 
} 

Một đoạn video hướng dẫn của tương tự có thể được nhìn thấy ở đây: Data structures: Array implementation of Queue