Implementación de array de cola (simple)

En queue , la inserción y la eliminación ocurren en los extremos opuestos, por lo que la implementación no es tan simple como stack
Para implementar una cola usando una array, cree una array arr de tamaño n y tome dos variables delante y detrás , las cuales se inicializarán en 0 , lo que significa que la cola está actualmente vacía. El elemento posterior es el índice hasta el cual se almacenan los elementos en la array y el frente es el índice del primer elemento de la array. Ahora, algunas de las implementaciones de las operaciones de cola son las siguientes: 

  1. Enqueue: Adición de un elemento a la cola. La adición de un elemento se realizará después de comprobar si la cola está llena o no. Si trasero < n , lo que indica que la array no está llena, almacene el elemento en arr[posterior] e incremente la parte trasera en 1 , pero si trasera == n , entonces se dice que es una condición de desbordamiento ya que la array está llena.
  2. Dequeue: Eliminación de un elemento de la cola. Un elemento solo se puede eliminar cuando hay al menos un elemento para eliminar, es decir, trasero > 0 . Ahora, el elemento en arr[front] se puede eliminar, pero todos los elementos restantes deben desplazarse hacia la izquierda una posición para que la operación de eliminación de la cola elimine el segundo elemento de la izquierda en otra operación de eliminación de la cola.
  3. Frontal: Obtenga el elemento frontal de la cola, es decir , arr[frontal] si la cola no está vacía.
  4. Pantalla: Imprime todos los elementos de la cola. Si la cola no está vacía, recorra e imprima todos los elementos desde el índice de adelante hacia atrás .

A continuación se muestra la implementación de una cola usando una array: 

C++

// C++ program to implement a queue using an array
#include <bits/stdc++.h>
using namespace std;
 
struct Queue {
    int front, rear, capacity;
    int* queue;
    Queue(int c)
    {
        front = rear = 0;
        capacity = c;
        queue = new int;
    }
 
    ~Queue() { delete[] queue; }
 
    // function to insert an element
    // at the rear of the queue
    void queueEnqueue(int data)
    {
        // check queue is full or not
        if (capacity == rear) {
            printf("\nQueue is full\n");
            return;
        }
 
        // insert element at the rear
        else {
            queue[rear] = data;
            rear++;
        }
        return;
    }
 
    // function to delete an element
    // from the front of the queue
    void queueDequeue()
    {
        // if queue is empty
        if (front == rear) {
            printf("\nQueue is  empty\n");
            return;
        }
 
        // shift all the elements from index 2 till rear
        // to the left by one
        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }
 
            // decrement rear
            rear--;
        }
        return;
    }
 
    // print queue elements
    void queueDisplay()
    {
        int i;
        if (front == rear) {
            printf("\nQueue is Empty\n");
            return;
        }
 
        // traverse front to rear and print elements
        for (i = front; i < rear; i++) {
            printf(" %d <-- ", queue[i]);
        }
        return;
    }
 
    // print front of queue
    void queueFront()
    {
        if (front == rear) {
            printf("\nQueue is Empty\n");
            return;
        }
        printf("\nFront Element is: %d", queue[front]);
        return;
    }
};
 
// Driver code
int main(void)
{
    // Create a queue of capacity 4
    Queue q(4);
 
    // print Queue elements
    q.queueDisplay();
 
    // inserting elements in the queue
    q.queueEnqueue(20);
    q.queueEnqueue(30);
    q.queueEnqueue(40);
    q.queueEnqueue(50);
 
    // print Queue elements
    q.queueDisplay();
 
    // insert element in the queue
    q.queueEnqueue(60);
 
    // print Queue elements
    q.queueDisplay();
 
    q.queueDequeue();
    q.queueDequeue();
 
    printf("\n\nafter two node deletion\n\n");
 
    // print Queue elements
    q.queueDisplay();
 
    // print front of the queue
    q.queueFront();
 
    return 0;
}

Java

// Java program to implement a queue using an array
class Queue {
    private int front, rear, capacity;
    private int queue[];
 
    Queue(int c)
    {
        front = rear = 0;
        capacity = c;
        queue = new int[capacity];
    }
 
    // function to insert an element
    // at the rear of the queue
    static void queueEnqueue(int data)
    {
        // check queue is full or not
        if (capacity == rear) {
            System.out.printf("\nQueue is full\n");
            return;
        }
 
        // insert element at the rear
        else {
            queue[rear] = data;
            rear++;
        }
        return;
    }
 
    // function to delete an element
    // from the front of the queue
    static void queueDequeue()
    {
        // if queue is empty
        if (front == rear) {
            System.out.printf("\nQueue is empty\n");
            return;
        }
 
        // shift all the elements from index 2 till rear
        // to the right by one
        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }
 
