Build a list from nodes, following commands.
What to build
A linked list that you manage by hand.
Requirements
push Xadds at the front. Print nothing.popremoves the front value and prints it, or printsempty.printprints all the values from front to back, separated by single spaces, orempty.- Delete every remaining node at the end.
Input
The first line has n. Each of the next n lines is a command.
Output
One line for each pop and print.
Constraints
n is from 1 to 1000.
Example
Input:
4
push 1
push 2
print
pop
Output:
2 1
2
Why it works
Each node is created with new, so each must be deleted exactly once, whether it is popped or left over at the end.
Examples
Example 1 · Input
4 push 1 push 2 print pop
Expected output
2 1 2
Example 2 · Input
2 pop print
Expected output
empty empty
Hints
Hint 1
Each node holds a value and a pointer to the next one.
Hint 2
pop has to save the next pointer before deleting.
Hint 3
Delete every remaining node at the end.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <string>
using namespace std;
struct Node {
int value;
Node* next;
};
int main() {
int n;
cin >> n;
Node* head = nullptr;
for (int i = 0; i < n; i++) {
string command;
cin >> command;
if (command == "push") {
int x;
cin >> x;
Node* node = new Node;
node->value = x;
node->next = head;
head = node;
} else if (command == "pop") {
if (head == nullptr) {
cout << "empty" << endl;
} else {
Node* old = head;
cout << old->value << endl;
head = old->next;
delete old;
}
} else if (head == nullptr) {
cout << "empty" << endl;
} else {
for (Node* p = head; p != nullptr; p = p->next) {
cout << p->value << (p->next ? " " : "\n");
}
}
}
while (head != nullptr) {
Node* next = head->next;
delete head;
head = next;
}
return 0;
}