Stack
A Stack is a linear data structure that follows the LIFO (Last In First Out)
principle.
That means — the element that is inserted last is the first to be removed.
Basic Operations:
1. push(x) → Insert an element x into the stack.
2. pop() → Remove the top element.
3. peek() / top() → View the top element without removing it.
4. isEmpty() → Check if stack is empty.
5. isFull() → (for array) Check if stack is full.
Basic Stack Operations
Operation Description Example
PUSH Adds (inserts) an element to the top of the stack. Push(10)
POP Removes (deletes) the topmost element from the stack. Pop() → removes 10
PEEK / TOP Returns the top element without removing it. Top() → returns 10
isEmpty() Checks if the stack is empty. True / False
isFull() Checks if the stack is full (in array implementation). True / False
Stack Working (Example)
Let’s consider a stack of integers.
Operation Stack Contents (Top → Bottom)
Push(10) 10
Push(20) 20, 10
Push(30) 30, 20, 10
Pop() Removes 30 → Stack = 20, 10
Shows top element = 20
Peek()
Stack Representation
A stack can be implemented using:
1. Array
2. Linked List
Each implementation has the same basic operations but uses different memory management.
Stack using Array
Algorithm
Algorithm for Push (insert an element):
1. If top == MAX - 1, then print “Stack Overflow”.
2. Else increment top by 1.
3. Assign stack[top] = value.
Algorithm for Pop (remove an element):
1. If top == -1, then print “Stack Underflow”.
2. Else display stack[top].
3. Decrement top by 1.
Algorithm for Peek:
1. If top == -1, print “Stack is Empty”.
2. Else print stack[top].
Pseudocode
Initialize stack[MAX]
Set top = -1
Procedure PUSH(value)
if top == MAX - 1 then
print "Stack Overflow"
else
top = top + 1
stack[top] = value
end if
End Procedure
Procedure POP()
if top == -1 then
print "Stack Underflow"
else
print "Deleted element:", stack[top]
top = top - 1
end if
End Procedure
Procedure PEEK()
if top == -1 then
print "Stack is Empty"
else
print "Top element:", stack[top]
end if
End Procedure
Program — Stack using Array
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
void push(int value) {
if (top == MAX - 1)
printf("Stack Overflow!\n");
else {
top++;
stack[top] = value;
printf("%d pushed into stack.\n", value);
}
}
void pop() {
if (top == -1)
printf("Stack Underflow!\n");
else {
printf("%d popped from stack.\n", stack[top]);
top--;
}
}
void peek() {
if (top == -1)
printf("Stack is Empty!\n");
else
printf("Top element is %d\n", stack[top]);
}
void display() {
if (top == -1)
printf("Stack is Empty!\n");
else {
printf("Stack elements: ");
for (int i = top; i >= 0; i--)
printf("%d ", stack[i]);
printf("\n");
}
}
int main() {
push(10);
push(20);
push(30);
display();
peek();
pop();
display();
return 0;
}
Output
10 pushed into stack.
20 pushed into stack.
30 pushed into stack.
Stack elements: 30 20 10
Top element is 30
30 popped from stack.
Stack elements: 20 10
Stack using Linked List
Algorithm
Algorithm for Push (insert element at top):
1. Create a new node.
2. Assign newNode->data = value.
3. Set newNode->next = top.
4. Set top = newNode.
Algorithm for Pop (remove element):
1. If top == NULL, print “Stack Underflow”.
2. Else, store temp = top.
3. Move top = top->next.
4. Free temp.
Algorithm for Peek:
1. If top == NULL, print “Stack is Empty”.
2. Else, print top->data.
Pseudocode
Initialize top = NULL
Procedure PUSH(value)
create newNode
newNode->data = value
newNode->next = top
top = newNode
print "Element pushed"
End Procedure
Procedure POP()
if top == NULL then
print "Stack Underflow"
else
temp = top
print "Element popped:", top->data
top = top->next
free(temp)
end if
End Procedure
Procedure PEEK()
if top == NULL then
print "Stack is Empty"
else
print "Top element:", top->data
end if
End Procedure
Program — Stack using Linked List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *top = NULL;
void push(int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top;
top = newNode;
printf("%d pushed into stack.\n", value);
}
void pop() {
if (top == NULL)
printf("Stack Underflow!\n");
else {
struct Node *temp = top;
printf("%d popped from stack.\n", top->data);
top = top->next;
free(temp);
}
}
void peek() {
if (top == NULL)
printf("Stack is Empty!\n");
else
printf("Top element is %d\n", top->data);
}
void display() {
if (top == NULL)
printf("Stack is Empty!\n");
else {
struct Node *temp = top;
printf("Stack elements: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}
int main() {
push(10);
push(20);
push(30);
display();
peek();
pop();
display();
return 0;
}
Output
10 pushed into stack.
20 pushed into stack.
30 pushed into stack.
Stack elements: 30 20 10
Top element is 30
30 popped from stack.
Stack elements: 20 10
Operator Precedence
Operator precedence defines the priority level of an operator.
When an expression has multiple operators, the operator with higher precedence is
evaluated first.
Example:
int a = 10 + 5 * 2;
Here, * (multiplication) has higher precedence than +,
so first 5 * 2 = 10, then 10 + 10 = 20.
Associativity
When two operators have same precedence, the associativity decides the
order of evaluation —
either left-to-right or right-to-left.
Example:
int a = 10 / 5 * 2;
Both / and * have the same precedence and are left-to-right
associative.
So the expression is evaluated as:
(10 / 5) * 2 = 2 * 2 = 4
Operator Precedence and Associativity Table
Category Operators Associativity Description / Example
Function call, array subscript,
1. Postfix (), [], ->, ., ++, -- Left to Right
structure access
+, -, !, ~, ++, --, (type), *, &,
2. Unary Right to Left Unary operators
sizeof
3.
*, /, % Left to Right Multiplication, Division, Modulus
Multiplicative
4. Additive +, - Left to Right Addition, Subtraction
Category Operators Associativity Description / Example
5. Shift <<, >> Left to Right Bitwise shift
6. Relational <, <=, >, >= Left to Right Comparison operators
7. Equality ==, != Left to Right Equality / Inequality
8. Bitwise AND & Left to Right Bitwise AND
9. Bitwise XOR ^ Left to Right Bitwise XOR
10. Bitwise OR ` ` Left to Right
11. Logical AND && Left to Right Logical AND
12. Logical OR ` `
13. Conditional ?: Right to Left Ternary conditional
14. Assignment =, +=, -=, *=, /=, %= etc. Right to Left Assignment operators
15. Comma , Left to Right Comma separator
Example 1:
int a = 2 + 3 * 4;
Multiplication has higher precedence
So, 3 * 4 = 12, then 2 + 12 = 14.
Example 2:
int a = 10, b = 20, c;
c = a > b ? a : b;
?: (Ternary) operator has right-to-left associativity.
Result: c = 20.
Example 3:
int a = 5, b = 10, c;
c = a + b * a++;
Step 1: b * a++ (Multiplication first)
Step 2: After using a, it increments to 6
Step 3: 5 + 50 = 55
NOTE
Parentheses () can be used to change the order of evaluation.
Postfix operators like a++ are evaluated after the expression.
Assignment operators are right-to-left associative.
Comma , operator has lowest precedence.