Build a stack of whole numbers as a linked list. Handle these commands:
push x: put x on top.pop: remove the top number and print it, or printemptyif the stack is empty.size: print how many numbers are on the stack.
At the end, free every node that is left.
What to build
A stack built from nodes on the heap.
Requirements
- Handle
push,popandsize. - Free every remaining node at the end.
Input
The first line has q (1 ≤ q ≤ 1000). Each of the next q lines has one command.
Output
One line for each pop and size command.
Constraints
q is from 1 to 1000.
Example
Input:
5
push 3
push 7
pop
size
pop
Output:
7
1
3
Why it works
The top of the stack is the head of the list, so both push and pop work at the front and need only one or two pointer changes.
Examples
Example 1 · Input
5 push 3 push 7 pop size pop
Expected output
7 1 3
Example 2 · Input
2 pop size
Expected output
empty 0
Hints
Hint 1
push: malloc a node, set node->next = top, then top = node.
Hint 2
pop: remember top->next, print and free top, then move top.
Hint 3
Popping an empty stack prints empty.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
int value;
struct node *next;
};
int main(void) {
int q;
scanf("%d", &q);
struct node *top = NULL;
int size = 0;
for (int i = 0; i < q; i++) {
char cmd[8];
scanf("%7s", cmd);
if (strcmp(cmd, "push") == 0) {
int x;
scanf("%d", &x);
struct node *n = malloc(sizeof(struct node));
n->value = x;
n->next = top;
top = n;
size++;
} else if (strcmp(cmd, "pop") == 0) {
if (top == NULL) {
printf("empty\n");
} else {
struct node *next = top->next;
printf("%d\n", top->value);
free(top);
top = next;
size--;
}
} else {
printf("%d\n", size);
}
}
while (top != NULL) {
struct node *next = top->next;
free(top);
top = next;
}
return 0;
}