A linked stack that cleans up after itself

Build a stack of heap nodes, and make sure every node is deleted exactly once.

What to build

A Stack class built from linked nodes, with commands to push, pop, look at the top and count.

Requirements

Create each node with new and delete it when it is popped.
Print empty for pop or top on an empty stack.
In the destructor, delete the remaining nodes and print freed K, where K is how many there were.
Forbid copying the stack.

Input

The first line has q. Each of the next q lines is push x, pop, top or size.

Output

One line for each pop, top and size, then freed K when the stack is destroyed at the end of main.

Constraints

1 ≤ q ≤ 1000, and each x is from -1000 to 1000.

Example

Input:

6
push 5
push 7
top
pop
size
push 9

Output:

7
7
1
freed 2

Why it works

Every node is deleted either by pop or by the destructor, never both, so nothing leaks and nothing is freed twice. Forbidding copies stops two stacks from owning the same nodes.

Examples

Example 1 · Input

6
push 5
push 7
top
pop
size
push 9

Expected output

7
7
1
freed 2

Example 2 · Input

2
pop
top

Expected output

empty
empty
freed 0

Hints

Hint 1

Each push makes a node with `new`, pointing at the old top.

Hint 2

Each pop keeps the value, moves the top down, and deletes the old node.

Hint 3

The destructor deletes every node still left, counting them, and prints `freed K`.

Solution

Show one correct solution (try it yourself first)

#include <iostream>
#include <string>
using namespace std;

struct Node {
    int value;
    Node* next;
};

class Stack {
    Node* head;
    int count;
public:
    Stack() : head(nullptr), count(0) {}
    Stack(const Stack&) = delete;
    Stack& operator=(const Stack&) = delete;
    ~Stack() {
        int freed = 0;
        while (head != nullptr) {
            Node* old = head;
            head = head->next;
            delete old;
            freed++;
        }
        cout << "freed " << freed << endl;
    }
    void push(int x) {
        head = new Node{x, head};
        count++;
    }
    bool empty() const { return head == nullptr; }
    int top() const { return head->value; }
    int pop() {
        Node* old = head;
        int x = old->value;
        head = old->next;
        delete old;
        count--;
        return x;
    }
    int size() const { return count; }
};

int main() {
    int q;
    cin >> q;
    Stack s;
    while (q-- > 0) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int x;
            cin >> x;
            s.push(x);
        } else if (cmd == "size") {
            cout << s.size() << endl;
        } else if (s.empty()) {
            cout << "empty" << endl;
        } else if (cmd == "top") {
            cout << s.top() << endl;
        } else {
            cout << s.pop() << endl;
        }
    }
    return 0;
}

Lesson: Objects on the heap: new and delete →