Summary stack

STACK
A stack is a linear data structure that follows the Last-In-
First-Out (LIFO) principle. It is named "stack" because it
resembles a stack of items, where the last item placed on
top is the first one to be removed.
1. REPRESENTATION AND OPERATIONS ON STACK USING ARRAYS
AND LINKED LIST
Representation and Operations on Stack using Arrays:

Representation:
- Stacks can be implemented using arrays.
- Create an array of a fixed size to hold the elements of the
stack.
- Use a variable to keep track of the top index, which
indicates the position of the topmost element in the stack.

Operations:
1. Push: Adds an element to the top of the stack.
- Check if the stack is full (top index equals the maximum
size minus 1) to avoid overflow.
- Increment the top index and insert the element at that
position in the array.

2. Pop: Removes and returns the topmost element from the
stack.
- Check if the stack is empty (top index is -1) to avoid
underflow.
- Retrieve the element at the top index, decrement the top
index, and return the element.

3. Peek (or Top): Returns the topmost element from the
stack without removing it.
- Check if the stack is empty (top index is -1) to avoid
accessing invalid memory.
- Return the element at the top index without modifying
the stack.

Representation and Operations on Stack using Linked List:

Representation:
- Stacks can also be implemented using linked lists.
- Create a linked list where each node contains the element
and a reference to the next node.
- Use a variable to keep track of the top node, which
represents the topmost element in the stack.

Operations:
1. Push: Adds an element to the top of the stack.
- Create a new node with the element.
- Set the next reference of the new node to point to the
current top node.

, - Update the top node reference to the new node.

2. Pop: Removes and returns the topmost element from the
stack.
- Check if the stack is empty (top node is NULL) to avoid
underflow.
- Store the element from the top node.
- Update the top node reference to point to the next node.
- Free the memory allocated for the previous top node.
- Return the stored element.

3. Peek (or Top): Returns the topmost element from the
stack without removing it.
- Check if the stack is empty (top node is NULL) to avoid
accessing invalid memory.
- Return the element from the top node without modifying
the stack.

In both representations, it's essential to handle special
cases such as checking for overflow or underflow conditions
and properly managing memory to avoid memory leaks. The
choice of array or linked list implementation depends on
factors like the size requirements, efficiency, and flexibility
needed in the specific use case.


2. APPLICATION OF STACK-POLISH NOTATION
One of the applications of a stack is the evaluation of
expressions written in Polish Notation (also known as
Reverse Polish Notation or RPN). Polish Notation is a way of
representing arithmetic expressions without using
parentheses to indicate the order of operations.

In Polish Notation, operators are placed before their
operands. For example, the expression "3 + 4" in traditional
notation would be written as "+ 3 4" in Polish Notation.

Here's how stacks are used in the evaluation of expressions
in Polish Notation:

1. Start with an empty stack.
2. Read the expression from left to right.
3. If the token is a number, push it onto the stack.
4. If the token is an operator, pop the top two numbers from
the stack, perform the operation, and push the result back
onto the stack.
5. Repeat steps 3 and 4 until all tokens in the expression
are processed.
6. The final result will be the value left on the stack.

For example, let's evaluate the expression "+ * 5 4 2" in
Polish Notation:

1. Start with an empty stack.