File d'attente qui utilise une pile

Question

Je n'arrive pas à comprendre une question. La question demande d'abord d'écrire une classe C++ pour représenter une pile d'entiers, et c'est tant fait. Voici mes prototypes:

class Stack{ 
private: 
    int top; 
    int item[100]; 
public: 
    Stack() {top = -1;} 
    ~Stack(); 
    void push(int x) {item[++top] = x;} 
    int pop() {return item[top--];} 
    int empty(int top); 
}; 

La deuxième partie de la question dit « Utilisation de la pile à des fins de stockage, écrire une classe C++ pour représenter une file d'attente d'entiers ». Ma file d'attente est la suivante:

class Queue{ 
private: 
    int * data; 
    int beginning, end, itemCount; 
public: 
    Queue(int maxSize = 100); 
    Queue(Queue &OtherQueue); 
    ~Queue(); 
    void enqueue(int x); 
    void dequeue(); 
    int amount(); 
}; 

Je ne comprends pas comment je dois utiliser une pile pour le stockage d'une file d'attente.

Answer 1

Je ne suis pas d'accord avec la réponse existante. Typiquement, une file d'attente est First In First Out, alors qu'une pile est évidemment Last In First Out. Je ne peux penser à une mise en œuvre en utilisant deux piles, en sautant le tout et en ajoutant tout sauf le dernier élément à la deuxième pile.

On dirait une chose stupide à faire, mais je suppose que c'est pour le bien de l'exercice. Comme indiqué ci-dessous, il est possible de faire amortized O (1), car la deuxième pile sera dans le bon ordre. Vous pouvez simplement prendre des éléments de la deuxième pile, jusqu'à ce que vous en manquiez, auquel cas vous déplacez tout de la pile d'origine à la deuxième pile.

Une file d'attente FIFO serait juste une pile avec Enqueue étant Push et Dequeue étant Pop. Cela n'a aucun sens en tant qu'exercice, alors je suppose qu'une file d'attente FIFO était prévue.

Modifier: Ajout de quelques liens, quelque chose de pas facile à faire sur mon téléphone :)

Answer 2

Une file d'attente est une pile d'entiers dans votre instance. Vous ajoutez des entiers à la pile et les supprimez de la pile.

Answer 3

Évidemment, ce ne serait pas la méthode recommandée de stockage, puisque l'un est LIFO et l'autre est FIFO.

Pour mettre en file d'attente, vous devez pousser votre entier sur la pile.

Pour supprimer la file d'attente, vous devez supprimer tous les entiers de la pile, obtenir le dernier entier et repasser tous les autres entiers sur la pile. Avoir une pile temporaire où vous poussez tous les entiers lorsque vous les enlevez, obtenez votre réponse, puis retournez tous les entiers de la pile temporaire sur votre stockage principal.

Answer 4

Je soupçonne que l'intention de la question est de définir d'abord une classe Stack comme vous avez qui a la capacité de stocker ints.

puis de déclarer une classe héritée de la pile appelée Queue qui possède ses propres fonctions addtoqueue et servefromqueue mais utilise le même mécanisme de stockage que Stack. Etant donné votre implémentation, cela peut sembler un peu étrange, mais ils ont probablement prévu une sorte d'implémentation de la liste chaînée de la pile (qui a l'avantage de ne pas avoir de limite supérieure prédéfinie) auquel cas la file héritée de la pile sens du design.

Answer 5

File d'attente avec pile? Vous aurez besoin de 2 piles, bien sûr ce serait une implémentation de file d'attente O (n).

Answer 6

Il existe différents types de files d'attente:

• First in - first out (FIFO) queues
• Last in - first out (LIFO) queues

Si votre file d'attente est une file d'attente LIFO, qu'il devient simplement une façade d'une pile où la carte Enque/deque pousser/pop. Si vous voulez une file d'attente FIFO, vous aurez besoin de deux piles et déplacez les éléments de l'un vers l'autre pour accéder au premier élément quand il est interrogé, alors vous pouvez dessiner à partir du haut de la deuxième pile (qui est dans l'ordre inverse) tant que rien d'autre n'est demandé. si cela arrive, vous devez tout remettre à la première pile ... Pas très efficace mais peut-être réaliser que c'est le but de l'exercice ...

