Réapprendre les bases de CS - Implémentation de Queue

Avez-vous déjà fait la queue ? La structure des données de la file d'attente fait également la même chose. Vous vous tenez au bout de la file d'attente lorsque vous souhaitez passer une commande, peut-être dans votre restaurant libre-service préféré, puis vous remontez la file d'attente et partez.

La structure de données Queue dans CS exécute la même fonctionnalité. La structure de données de file d'attente est une structure de données premier entré, premier sorti. La structure des données de file d'attente peut être construite avec deux fonctions de base Enqueue et Dequeue qui consistent essentiellement à ajouter à la liste et à supprimer de la liste.

Exemples concrets

Dans le monde réel de l'informatique, les files d'attente constituent l'épine dorsale des composants logiciels suivants

• Planification des tâches
• Gestion des événements
• Communication asynchrone, etc.

Alors qu'un composant simple et facile à visualiser serait

1. Une file d'attente en playlist pour les chansons
2. Une file d'attente dans l'ordre des données envoyées sur le réseau, etc.

Mise en œuvre

package main

import (
    "fmt"
    "errors"
)

type Queue struct{
    Elements []int
    Size int
}

func (q *Queue) Enqueue(value int){
    if q.GetLength() == q.Size { 
        fmt.Println("Overflow") 
        return
    } 
    q.Elements = append(q.Elements, value) 
}

func (q *Queue) Dequeue() int {
    if q.IsEmpty() { 
        fmt.Println("UnderFlow") 
        return 0
    } 
    element := q.Elements[0] 
    if q.GetLength() == 1 { 
        q.Elements = nil 
        return element 
    } 
    q.Elements = q.Elements[1:] 
    return element
}

func (q *Queue) GetLength() int { 
    return len(q.Elements) 
} 

func (q *Queue) IsEmpty() bool { 
    return len(q.Elements) == 0
} 

func (q *Queue) Peek() (int, error) { 
    if q.IsEmpty() { 
        return 0, errors.New("empty queue") 
    } 
    return q.Elements[0], nil 
} 

Complexité

Complexité temporelle - O(1) pour la mise en file d'attente et la suppression de la file d'attente
Complexité spatiale - O(1) pour Enqueue et Dequeue

Références

Référence - https://www.geeksforgeeks.org/queue-in-go-lingual/

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!