Grade 11 · Dynamic allocation: lists, stacks, queuesCitește în română

Stack implemented with a linked list

Original: Stiva implementată cu o listă înlănțuită

O(1)C++1788 lines1 example

The idea

The top of the stack is the first node of a singly linked list. push creates a new node and links it in front of the top; pop moves the top to the next node and frees the old one with delete. This way the stack has no fixed maximum size. The operations are 'push x', 'pop' and 'top'; on an empty stack 'Stiva vida' (empty stack) is printed. At the end the remaining elements are printed, from the top to the bottom.

Original description (Romanian)

Vârful stivei este primul nod al unei liste simplu înlănțuite. push creează un nod nou și îl leagă în fața vârfului; pop mută vârful pe nodul următor și eliberează nodul vechi cu delete. Așa stiva nu are o dimensiune maximă fixată. Operațiile sunt „push x”, „pop” și „top”; la stivă vidă se afișează „Stiva vida”. La final se afișează elementele rămase, din vârf spre bază.

Complexity
O(1) per operation
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

6
push 5
push 1
push 9
top
pop
push 4

Expected output

9
Ramase: 4 1 5

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

stiva-cu-lista.cpp
/*
 * Titlu: Stiva implementată cu o listă înlănțuită
 * Clasa: 11
 * Capitol: Alocare dinamică: liste, stive, cozi
 * Descriere: Vârful stivei este primul nod al unei liste simplu înlănțuite. push creează
 *            un nod nou și îl leagă în fața vârfului; pop mută vârful pe nodul următor și
 *            eliberează nodul vechi cu delete. Așa stiva nu are o dimensiune maximă fixată.
 *            Operațiile sunt „push x”, „pop” și „top”; la stivă vidă se afișează
 *            „Stiva vida”. La final se afișează elementele rămase, din vârf spre bază.
 * Complexitate: O(1) pentru fiecare operație
 *
 * Exemplu
 * Intrare:
 * 6
 * push 5
 * push 1
 * push 9
 * top
 * pop
 * push 4
 * Ieșire:
 * 9
 * Ramase: 4 1 5
 */
#include <iostream>
#include <string>
using namespace std;

struct nod
{
    int info;
    nod *urm;
};

nod *varf = NULL;

void push(int x)
{
    nod *p = new nod;
    p->info = x;
    p->urm = varf;
    varf = p;
}

void pop()
{
    nod *p = varf;
    varf = varf->urm;
    delete p;
}

int main()
{
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        string op;
        cin >> op;
        if (op == "push")
        {
            int x;
            cin >> x;
            push(x);
        }
        else if (varf == NULL)
        {
            cout << "Stiva vida\n";
        }
        else if (op == "pop")
        {
            pop();
        }
        else
        {
            cout << varf->info << '\n';
        }
    }
    cout << "Ramase:";
    while (varf != NULL)
    {
        cout << ' ' << varf->info;
        pop();
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.