NB: vous pouvez au moins faire la capacité maximale de votre pile configurable au moment de la construction. Le rendre entièrement dynamique est probablement hors de la portée de l'exercice que vous essayez de résoudre.

Answer 7

Les données privées de la file d'attente doivent être une pile.Avec cela seul vous pouvez bien sûr mettre en œuvre une file d'attente LIFO seulement; pour une file d'attente FIFO vous avez besoin de deux piles - pour citer l'indice pour l'exercice 10 à cet excellent page, "Indice: Si vous poussez des éléments sur une pile, puis les pop tous, ils apparaissent dans l'ordre inverse.Si vous répétez ce processus »

Answer 8

La différence entre une pile et une file d'attente est dans une pile que vous ajoutez et supprimez des éléments du haut, alors que dans une file d'attente vous ajoutez en haut et supprimez du fond. Donc, pour implémenter une file d'attente en utilisant une pile, l'opération de mise en file d'attente sera un push normal sur la pile, tandis que l'opération de dequeue devra sortir la pile entière, récupérer le dernier élément, puis repasser tous les éléments sur la pile. Vous devrez utiliser une autre pile pour stocker les éléments temporairement.

Answer 9

Prenez deux piles, dans et sur.

• Pour enqueue un élément, push sur pile en.
• Pour dequeue un élément,
  1. pop un élément de pile à si sur est non vide; sinon,
  2. pop et push tous les éléments de dans à sur, servent ensuite l'élément supérieur de sur.

Il est important que vous effectuez l'étape 2 seulement si nécessaire. Notez que enqueue a la complexité O (1) et dequeue a amortized complexité O (1), à condition que vos implémentations de pop et push sont O (1).

Answer 10

Je suppose que "utiliser la pile à des fins de stockage" signifie utiliser la pile au lieu du tas. Autrement dit, n'appelez pas malloc et n'utilisez pas de variables globales.

Modifier: Ou peut-être pas. Plus je pense à cela, plus je pense que c'est une mission mal formulée ou mal conçue.

Answer 11

Si vous souhaitez vraiment implémenter une file d'attente à l'aide d'une pile, vous pouvez ajouter une variable membre Stack à la classe Queue. Les méthodes sont ensuite implémentées comme ceci:

void Queue::enqueue(int value) { 
    stack.push(value); 
} 

int Queue::dequeue() { 
    // TODO: Check for empty queue. 
    Stack tempStack; 
    do { 
    tempStack.push(stack.pop()); 
    } while (!stack.empty()); 
    int value = tempStack.pop(); 
    while (!tempStack.empty()) { 
    stack.push(tempStack.pop()); 
    } 
    return value; 
} 

C'est une implémentation très inefficace.

Answer 12

Donc, vraiment, il s'agit de donner une entrée de pile et ensuite de sortir des informations de cette pile comme si c'était un que.

Je ne pense pas que vous ayez besoin d'enlever TOUS les entiers de la pile. Êtes-vous autorisé à utiliser d'autres méthodes pour la pile? Je veux dire, basé sur x86, vous pouvez toujours obtenir des éléments sur une pile en fonction de leur adresse. En ce sens, vous pouvez toujours obtenir le premier élément sur le qui en récupérant le membre de données «premier entré» qui sera toujours au premier index du tableau dans la structure de données de la pile (comme représenté dans votre prototype). Donc - puisque la pile est LIFO et que le est FIFO, utilisez cela à votre avantage puisque la structure de données que dépend de la structure de données de la pile. Si vous le pouvez, incluez une méthode qui permet la récupération du premier élément sur 'top' de la pile (ce qui serait l'élément @ index 0).

Assurez-vous que cela convient à votre professeur d'abord.