Рубрики

Очередь | Набор 1 (Введение и реализация массива)

Подобно стеку , очередь представляет собой линейную структуру, которая следует определенному порядку выполнения операций. Порядок Р IRST Н Ф О IRST ут (FIFO). Хорошим примером очереди является любая очередь потребителей для ресурса, где первым обслужен потребитель, который пришел первым.
Разница между стеками и очередями заключается в удалении. В стеке мы удаляем элемент, который был добавлен последним; в очереди удаляем элемент, наименее добавленный за последнее время.

Операции в очереди:
В основном следующие четыре основные операции выполняются в очереди:

Постановка в очередь: добавляет элемент в очередь. Если очередь заполнена, это называется условием переполнения.
Dequeue: удаляет элемент из очереди. Элементы появляются в том же порядке, в котором они помещены. Если очередь пуста, то говорят, что это условие Underflow.
Front: получить передний элемент из очереди.
Сзади: получить последний элемент из очереди.

Приложения очереди:
Очередь используется , когда вещи не должны быть обработаны немедленно, но должны быть обработаны в F IRST I п F IRST O ут порядка , как поиск в ширину . Это свойство очереди делает его также полезным в следующих сценариях.

1) Когда ресурс распределяется между несколькими потребителями. Примеры включают планирование ЦП, планирование диска.
2) Когда данные передаются асинхронно (данные не обязательно принимаются с той же скоростью, что и отправленные) между двумя процессами. Примеры включают буферы ввода-вывода, каналы, файловый ввод-вывод и т. Д.

Смотрите это для более подробного применения очереди и стека.

Реализация массива очереди
Для реализации очереди нам нужно отслеживать два индекса: передний и задний. Мы ставим в очередь предмет сзади и снимаем предмет спереди. Если мы просто увеличиваем передний и задний индексы, то могут возникнуть проблемы, передний может достигнуть конца массива. Решение этой проблемы заключается в круговом увеличении передней и задней части (подробности см. В этом разделе)

C ++

// Программа CPP для реализации массива очереди
#include <bits/stdc++.h>

using namespace std;

  
// Структура для представления очереди

class Queue 

    public:

    int front, rear, size; 

    unsigned capacity; 

    int* array; 

}; 

  
// функция для создания очереди заданной емкости.
// Инициализирует размер очереди как 0
Queue* createQueue(unsigned capacity) 

    Queue* queue = new Queue();

    queue->capacity = capacity; 

    queue->front = queue->size = 0; 

    queue->rear = capacity - 1; // Это важно, см. Очередь

    queue->array = new int[(queue->capacity * sizeof(int))]; 

    return queue; 

  
// очередь заполнена при размере
// становится равным емкости

int isFull(Queue* queue) 

{ return (queue->size == queue->capacity); } 

  
// очередь пуста при размере 0

int isEmpty(Queue* queue) 

{ return (queue->size == 0); } 

  
// Функция для добавления элемента в очередь.
// Он меняет тыл и размер

void enqueue(Queue* queue, int item) 

    if (isFull(queue)) 

        return

    queue->rear = (queue->rear + 1) % queue->capacity; 

    queue->array[queue->rear] = item; 

    queue->size = queue->size + 1; 

    cout << item << " enqueued to queue\n"

  
// Функция для удаления элемента из очереди.
// Изменяет фронт и размер

int dequeue(Queue* queue) 

    if (isEmpty(queue)) 

        return INT_MIN; 

    int item = queue->array[queue->front]; 

    queue->front = (queue->front + 1) % queue->capacity; 

    queue->size = queue->size - 1; 

    return item; 

  
// Функция для получения фронта очереди

int front(Queue* queue) 

    if (isEmpty(queue)) 

        return INT_MIN; 

    return queue->array[queue->front]; 

  
// Функция для возврата в очередь

int rear(Queue* queue) 

    if (isEmpty(queue)) 

        return INT_MIN; 

    return queue->array[queue->rear]; 

  
// Код драйвера

int main() 

    Queue* queue = createQueue(1000); 

  

    enqueue(queue, 10); 

    enqueue(queue, 20); 

    enqueue(queue, 30); 

    enqueue(queue, 40); 

  

    cout<<dequeue(queue)<<" dequeued from queue\n"

  

    cout << "Front item is " << front(queue) << endl; 

    cout << "Rear item is " << rear(queue) << endl; 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для реализации массива очереди
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

  
// Структура для представления очереди