            // store 0 at rear indicating there's no element
            if (rear < capacity)
                queue[rear] = 0;
 
            // decrement rear
            rear--;
        }
        return;
    }
 
    // print queue elements
    static void queueDisplay()
    {
        int i;
        if (front == rear) {
            System.out.printf("\nQueue is Empty\n");
            return;
        }
 
        // traverse front to rear and print elements
        for (i = front; i < rear; i++) {
            System.out.printf(" %d <-- ", queue[i]);
        }
        return;
    }
 
    // print front of queue
    static void queueFront()
    {
        if (front == rear) {
            System.out.printf("\nQueue is Empty\n");
            return;
        }
        System.out.printf("\nFront Element is: %d", queue[front]);
        return;
    }
}
 
public class StaticQueueinjava {
 
    // Driver code
    public static void main(String[] args)
    {
        // Create a queue of capacity 4
        Queue q = new Queue(4);
 
        // print Queue elements
        q.queueDisplay();
 
        // inserting elements in the queue
        q.queueEnqueue(20);
        q.queueEnqueue(30);
        q.queueEnqueue(40);
        q.queueEnqueue(50);
 
        // print Queue elements
        q.queueDisplay();
 
        // insert element in the queue
        q.queueEnqueue(60);
 
        // print Queue elements
        q.queueDisplay();
 
        q.queueDequeue();
        q.queueDequeue();
        System.out.printf("\n\nafter two node deletion\n\n");
 
        // print Queue elements
        q.queueDisplay();
 
        // print front of the queue
        q.queueFront();
    }
}

Python3

# Python3 program to implement
# a queue using an array
class Queue:
 
    # To initialize the object.
    def __init__(self, c):
         
        self.queue = []
        self.front = self.rear = 0
        self.capacity = c
 
    # Function to insert an element
    # at the rear of the queue
    def queueEnqueue(self, data):
 
        # Check queue is full or not
        if(self.capacity == self.rear):
            print("\nQueue is full")
 
        # Insert element at the rear
        else:
            self.queue.append(data)
            self.rear += 1
 
    # Function to delete an element
    # from the front of the queue
    def queueDequeue(self):
 
        # If queue is empty
        if(self.front == self.rear):
            print("Queue is empty")
 
        # Pop the front element from list
        else:
            x = self.queue.pop(0)
            self.rear -= 1
 
    # Function to print queue elements
    def queueDisplay(self):
         
        if(self.front == self.rear):
            print("\nQueue is Empty")
 
        # Traverse front to rear to
        # print elements
        for i in self.queue:
            print(i, "<--", end = '')
     
    # Print front of queue
    def queueFront(self):
         
        if(self.front == self.rear):
            print("\nQueue is Empty")
 
        print("\nFront Element is:",
              self.queue[self.front])
 
# Driver code
if __name__=='__main__':
 
    # Create a new queue of
    # capacity 4
    q = Queue(4)
 
    # Print queue elements
    q.queueDisplay()
 
    # Inserting elements in the queue
    q.queueEnqueue(20)
    q.queueEnqueue(30)
    q.queueEnqueue(40)
    q.queueEnqueue(50)
 
    # Print queue elements
    q.queueDisplay()
 
    # Insert element in queue
    q.queueEnqueue(60)
 
    # Print queue elements
    q.queueDisplay()
 
    q.queueDequeue()
    q.queueDequeue()
    print("\n\nafter two node deletion\n")
 
    # Print queue elements
    q.queueDisplay()
 
    # Print front of queue
    q.queueFront()
 
# This code is contributed by Amit Mangal

C#

// C# program to implement a queue using an array
using System;
 
public class Queue
{
    private int front, rear, capacity;
    private int []queue;
 
    public Queue(int c)
    {
        front = rear = 0;
        capacity = c;
        queue = new int[capacity];
    }
 
    // function to insert an element
    // at the rear of the queue
    public void queueEnqueue(int data)
    {
        // check queue is full or not
        if (capacity == rear)
        {
            Console.Write("\nQueue is full\n");
            return;
        }
 
        // insert element at the rear
        else
        {
            queue[rear] = data;
            rear++;
        }
        return;
    }
 
    // function to delete an element
    // from the front of the queue
    public void queueDequeue()
    {
        // if queue is empty
        if (front == rear)
        {
            Console.Write("\nQueue is empty\n");
            return;
        }
 
        // shift all the elements from index 2 till rear
        // to the right by one
        else
        {
            for (int i = 0; i < rear - 1; i++)
            {
                queue[i] = queue[i + 1];
            }
 
            // store 0 at rear indicating there's no element
            if (rear < capacity)
                queue[rear] = 0;
 
            // decrement rear
            rear--;
        }
        return;
    }
 
