ARRAY REPRESENTATION OF STACKS
- In the computer’s memory, stacks can be represented as a linear array.
- Every stack has a variable called TOP associated with it, which is used to store the address of the topmost element of the stack.
- TOP is the position where the element will be added to or deleted from.
- There is another variable called MAX, which is used to store the maximum number of elements that the stack can hold
Underflow and Overflow
if TOP = -1 ,(underflow), it indicates that the stack is empty
if TOP = MAX–1,(overflow) then the stack is full
PUSH operation of stack
The algorithm for the push operation of a stack is a straightforward process of adding an element to the top of the stack. Here’s the step-by-step algorithm for the push operation of a stack:
- Check if the stack is full (if it has reached its maximum capacity). If the stack is full, you cannot push another element, and you should handle this situation accordingly (e.g., by displaying an error message or resizing the stack).
- If the stack is not full, increment the top (variable)/index by 1 to move it to the next available position in the array (assuming you’re implementing the stack using an array). Otherwise, if implemented using linked then create a new node.
- Add the new element to the position indicated by the updated index (in case of array) or add newly created node at the beginning of the list (in case of linked list)
Remember to handle stack overflow conditions by checking if the stack is full before pushing an element. How you handle stack overflow depends on your specific implementation
Algorithm for PUSH operation
Step1: if TOP = MAX-1 Print OVERFLOW, Goto Step 4
Step2: Set TOP = TOP + 1
Step3: Set Stack[TOP] = Value
Step4: END
POP operation of stack
The pop operation in a stack is used to remove and retrieve the top element from the stack. It follows the Last-In-First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. Here’s the algorithm for the pop operation of a stack:
- Check if the stack is empty. If the stack is empty (i.e., there are no elements to pop), you may want to handle this situation accordingly, such as displaying an error message or returning a special value (e.g., -1) to indicate an empty stack.
- If the stack is not empty, retrieve the element at the top of the stack, which is the element at the position indicated by the
toppointer/index. - Decrement the
toppointer/index by 1 to remove the top element from the stack. This step effectively “pops” the element from the stack. - Optionally, you can return the popped element if you want to use it or process it in some way.
Algorithm for POP operation
Step1: if TOP = -1 Print UNDERFLOW, Goto Step 4
Step2: Set value = Stack[TOP]
Step3: Set TOP = TOP -1
Step4: END
linked list REPRESENTATION OF STACKS
A linked list can be used to represent a stack data structure. In a linked list representation of a stack, each element in the stack is represented by a node in the linked list. Following declaration are required for implementaion
Node Structure: First, you need a node structure that consists of two parts: a data field to store the element being pushed onto the stack and a reference (or pointer) to the next node in the stack. This reference is what creates the linkage between nodes, forming the linked list.
struct Node {
int data; // Data or value of the element
Node* next; // Pointer to the next node in the stack
};
Stack Class: Next, you can create a stack class that uses the linked list node structure to implement stack operations. The stack class will typically have the following attributes and methods:
- A pointer to the top of the stack (often called top), which initially points to NULL to indicate an empty stack.
- Methods for stack operations: push, pop, peek (or top), isEmpty, and size.
The elements are dynamically allocated and linked together, allowing the stack to grow and shrink as elements are pushed and popped.
Expertvision 