AVAILABLE: 5
A stack can be described as a collection of objects or data arranged in a way where items are placed one on top of another. The first item to enter the stack will be the last to leave. This concept can be easily visualized as a stack of books, where the first book placed at the bottom is the last one to be removed. This is known as FILO (First In Last Out). The addition or removal of data occurs only from one end, known as the Top of Stack.
Basic Stack Operations
There are two fundamental operations in a stack:
- Push: Adds an element to the top of the stack.
- Pop: Removes the top element from the stack.
Other Operations on Stacks
Apart from push and pop, other operations associated with stacks include:
- Declaration: Defining the stack structure.
- Initialization: Creating an empty stack by assigning an initial value to the top.
- Empty Check: Checking if the stack is empty.
- Full Check: Checking if the stack is full.
Complete Stack Operations
1. Stack Declaration with Arrays
The stack structure is created in memory. Since a stack can be represented in two ways, declaration methods also vary. A stack typically consists of:
- Top: Points to the last element in the stack.
- Elements: Contain the data in the stack, represented as an array.
Example of stack declaration:
struct stack {
int elements[10]; // Elements
int top; // Top of the stack
};
2. Initialization
Initialization involves creating an empty stack. For an array-based stack, the top field is set to -1 if the array starts from index 0, or 0 if it starts from index 1.
p->top = -1;
3. Empty Check
This operation checks whether the stack is empty. It is essential before performing a pop operation, as popping from an empty stack is invalid.
if (p->top == -1) {
cout << "STACK is empty";
return -1;
}
4. Full Check
This operation determines if the stack is full. It returns true if the top field equals size - 1.
if (p->top == size - 1)
cout << "STACK is full";
5. Push Operation
This operation adds a new element to the stack and updates the top position.
Steps:
- Check if the stack is full. If not, proceed with the push.
- Increment the top and assign the new value.
if (p->top == size - 1)
cout << "STACK is full";
else
p->elements[++p->top] = value;
6. Pop Operation
This operation removes the top element and updates the top position.
Steps:
- Check if the stack is empty. If not, remove the top element.
if (p->top == -1) {
cout << "STACK is empty";
return -1;
} else {
return p->elements[p->top--];
}
Complete Program Example
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#define size 50
struct stack {
int elements[size];
int top;
};
typedef struct stack STACK;
void push(STACK* p, int value) {
if (p->top == size - 1)
cout << "STACK is full";
else
p->elements[++p->top] = value;
}
int pop(STACK* p) {
if (p->top == -1) {
cout << "STACK is empty";
return -1;
} else {
return p->elements[p->top--];
}
}
void display(STACK* p) {
if (p->top == -1)
cout << "\nSTACK is empty\n";
else {
cout << "\nSTACK contents: \n";
for (int i = p->top; i >= 0; --i)
cout << p->elements[i] << "\n";
}
}
void main() {
STACK s;
int x, c;
s.top = -1;
do {
cout << "Menu Options";
cout << "\n1: PUSH Operation\n";
cout << "2: POP Operation\n";
cout << "3: Display Stack\n";
cout << "4: Clear Stack\n";
cout << "5: Exit\n";
cout << "\nYour choice: ";
cin >> c;
switch (c) {
case 1:
cout << "\nEnter stack element: ";
cin >> x;
push(&s, x);
display(&s);
break;
case 2:
x = pop(&s);
if (x != -1)
cout << "\nRemoved Element: " << x;
break;
case 3:
display(&s);
break;
case 4:
if (s.top == -1)
cout << "\nSTACK is empty";
else {
cout << "\nClearing STACK\n";
while (s.top != -1)
cout << "Removed element: " << pop(&s) << "\n";
}
s.top = -1;
}
getch();
} while (c != 5);
}
Animated Stack Example
The article also includes an animation example for visualizing push and pop operations. It uses delay functions to mimic movement, but this code might need modification to compile with modern C++ compilers.
Source:
Data Structure Course Materials, STMIK EL Rahma Yogyakarta, by Eko Riswanto