Clasa a XI-a · Alocare dinamică: liste, stive, coziRead in English

Coada implementată cu un vector în C++

În engleză: Queue implemented with an array

O(1)C++1762 de linii1 exemplu

Ideea

Coada este o structură de tip FIFO (primul intrat, primul ieșit): se adaugă la sfârșit și se scoate de la început, ca la un ghișeu. Cu un vector c și doi indici: inc (poziția primului element) și sf (poziția ultimului). push pune elementul pe poziția sf + 1, pop crește inc, iar coada e vidă când inc > sf. Operațiile sunt „push x”, „pop” și „front” (afișează primul element); la coadă vidă se afișează „Coada vida”.

Descrierea în engleză

The queue is a FIFO structure (first in, first out): elements are added at the end and removed from the front, as at a ticket counter. With an array c and two indices: inc (the position of the first element) and sf (the position of the last one). push places the element at position sf + 1, pop increases inc, and the queue is empty when inc > sf. The operations are 'push x', 'pop' and 'front' (prints the first element); on an empty queue 'Coada vida' (empty queue) is printed.

Complexitate
O(1) pentru fiecare operație
Clasa
Clasa a XI-a (Grade 11)

Exemple

Exemplul 1

Intrare

7
push 4
push 7
push 1
front
pop
front
pop

Ieșire așteptată

4
7

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

coada-cu-vector.cpp
/*
 * Titlu: Coada implementată cu un vector
 * Clasa: 11
 * Capitol: Alocare dinamică: liste, stive, cozi
 * Descriere: Coada este o structură de tip FIFO (primul intrat, primul ieșit): se adaugă
 *            la sfârșit și se scoate de la început, ca la un ghișeu. Cu un vector c și doi
 *            indici: inc (poziția primului element) și sf (poziția ultimului). push pune
 *            elementul pe poziția sf + 1, pop crește inc, iar coada e vidă când inc > sf.
 *            Operațiile sunt „push x”, „pop” și „front” (afișează primul element); la coadă
 *            vidă se afișează „Coada vida”.
 * Complexitate: O(1) pentru fiecare operație
 *
 * Exemplu
 * Intrare:
 * 7
 * push 4
 * push 7
 * push 1
 * front
 * pop
 * front
 * pop
 * Ieșire:
 * 4
 * 7
 */
#include <iostream>
#include <string>
using namespace std;

int c[10005], inc = 1, sf = 0;

int main()
{
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        string op;
        cin >> op;
        if (op == "push")
        {
            int x;
            cin >> x;
            c[++sf] = x;
        }
        else if (inc > sf)
        {
            cout << "Coada vida\n";
        }
        else if (op == "pop")
        {
            inc++;
        }
        else
        {
            cout << c[inc] << '\n';
        }
    }
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.