Stack Implementation Using Linked List

Stack with array implementation has size limitation.
To make the stack dynamically grow, we can implement it using linked list.

Worst case

Removing a node from the end of the list would require us to transverse the whole list from head to the node before current.

int value = head->get();
Node* p = head;

head = head->getNext();

delete p;
return value;

int pop () {
    int value = head->get();
    Node* p = head;
    head = head->getNext();
    delete p;
    return value;
}

Node* newNode = new Node();

newNode->set(value);
newNode->setNext(head);

head = newNode;

void push(int value) {
    Node* newNode = new Node();
    newNode->set(value);
    newNode->setNext(head);
    head = newNode;
}

Other methods:

int top () {
    return head->get();
}

int isEmpty () {
    return (head == NULL);
}

isFULL() is not required since there is no issue of limitations on the stack size.

Linked list: each stack element has a higher memory space requirement (for the next pointers). The allocation and de-allocation of nodes also takes a little bit of time. But the benefit here is the memory can grow and shrink dynamically without any upper limit.
Array: it is pre-allocated so it is faster in terms of pop() and push() requests. The down side here is the fixed memory space, it cannot grow neither shrink and leaves vacant space behind after pop() operations.

When the operator is in between the operands.
Example: A + B;

when the operator is before the operands.
Example: + A B; ++x;

when the operator is after the operands.
Example: A B +; x++;

Examples: 1. A + (B * C) 1. A + (B C *) 2. A B C * + 2. (A + B) * C 1. (A B +) * C 2. A B + C *

Examples: