Рубрики

Очередь — реализация связанного списка

В предыдущем посте мы представили Queue и обсудили реализацию массива. В этом посте обсуждается реализация связанного списка. Следующие две основные операции должны быть реализованы эффективно.

В структуре данных Queue мы поддерживаем два указателя, спереди и сзади . Фронт указывает первый элемент очереди, а задний указывает на последний элемент.

enQueue () Эта операция добавляет новый узел после заднего и перемещает задний к следующему узлу.

deQueue () Эта операция удаляет передний узел и перемещает фронт к следующему узлу.

C ++

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

using namespace std;

  
// Узел связанного списка (LL) для хранения записи в очереди

class QNode {

public:

    int key;

    QNode* next;

};

  
// очередь передний хранит передний узел
// LL и задний хранит последний узел LL

class Queue {

public:

    QNode *front, *rear;

};

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

QNode* newNode(int k)

{

    QNode* temp = new QNode();

    temp->key = k;

    temp->next = NULL;

    return temp;

}

  
// Вспомогательная функция для создания пустой очереди
Queue* createQueue()
{

    Queue* q = new Queue();

    q->front = q->rear = NULL;

    return q;

}

  
// Функция добавления ключа k в q

void enQueue(Queue* q, int k)

{

    // Создаем новый узел LL

    QNode* temp = newNode(k);

  

    // Если очередь пуста, то

    // новый узел - передний и задний оба

    if (q->rear == NULL) {

        q->front = q->rear = temp;

        return;

    }

  

    // Добавить новый узел в

    // конец очереди и смена тылов

    q->rear->next = temp;

    q->rear = temp;

}

  
// Функция для удаления
// ключ из заданной очереди q
QNode* deQueue(Queue* q)
{

    // Если очередь пуста, вернуть NULL.

    if (q->front == NULL)

        return NULL;

  

    // Сохранить предыдущий фронт и

    // передвинемся на один узел вперед

    QNode* temp = q->front;

    delete(temp);

  

    q->front = q->front->next;

  

    // Если front становится NULL, то

    // изменить задний также как NULL

    if (q->front == NULL)

        q->rear = NULL;

    return temp;

}

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

int main()

{

    Queue* q = createQueue();

    enQueue(q, 10);

    enQueue(q, 20);

    deQueue(q);

    deQueue(q);

    enQueue(q, 30);

    enQueue(q, 40);

    enQueue(q, 50);

    QNode* n = deQueue(q);

    if (n != NULL)

        cout << "Dequeued item is " << n->key;

    return 0;

}

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

С

// Программа AC для демонстрации реализации очереди на основе связанного списка
#include <stdio.h>
#include <stdlib.h>

  
// Узел связанного списка (LL) для хранения записи в очереди

struct QNode {

    int key;

    struct QNode* next;

};

  
// очередь, front хранит передний узел LL, а tail хранит
// последний узел LL

struct Queue {

    struct QNode *front, *rear;

};

  
// Вспомогательная функция для создания нового узла связанного списка.

struct QNode* newNode(int k)

{

    struct QNode* temp = (struct QNode*)malloc(sizeof(struct QNode));

    temp->key = k;

    temp->next = NULL;

    return temp;

}

  
// Вспомогательная функция для создания пустой очереди

struct Queue* createQueue()

{

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

    q->front = q->rear = NULL;

    return q;

}

  
// Функция добавления ключа k в q

void enQueue(struct Queue* q, int k)

{

    // Создаем новый узел LL

    struct QNode* temp = newNode(k);

  

    // Если очередь пуста, то новый узел - передний и задний оба

    if (q->rear == NULL) {

        q->front = q->rear = temp;

        return;

    }

  

    // Добавить новый узел в конец очереди и изменить тыл

    q->rear->next = temp;

    q->rear = temp;

}

  
// Функция для удаления ключа из заданной очереди q

struct QNode* deQueue(struct Queue* q)

{

    // Если очередь пуста, вернуть NULL.

    if (q->front == NULL)

        return NULL;

  

    // Сохранить предыдущий фронт и переместить фронт на один узел вперед

    struct QNode* temp = q->front;

    free(temp);

  

    q->front = q->front->next;

  

    // Если передний становится NULL, то изменить задний также как NULL

    if (q->front == NULL)

        q->rear = NULL;

    return temp;

}

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

int main()

{

    struct Queue* q = createQueue();

    enQueue(q, 10);

    enQueue(q, 20);

    deQueue(q);

    deQueue(q);

    enQueue(q, 30);

    enQueue(q, 40);

    enQueue(q, 50);

    struct QNode* n = deQueue(q);

    if (n != NULL)

        printf("Dequeued item is %d", n->key);

    return 0;

}

