Stack Introduction
Stack is a linear data structure which is simple and easy to implement. In stack, elements are inserted and removed from only one end. So, it is less flexible than list. The first element stored in the stack is last removed out and the element last stored is first removed out. That's why stack is called LIFO (Last-In-First-Out).
Real life examples of stack are plates on a tray, coin stacks, shipments in a cargo and the examples of stack in the computer world are compiler, browser back button.
Stack Operations
In stack terminology, the element to be removed is called popped from stack and the element to be inserted is called pushed onto the stack.
The PUSH and POP operations are performed only one end of the stack. There is a pointer TOP in the stack to keep track of top element. Whenever a new element is inserted, the pointer is increased by one and then the element is placed on the stack. And when an existing element is deleted the pointer is decreased by one.
Stack Operations
These are the different operations performed on a stack -
- PUSH
- POP
- PEER
PUSH
The PUSH operation is performed to insert new element in an existing stack from the top of the stack. These are the procedural steps to insert new element in a stack.
STEP 1: If TOP >= N
print('Stack Overflow')
return
STEP 2: TOP <- TOP + 1
STEP 3: S[TOP] <- NE
STEP 4: ReturnIn the first step, we have checked the existence of space in stack (S). If there is no space then print 'Stack Overflow' and the code is exited and if not, then it first increment the top by one and place the new element (NE) at the top of stack and return.
POP
The POP operation is performed to remove existing elements from the top of the stack. These are the procedural steps to remove existing elements from a stack.
STEP 1: If TOP = 0
print('Stack Underflow')
return
STEP 2: TOP = TOP - 1
STEP 3: S[TOP - 1]
STEP 4: ReturnIn the first step, we have checked the existence of elements in a stack. If there is no any element, then print 'Stack Underflow' and the code is exited and if not then first remove the top element from the top of stack and decrease the top by one.
PEER
The stack PEER operation return the ith element from the TOP of the stack.
STEP 1: If TOP -I+1 <= 0
print('Stack Underflow')
return
STEP 2: S[TOP -I +1]
STEP 3: ReturnIn the first step, we have checked the existence of elements in a stack. If there is no any element, then print 'Stack Underflow' and the code is exited and if not, then return the ith element from the top of the stack.
Stack Program in C
#include
#include
int stack[5];
void push();
int pop();
void display();
int is_empty();
int top_element();
int top = 0;
int main()
{
int element, choice;
do
{
printf("Stack Operations.\n");
printf("1. Enter 1 to insert into stack (PUSH).\n");
printf("2. Enter 2 to delete from stack (POP).\n");
printf("3. Enter 3 to print TOP element.\n");
printf("4. Check if stack is empty.\n");
printf("5. Display stack.\n");
printf("6. Exit.\n");
printf("Enter your choice.\n");
scanf("%d",&choice);
switch (choice)
{
case 1:
if (top == 5)
printf("Error: Overflow\n\n");
else {
printf("Enter a value to insert.\n");
scanf("%d", &element);
push(element);
}
break;
case 2:
if (top == 0)
printf("Error: Underflow.\n\n");
else {
element = pop();
printf("Element removed from the stack is %d.\n", element);
}
break;
case 3:
if (!is_empty()) {
element = top_element();
printf("Element at the top of the stack is %d\n\n", element);
}
else
printf("The stack is empty.\n\n");
break;
case 4:
if (is_empty())
printf("The stack is empty.\n\n");
else
printf("The stack isn't empty.\n\n");
break;
case 5:
display();
break;
case 6:
exit(0);
}
}while(1);
return 0;
}
void push(int value) {
stack[top] = value;
top++;
}
int pop() {
top--;
return stack[top];
}
void display() {
int d;
if (top == 0) {
printf("The stack is empty.\n\n");
return;
}
printf("There are %d elements in the stack.\n", top);
for (d = top - 1; d >= 0; d--)
printf("%d\n", stack[d]);
printf("\n");
}
int is_empty() {
if (top == 0)
return 1;
else
return 0;
}
int top_element() {
return stack[top-1];
} Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
1
Enter a value to insert.
20
Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
1
Enter a value to insert.
93
Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
1
Enter a value to insert.
30
Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
1
Enter a value to insert.
30
Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
5
There are 4 elements in the stack.
30
30
93
20
Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
3
Element at the top of the stack is 30
Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
2
Element removed from the stack is 30.
Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
5
There are 3 elements in the stack.
30
93
20
Stack Operations.
1. Enter 1 to insert into stack (PUSH).
2. Enter 2 to delete from stack (POP).
3. Enter 3 to print TOP element.
4. Check if stack is empty.
5. Display stack.
6. Exit.
Enter your choice.
