What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack
has one end, whereas the Queue has two ends (front and rear). It contains only one
pointer top pointer pointing to the topmost element of the stack. Whenever an element
is added in the stack, it is added on the top of the stack, and the element can be deleted
only from the stack. In other words, a stack can be defined as a container in which
insertion and deletion can be done from the one end known as the top of the stack.

Some key points related to stack

o It is called as stack because it behaves like a real-world stack, piles of books, etc.
o A Stack is an abstract data type with a pre-defined capacity, which means that it
can store the elements of a limited size.
o It is a data structure that follows some order to insert and delete the elements, and
that order can be LIFO or FILO.

Working of Stack
Stack works on the LIFO pattern. As we can observe in the below figure there are five
memory blocks in the stack; therefore, the size of the stack is 5.

Suppose we want to store the elements in a stack and let's assume that stack is empty.
We have taken the stack of size 5 as shown below in which we are pushing the elements
one by one until the stack becomes full.
Since our stack is full as the size of the stack is 5. In the above cases, we can observe
that it goes from the top to the bottom when we were entering the new element in the
stack. The stack gets filled up from the bottom to the top.

When we perform the delete operation on the stack, there is only one way for entry and
exit as the other end is closed. It follows the LIFO pattern, which means that the value
entered first will be removed last. In the above case, the value 5 is entered first, so it will
be removed only after the deletion of all the other elements.

PUSH operation
The steps or Algorithm involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

o If we try to insert the element in a stack, and the stack is full, then the overflow condition
occurs.
o When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
o When the new element is pushed in a stack, first, the value of the top gets incremented,
i.e., top=top+1, and the element will be placed at the new position of the top.
o The elements will be inserted until we reach the max size of the stack.

Code
POP operation
The steps involved in the POP operation is given below:

o Before deleting the element from the stack, we check whether the stack is empty.
o If we try to delete the element from the empty stack, then the underflow condition occurs.
o If the stack is not empty, we first access the element which is pointed by the top
o Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Code
How stack is implemented using Array
// array implementation
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int stack[MAX]; // stack[5]
int top = -1;
// push
void push()
{
int item;
printf("Enter the item: ");
scanf("%d", &item);
if (top == MAX - 1) //-1==4
{
printf("Stack Overflow");
}
else
{
printf("The element is now inserted");
top = top + 1;
stack[top] = item;
}
}
// display
void display()
{
int i;
if (top == -1)
{
printf("Stack is empty");
}
else
{
printf("The elements in the stack are: ");
for (i = top; i >= 0; i--)
{
printf("%d", stack[i]);
printf("\n");
}
}
}
// pop
void pop()
{
int data;
if (top == -1)
{
printf("stack underflow");
}
else
{
 data = stack[top];
top--; //top=top-1
printf("The deleted element is: %d", data);
}
}
// peek
// print the top most element
void peek()
{
if (top == -1)
{
printf("stack underflow");
}
else
{
printf("%d", stack[top]);
}
}
int main()
{
int ch;
while (1)
{
printf("Enter your choice: \n");
printf("1.PUSH\n2.POP\n3.DISPLAY\n4.PEEK\n5.EXIT\n");
scanf("%d", &ch);
 switch (ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
peek();
break;
case 5:
exit(0);
break;
default:
printf("Invalid chocie........");
}
}
return 0;
}
How stack implemented using Linked list
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *top=NULL;
void push()
{
struct node *newnode;
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter the data: ");
scanf("%d",&newnode->data);
newnode->next=top;
top=newnode;
}
void display()
{
struct node *temp;
temp=top;
if(top==NULL)
{
printf("Stack is empty");
}
else
{
while(temp!=NULL)
{
printf("%d\n",temp->data);
temp=temp->next;
}
}
}
void pop()
{
struct node *temp;
temp=top;
if(top==NULL)
{
printf("Stack is empty");
}
else
{
printf("Deleted element is %d",temp->data);
top=top->next;
free(temp);
}
}
void peek()
{
if(top==NULL)
{
printf("Stack is empty");
}
else
{
printf("Top element is %d",top->data);
}
}

void main()
{
int ch;
while(1)
{
printf("\n1.Push\n2.Pop\n3.Display\n4.Peek\n5.Exit\n");
printf("Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
 case 4:peek();
break;
case 5:exit(0);
break;
default:printf("Invalid choice");
}
}
}

Application of stack
Applications of the stack:
 Infix to Postfix /Prefix conversion
 Redo-undo features at many places like editors, photoshop.
 Forward and backward features in web browsers
 Used in many algorithms like Tower of Hanoi, tree
traversals, stock span problems, and histogram problems.
 Stack also helps in implementing function call in computers. The last
called function is always completed first.
 Stacks are also used to implement the undo/redo operation in text
editor.

Advantages of array implementation:

 Easy to implement.
 Memory is saved as pointers are not involved.
Disadvantages of array implementation:
 It is not dynamic i.e., it doesn’t grow and shrink depending on needs at
runtime. [But in case of dynamic sized arrays like vector in C++, list in
Python, ArrayList in Java, stacks can grow and shrink with array
implementation as well].
 The total size of the stack must be defined beforehand.
Types of Stacks:
 Fixed Size Stack: As the name suggests, a fixed size stack has a
fixed size and cannot grow or shrink dynamically. If the stack is full and
an attempt is made to add an element to it, an overflow error occurs. If
the stack is empty and an attempt is made to remove an element from
it, an underflow error occurs.
 Dynamic Size Stack: A dynamic size stack can grow or shrink
dynamically. When the stack is full, it automatically increases its size
to accommodate the new element, and when the stack is empty, it
decreases its size. This type of stack is implemented using a linked
list, as it allows for easy resizing of the stack.


Complexity Analysis:
Time Complexity
Opera ons Complexity
push() O(1)

pop() O(1)

isEmpty() O(1)

size() O(1)

And follow stack conversion (most imp)