Реализация очереди массива (простая)

Опубликовано: 5 Января, 2022

В очереди вставка и удаление происходят на противоположных концах, поэтому реализация не так проста, как стек.
Чтобы реализовать очередь с использованием массива, создайте массив arr размера n и возьмите две переменные спереди и сзади, обе из которых будут инициализированы до 0, что означает, что очередь в настоящее время пуста. Задний элемент - это индекс, до которого элементы хранятся в массиве, а передний - это индекс первого элемента массива. Теперь некоторые реализации операций с очередями выглядят следующим образом:

  1. Enqueue: добавление элемента в очередь. Добавление элемента будет выполнено после проверки, заполнена ли очередь. Если back <n, что указывает на то, что массив не заполнен, сохраните элемент в arr [rear] и увеличьте задний на 1, но если back == n, то это считается условием переполнения, поскольку массив заполнен.
  2. Dequeue: удаление элемента из очереди. Элемент может быть удален только тогда, когда есть хотя бы элемент для удаления, т.е. задний> 0 . Теперь элемент в arr [front] может быть удален, но все оставшиеся элементы должны быть сдвинуты влево на одну позицию, чтобы операция удаления из очереди удалила второй элемент слева в другой операции удаления из очереди.
  3. Front: Получить передний элемент из очереди, т.е. arr [front], если очередь не пуста.
  4. Дисплей: распечатать весь элемент очереди. Если очередь не пуста, траверс и напечатать все элементы индекса спереди сзади.

Ниже представлена реализация очереди с использованием массива:

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( data) int
{
// check queue is full or not
if (capacity == rear) {
printf ( " Queue is full " );
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 ( " Queue is empty " );
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 ( " Queue is Empty " );
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 ( " Queue is Empty " );
return ;
}
printf ( " Front 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 ( " after two node deletion " );
// print Queue elements
q.queueDisplay();
// print front of the queue
q.queueFront();
return 0;
}

Джава

// Java program to implement a queue using an array
class Queue {
private static int front, rear, capacity;
private static 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( data) int
{
// check queue is full or not
if (capacity == rear) {
System.out.printf( " Queue is full " );
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( " Queue is empty " );
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( " Queue is Empty " );
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( " Queue is Empty " );
return ;
}
System.out.printf( " Front 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( " after two node deletion " );
// 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 ( " Queue 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 ( " Queue 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 ( " Queue is Empty" )
print ( " Front 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 ( " after two node deletion " )
# 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 static int front, rear, capacity;
private static 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( data) int
{
// check queue is full or not
if (capacity == rear)
{
Console.Write( " Queue is full " );
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( " Queue is empty " );
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( " Queue is Empty " );
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()
{