    // print queue elements
    public void queueDisplay()
    {
        int i;
        if (front == rear)
        {
            Console.Write("\nQueue is Empty\n");
            return;
        }
 
        // traverse front to rear and print elements
        for (i = front; i < rear; i++)
        {
            Console.Write(" {0} <-- ", queue[i]);
        }
        return;
    }
 
    // print front of queue
    public void queueFront()
    {
        if (front == rear)
        {
            Console.Write("\nQueue is Empty\n");
            return;
        }
        Console.Write("\nFront Element is: {0}", queue[front]);
        return;
    }
}
 
public class StaticQueueinjava {
 
    // Driver code
    public static void Main(String[] args)
    {
        // Create a queue of capacity 4
        Queue q = new Queue(4);
 
        // print Queue elements
        q.queueDisplay();
 
        // inserting elements in the queue
        q.queueEnqueue(20);
        q.queueEnqueue(30);
        q.queueEnqueue(40);
        q.queueEnqueue(50);
 
        // print Queue elements
        q.queueDisplay();
 
        // insert element in the queue
        q.queueEnqueue(60);
 
        // print Queue elements
        q.queueDisplay();
 
        q.queueDequeue();
        q.queueDequeue();
        Console.Write("\n\nafter two node deletion\n\n");
 
        // print Queue elements
        q.queueDisplay();
 
        // print front of the queue
        q.queueFront();
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to implement a queue using an array
class Queue{
     
constructor(c)
{
    this.front = this.rear = 0;
    this.capacity = c;
    this.queue = new Array(this.capacity);
}
 
// Function to insert an element
// at the rear of the queue
queueEnqueue(data)
{
     
    // Check queue is full or not
    if (this.capacity == this.rear)
    {
        document.write("<br>Queue is full<br>");
        return;
    }
 
    // insert element at the rear
    else
    {
        this.queue[this.rear] = data;
        this.rear++;
    }
    return;
}
 
// Function to delete an element
// from the front of the queue
queueDequeue()
{
     
    // If queue is empty
    if (this.front == this.rear)
    {
        document.write("<br>Queue is empty<br>");
        return;
    }
 
    // Shift all the elements from index 2 till rear
    // to the right by one
    else
    {
        for(let i = 0; i < this.rear - 1; i++)
        {
            this.queue[i] = this.queue[i + 1];
        }
 
        // Store 0 at rear indicating there's no element
        if (this.rear < this.capacity)
            this.queue[this.rear] = 0;
 
        // Decrement rear
        this.rear--;
    }
    return;
}
 
// Print queue elements
queueDisplay()
{
    let i;
    if (this.front == this.rear)
    {
        document.write("<br>Queue is Empty<br>");
        return;
    }
 
    // Traverse front to rear and print elements
    for(i = this.front; i < this.rear; i++)
    {
        document.write(this.queue[i] + "  <-- ");
    }
    return;
}
 
// Print front of queue
queueFront()
{
    if (this.front == this.rear)
    {
        document.write("<br>Queue is Empty<br>");
        return;
    }
    document.write("<br>Front Element is: " +
                   this.queue[this.front]);
    return;
}
}
 
// Driver code
 
// Create a queue of capacity 4
let q = new Queue(4);
 
// Print Queue elements
q.queueDisplay();
 
// Inserting elements in the queue
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
 
// Print Queue elements
q.queueDisplay();
 
// Insert element in the queue
q.queueEnqueue(60);
 
// Print Queue elements
q.queueDisplay();
 
q.queueDequeue();
q.queueDequeue();
document.write("<br><br> after two node deletion <br><br>");
 
// Print Queue elements
q.queueDisplay();
 
// Print front of the queue
q.queueFront();
 
// This code is contributed by rag2127
 
</script>
Producción: 

Queue is Empty
 20 <--  30 <--  40 <--  50 <-- 
Queue is full
 20 <--  30 <--  40 <--  50 <-- 

after two node deletion

 40 <--  50 <-- 
Front Element is: 40

 

Complejidad de tiempo de puesta en cola: O(1) 
Complejidad de tiempo de puesta en cola: O(n)

Optimizaciones: 
podemos implementar operaciones de puesta y salida de cola en tiempo O(1). Para lograr esto, podemos usar la implementación de lista enlazada de cola o la implementación de array circular de cola .
 

Publicación traducida automáticamente

Artículo escrito por Rajput-Ji y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *