StackImplementation usingArray and
Linked List in C++
A Stackisa linear data structure that follows the principle:
LIFO – Last In First Out
Example from daily life:
A pileof plates. The plate placed last is removed first.
BasicOperationsof Stack:
Operation Meaning
Push Insert anelement
Pop Delete the top element
Peek /Top View top element
isEmpty Check if stack is empty
isFull Check if stack is full(arraystack)
1. Stack Implementation usingArray
Inthis method, stackelements are stored in a fixed-sizearray.
Diagram
Top
↓
| 40|
| 30 |
| 20 |
| 10 |
-----
ArrayStack
Algorithm
Push Operation
1. Check if stack is full
2. Increment top
3. Insert element at stack[top]
Pop Operation
1. Check if stack is empty
2. Store stack[top]
3. Decrementtop
C++ Implementation(Array Stack)
#include<iostream>
usingnamespace std;
#define MAX5
class Stack{
int arr[MAX];
int top;
public:
Stack(){
top= -1;
}
voidpush(int x){
if(top == MAX-1){
cout<<"Stack Overflow\n";
return;
}
arr[++top] =x;
}
voidpop(){
if(top == -1){
cout<<"Stack Underflow\n";
return;
}
cout<<"Deleted element: "<<arr[top]<<endl;
top--;
}
voidpeek(){
if(top == -1){
cout<<"Stack Empty\n";
return;
}
cout<<"Top element: "<<arr[top]<<endl;
}
voiddisplay(){
for(int i = top; i >= 0; i--){
cout<<arr[i]<<" ";
}
cout<<endl;
}
};
int main(){
Stack s;
[Link](10);
[Link](20);
[Link](30);
[Link]();
[Link]();
[Link]();
}
Advantages of Array Stack
1. Simple implementation
2. Fast memory access
3. No extra memoryfor pointers
Disadvantages
1. Fixed size
2. Maycause stackoverflow if size is exceeded
2. StackImplementation usingLinked
List
Inthis method, stackelements are stored using nodes connected by pointers.
Each node contains:
Data +Pointer to nextnode
Diagram
Top
↓
|30 | →|20 | →|10 | →NULL
Algorithm
Push
1. Create new node
2. Set new->next = top
3. Update top =new node
Pop
1. Store topnode
2. Move top to next node
3. Delete stored node
C++ Implementation(Linked List Stack)
#include<iostream>
usingnamespace std;
struct Node{
int data;
Node*next;
};
Node* top = NULL;
void push(int x){
Node*temp = new Node();
temp->data =x;
temp->next= top;
top = temp;
}
void pop(){
if(top == NULL){
cout<<"Stack Underflow\n";
return;
}
Node*temp = top;
cout<<"Deletedelement: "<<top->data<<endl;
top = top->next;
delete temp;
}
void display(){
Node*temp = top;
while(temp !=NULL){
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
int main(){
push(10);
push(20);
push(30);
display();
pop();
display();
}
3. Comparison Table (Very Important for
Exams)
Feature Array Implementation Linked List Implementation
MemorySize Fixed Dynamic
Overflow Possible Rare
MemoryUsage Less Extramemory forpointer
Implementation Easy Slightly complex
Flexibility Limited Flexible
4. Time Complexity
Operation TimeComplexity
Push O(1)
Pop O(1)
Peek O(1)
Bothimplementationshave constant time complexity.
5. Key Insight to Writein Exam (ToBeat
Competition)
Array stackis faster duetocontiguous memory, whilelinkedlist stackis more
flexiblebecauseit grows dynamically without predefinedsize.
Inmodernsystems, linked list stacks arepreferred when memory size is
unpredictable.
6. Real Applications of Stack
Stacks quietlypower many technologies:
Function calls and recursion
Expression evaluation
Undo/Redo operations
Browser history
Syntax parsingin compilers
✅ OnePowerful ClosingLinefor Exams
A stack is not merelya data structure; it is the silent mechanismbehind recursion,
compilers, and program execution itself.
If you want, I can also show 3advanced thingsthat most students never writein
exams:
1. Stack implementation using two queues
2. Howrecursion internally uses stackmemory
3. Stack memory diagramduringfunction calls
These conceptsmake your answer standfar aheadof otherstudents.