Chain Queue

Recently, I was in the study queue and wrote this study note

Basic concept of queue

Stack is first in first out - and queue is first in first out


Here is a queue:
<1 , 2 , 3 , 4 , 5 , 6>
Usually we have two operations on queues

  1. Team out
  2. Join the team
Team out

For < 1, 2, 3, 4, 5, 6 > to leave the team
The outgoing element is 1, then 2, then 3

Join the team

Yes < 1, 2, 3, 4, 5, 6 > join the team
Queue element 7 to <1, 2, 3, 4, 5, 6, 7>

  • It can be seen here that the queue is read from the head and delete, and the tail is added and inserted
  • It's like we're in line to buy tickets. We always buy tickets in front of us. We leave behind and join the people who want to buy tickets
  • // Define a class
    #ifndef QUEUE_H
    #define QUEUE_H
    // Define a class that contains the queue data structure and functions that operate on the queue
    class Queue
    {
        private:// Queue data
            struct ue{// Queue structure
                int num = 0;// data
                struct ue *next;// Tail pointer
            };
            struct ue *head, *last;// Head pointer and tail pointer
        public:
            Queue();
            ~Queue(); 
            // Show all information 
            void show();
            // Find if a value exists
            bool contains(int num); 
            // Access the value of the i th element 
            int indexOf(int i);
            // Get the number of current elements
            int size();  
            // Entry element to end
            bool push(int num);
            // pop out - but not deleted 
            int pop();
            // popFrist - dequeue and delete
            int popFrist(); 
        protected:
    };
    #endif
    //Queue class implementation function
    #include "Queue.h"
    #include <iostream>
    using namespace std;
    Queue::Queue()
    {
        head = nullptr;
    }
    // Access the value of the i th element 
    int Queue::indexOf(int i){
        struct ue *p = this->head; 
        int x = 0;
        while(p && x != i){
            p = p->next; 
            x++;
        } 
        if(p)
            return p->num;
        return INT_MIN; 
    } 
    // Find if a value exists
    bool Queue::contains(int num){
        struct ue *p = this->head; 
        while(p && p->num != num){
            p = p->next; 
        } 
        if(p)
            return true;
        return false; 
    } 
    // Get the number of current elements
    int Queue::size(){
        int i = 0;
        struct ue *p;
        p = this->head;
        while(p){
            i++;
            p = p->next; 
        }
        return i;
    } 
    // Do not delete elements when leaving the team 
    int Queue::pop(){
        return this->head->num; 
    } 
    // Queue out and delete elements
    int Queue::popFrist(){
        struct ue *p; 
        int num = this->head->num;
        p = this->head;
        this->head = this->head->next;
        delete p; 
        return num; 
    } 
    // Join the team 
    bool Queue::push(int num){
        struct ue *p;
        p = new struct ue;
        p->num = num;
        p->next = nullptr;
        if( this->head == nullptr ){
            this->head = p;
        } else {
            this->last->next = p;
        }
        this->last = p;
    } 
    // Show all elements 
    void Queue::show(){
        struct ue *temp = this->head;
        while(temp){
            cout << temp->num << ", ";
            temp = temp->next;
        }
        cout << endl; 
    }
    // Release space 
    Queue::~Queue()
    {
        struct ue *p = this->head;
        while(p){
            this->head = p;
            p = p->next;
            delete head;
        }
    }
    // Test the written queue class here
    #include <iostream>
    #include "Queue.h" 
    using namespace std; 
    int main(int argc, char** argv) {
        Queue queue;
        queue.push(10);// Join the team
        queue.push(20);
        queue.push(101);
        queue.show();
        cout << "There are in the current queue: " << queue.size() << endl; 
        cout << "Team leader element is: " << queue.pop() << endl; 
        cout << "Number of elements in the current queue: " << queue.size() << endl; 
        queue.show();
        cout << "Team leader element is: (Show and delete): " << queue.popFrist() << endl; 
        cout << "Number of elements in the current queue: " << queue.size() << endl; 
        queue.show();
        cout << "Whether the element is included in the queue: " << queue.contains(20) << endl; 
        cout << "Display the element value of the corresponding subscript: " <<queue.indexOf(1) << endl; 
    
        return 0;
    }

    Posted on Sun, 05 Apr 2020 09:35:24 -0700 by nickman013