struct Queue

{

    int front, rear, size;

    unsigned capacity;

    int* array;

};

  
// функция для создания очереди заданной емкости.
// Инициализирует размер очереди как 0

struct Queue* createQueue(unsigned capacity)

{

    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));

    queue->capacity = capacity;

    queue->front = queue->size = 0; 

    queue->rear = capacity - 1;  // Это важно, см. Очередь

    queue->array = (int*) malloc(queue->capacity * sizeof(int));

    return queue;

}

  
// очередь заполнена, когда размер становится равным емкости

int isFull(struct Queue* queue)

return (queue->size == queue->capacity);  }

  
// очередь пуста при размере 0

int isEmpty(struct Queue* queue)

return (queue->size == 0); }

  
// Функция для добавления элемента в очередь.
// Он меняет тыл и размер

void enqueue(struct Queue* queue, int item)

{

    if (isFull(queue))

        return;

    queue->rear = (queue->rear + 1)%queue->capacity;

    queue->array[queue->rear] = item;

    queue->size = queue->size + 1;

    printf("%d enqueued to queue\n", item);

}

  
// Функция для удаления элемента из очереди.
// Изменяет фронт и размер

int dequeue(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    int item = queue->array[queue->front];

    queue->front = (queue->front + 1)%queue->capacity;

    queue->size = queue->size - 1;

    return item;

}

  
// Функция для получения фронта очереди

int front(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    return queue->array[queue->front];

}

  
// Функция для возврата в очередь

int rear(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    return queue->array[queue->rear];

}

  
// Программа драйвера для проверки вышеуказанных функций ./

int main()

{

    struct Queue* queue = createQueue(1000);

  

    enqueue(queue, 10);

    enqueue(queue, 20);

    enqueue(queue, 30);

    enqueue(queue, 40);

  

    printf("%d dequeued from queue\n\n", dequeue(queue));

  

    printf("Front item is %d\n", front(queue));

    printf("Rear item is %d\n", rear(queue));

  

    return 0;

}

Джава

// Java-программа для реализации массива очереди

   
// Класс для представления очереди

class Queue

{

    int front, rear, size;

    int  capacity;

    int array[];

       

    public Queue(int capacity) {

         this.capacity = capacity;

         front = this.size = 0

         rear = capacity - 1;

         array = new int[this.capacity];

            

    }

       

    // очередь заполнена, когда размер становится равным

    // емкость

    boolean isFull(Queue queue)

    return (queue.size == queue.capacity);

    }

       

    // очередь пуста при размере 0

    boolean isEmpty(Queue queue)

    return (queue.size == 0); }

       

    // Метод добавления элемента в очередь.

    // Он меняет тыл и размер

    void enqueue( int item)

    {

        if (isFull(this))

            return;

        this.rear = (this.rear + 1)%this.capacity;

        this.array[this.rear] = item;

        this.size = this.size + 1;

        System.out.println(item+ " enqueued to queue");

    }

       

    // Метод удаления элемента из очереди.

    // Изменяет фронт и размер

    int dequeue()

    {

        if (isEmpty(this))

            return Integer.MIN_VALUE;

           

        int item = this.array[this.front];

        this.front = (this.front + 1)%this.capacity;

        this.size = this.size - 1;

        return item;

    }

       

    // Метод получения фронта очереди

    int front()

    {

        if (isEmpty(this))

            return Integer.MIN_VALUE;

           

        return this.array[this.front];

    }

        

    // Способ получить заднюю очередь

    int rear()

    {

        if (isEmpty(this))

            return Integer.MIN_VALUE;

           

        return this.array[this.rear];

    }

}

   

    
// Класс водителя

public class Test

{

    public static void main(String[] args) 

    {

        Queue queue = new Queue(1000);

            

        queue.enqueue(10);

        queue.enqueue(20);

        queue.enqueue(30);

        queue.enqueue(40);

        

        System.out.println(queue.dequeue() + 

                     " dequeued from queue\n");

        

        System.out.println("Front item is "

                               queue.front());

           

        System.out.println("Rear item is "

                                queue.rear());

    }

}

  
// Этот код предоставлен Gaurav Miglani