Джава

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

  
// Узел связанного списка (LL) для хранения записи в очереди

class QNode {

    int key;

    QNode next;

  

    // конструктор для создания нового узла связанного списка

    public QNode(int key)

    {

        this.key = key;

        this.next = null;

    }

}

  
// Класс для представления очереди
// очередь, front хранит передний узел LL, а tail хранит
// последний узел LL

class Queue {

    QNode front, rear;

  

    public Queue()

    {

        this.front = this.rear = null;

    }

  

    // Способ добавления ключа в очередь.

    void enqueue(int key)

    {

  

        // Создаем новый узел LL

        QNode temp = new QNode(key);

  

        // Если очередь пуста, то новый узел - передний и задний оба

        if (this.rear == null) {

            this.front = this.rear = temp;

            return;

        }

  

        // Добавить новый узел в конец очереди и изменить тыл

        this.rear.next = temp;

        this.rear = temp;

    }

  

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

    QNode dequeue()

    {

        // Если очередь пуста, вернуть NULL.

        if (this.front == null)

            return null;

  

        // Сохранить предыдущий фронт и переместить фронт на один узел вперед

        QNode temp = this.front;

        this.front = this.front.next;

  

        // Если передний становится NULL, то изменить задний также как NULL

        if (this.front == null)

            this.rear = null;

        return temp;

    }

}

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

public class Test {

    public static void main(String[] args)

    {

        Queue q = new Queue();

        q.enqueue(10);

        q.enqueue(20);

        q.dequeue();

        q.dequeue();

        q.enqueue(30);

        q.enqueue(40);

        q.enqueue(50);

  

        System.out.println("Dequeued item is " + q.dequeue().key);

    }

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

python3

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

  
# Узел связанного списка (LL)
# хранить запись в очереди

class Node:

      

    def __init__(self, data):

        self.data = data

        self.next = None

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

  
# Очередь, передний хранит передний узел
# LL и задний хранит последний узел LL

class Queue:

      

    def __init__(self):

        self.front = self.rear = None

  

    def isEmpty(self):

        return self.front == None

      

    # Способ добавления элемента в очередь

    def EnQueue(self, item):

        temp = Node(item)

          

        if self.rear == None:

            self.front = self.rear = temp

            return

        self.rear.next = temp

        self.rear = temp

  

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

    def DeQueue(self):

          

        if self.isEmpty():

            return

        temp = self.front

        self.front = temp.next

  

        if(self.front == None):

            self.rear = None

        return str(temp.data)

  
Код водителя

if __name__== '__main__':

    q = Queue()

    q.EnQueue(10)

    q.EnQueue(20)

    q.DeQueue()

    q.DeQueue()

    q.EnQueue(30)

    q.EnQueue(40)

    q.EnQueue(50)

      

    print("Dequeued item is " + q.DeQueue())

     

C #

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

using System;

  
// узел связанного списка (LL)
// сохраняем запись в очереди

class QNode {

    public int key;

    public QNode next;

  

    // конструктор для создания

    // новый узел связанного списка

    public QNode(int key)

    {

        this.key = key;

        this.next = null;

    }

}

  
// Класс для представления очереди Очередь,
// front хранит передний узел LL и
// в тылу хранится последний узел LL

class Queue {

    QNode front, rear;

  

    public Queue()

    {

        this.front = this.rear = null;

    }

  

    // Способ добавления ключа в очередь.

    public void enqueue(int key)

    {

  

        // Создаем новый узел LL

        QNode temp = new QNode(key);

  

        // Если очередь пуста, то новая

        // узел передний и задний оба

        if (this.rear == null) {

            this.front = this.rear = temp;

            return;

        }

  

        // Добавить новый узел в

        // конец очереди и изменение задней части

        this.rear.next = temp;

        this.rear = temp;

    }

  

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

    public QNode dequeue()

    {

        // Если очередь пуста, вернуть NULL.

        if (this.front == null)

            return null;

  

        // Сохранить предыдущий фронт и

        // передвинемся на один узел вперед

        QNode temp = this.front;

        this.front = this.front.next;

  

        // Если фронт становится NULL,

        // затем меняем тыл на NULL

        if (this.front == null)

            this.rear = null;

        return temp;

    }

}

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

public class Test {

    public static void Main(String[] args)

    {

        Queue q = new Queue();

        q.enqueue(10);

        q.enqueue(20);

        q.dequeue();

        q.dequeue();

        q.enqueue(30);

        q.enqueue(40);

        q.enqueue(50);

  

        Console.WriteLine("Dequeued item is " + q.dequeue().key);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Dequeued item is 30

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

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

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

Очередь — реализация связанного списка

0.00 (0%) 0 votes