python3

# Python3 программа для реализации массива очереди

  
# Class Queue для представления очереди

class Queue:

  

    функция # __init__

    def __init__(self, capacity):

        self.front = self.size = 0

        self.rear = capacity -1

        self.Q = [None]*capacity

        self.capacity = capacity

      

    # Очередь заполнена, когда размер становится

    # равно мощности

    def isFull(self):

        return self.size == self.capacity

      

    # Очередь пуста, когда размер равен 0

    def isEmpty(self):

        return self.size == 0

  

    # Функция для добавления элемента в очередь.

    # Это меняет тыл и размер

    def EnQueue(self, item):

        if self.isFull():

            print("Full")

            return

        self.rear = (self.rear + 1) % (self.capacity)

        self.Q[self.rear] = item

        self.size = self.size + 1

        print("%s enqueued to queue"  %str(item))

  

    # Функция для удаления элемента из очереди.

    # Изменяет фронт и размер

    def DeQueue(self):

        if self.isEmpty():

            print("Empty")

            return

          

        print("%s dequeued from queue" %str(self.Q[self.front]))

        self.front = (self.front + 1) % (self.capacity)

        self.size = self.size -1

          

    # Функция, чтобы получить начало очереди

    def que_front(self):

        if self.isEmpty():

            print("Queue is empty")

  

        print("Front item is", self.Q[self.front])

          

    # Функция, чтобы получить заднюю часть очереди

    def que_rear(self):

        if self.isEmpty():

            print("Queue is empty")

        print("Rear item is"self.Q[self.rear])

  

  
Код водителя

if __name__ == '__main__':

  

    queue = Queue(30)

    queue.EnQueue(10)

    queue.EnQueue(20)

    queue.EnQueue(30)

    queue.EnQueue(40)

    queue.DeQueue()

    queue.que_front()

    queue.que_rear()

C #

// C # программа для реализации массива очереди

using System;

  

namespace GeeksForGeeks

{

    // Класс для представления линейной очереди

    class Queue

    {

        private int []ele;

        private int front;

        private int rear;

        private int max;

  

        public Queue(int size)

        {

            ele = new int[size];

            front = 0 ;

            rear = -1;

            max = size;

        }

          

        // Функция для добавления элемента в очередь.

        // Он меняет тыл и размер

        public void enqueue(int item)

        {

            if (rear == max-1)

            {

                Console.WriteLine("Queue Overflow");

                return;

            }

            else

            {

                ele[++rear] = item;

            }

              

        }

          

        // Функция для удаления элемента из очереди.

        // Изменяет фронт и размер

        public int dequeue()

        

            if(front == rear + 1)

            {

                Console.WriteLine("Queue is Empty");

                return -1;

            }

            else

            {

                Console.WriteLine( ele[front]+" dequeued from queue");

                int p = ele[front++];

                Console.WriteLine();

                Console.WriteLine("Front item is {0}",ele[front]);

                Console.WriteLine("Rear item is {0} ",ele[rear]);

        return p;

            }

              

        }

          

        // Функция для печати очереди.

        public void printQueue()

        {

            if (front == rear + 1)

            {

                Console.WriteLine("Queue is Empty");

                return;

            }

            else

            {

                for (int i = front; i <= rear; i++)

                {

                    Console.WriteLine(ele[i]+ " enqueued to queue" );

                }

            }

              

        }

    }

  

    // Код драйвера

    class Program

    {

        static void Main()

        {

            Queue Q = new Queue(5);

  

            Q.enqueue(10);

            Q.enqueue(20);

            Q.enqueue(30);

            Q.enqueue(40);

            Q.printQueue();

            Q.dequeue();

          

          

        }

    }

}


Выход:

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40

Сложность времени: временная сложность всех операций, таких как enqueue (), dequeue (), isFull (), isEmpty (), front () и Rear (), равна O (1). Там нет цикла ни в одной из операций.

Реализация связного списка проще, это обсуждается здесь: Очередь | Набор 2 (реализация связанного списка)

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Очередь | Набор 1 (Введение и реализация массива)

0.00 (0%) 0 votes