What is Stack in Data Structure?
A stack is a linear data structure and can be implemented using an array or a linked list. The top of the stack is the position where the last element was pushed. It is important to note that only the top element can be accessed and removed, while the other elements are inaccessible until the top element is removed.
A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed first.
In addition to push and pop, other common operations performed on a stack include peek, which allows you to look at the top element without removing it, and isEmpty, which checks if the stack is empty.
Learn the concepts of DSA with the complete beginner-friendly video tutorial course Data Structures & Algorithms using Java
Points to remember
It is called a stack because it behaves like a real-world stack, piles of books, etc.
A Stack is an abstract data type with a pre-defined capacity, which means that it can store elements of a limited size.
It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.
Diagram of Stack in Data Structure
Last-In-First-Out (LIFO) principle. It is a collection of elements, with two main operations: push, which adds an element to the top of the stack, and pop, which removes the most recently added element from the top of the stack.
The stack data structure supports two fundamental operations: push and pop.
Push operation adds an element to the top of the stack, while
pop operation removes the top element from the stack.
Additionally, the stack may also support a peek operation that returns the top element of the stack without modifying the stack itself.
In terms of implementation, a stack can be implemented using an array or a linked list data structure.
Array-based implementation uses a fixed-size array to store the elements, and the top of the stack is represented by an index pointing to the last element added to the stack.
Linked-list-based implementation uses a linked list to store the elements, and the top of the stack is represented by the head node of the list.
When an element is pushed onto the stack, it is added to the top of the stack, and the top pointer is updated to point to the newly added element.
When an element is popped from the stack, the top element is removed, and the top pointer is updated to point to the next element in the stack.
Working of Stack Data Structure
The operations work as follows:
A pointer called TOP is used to keep track of the top element in the stack.
When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.
On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.
On popping an element, we return the element pointed to by TOP and reduce its value.
Before pushing, we check if the stack is already full
Before popping, we check if the stack is already empty
Space complexity
The space complexity of a stack depends on the maximum number of elements that can be stored in the stack at any given time.
In general, the space complexity of a stack is O(n), where n is the maximum number of elements that can be stored in the stack.
This is because, in the worst-case scenario, the stack will need to store all n elements, resulting in a space complexity of O(n). However, if the maximum size of the stack is known and fixed, the space complexity can be considered O(1) since the amount of memory used by the stack is constant and does not depend on the size of the stack.
Time complexity
It depends on the specific operation being performed.
In general, the time complexity of the most common stack operations is as follows:
Push operation: O(1)
Pop operation: O(1)
Peek operation: O(1)
Search operation: O(n)
The push, pop, and peek operations all have a constant time complexity of O(1) because they simply involve accessing or modifying the top element of the stack.
The search operation, which looks for a specific element in the stack, has a time complexity of O(n) in the worst case because it may need to traverse the entire stack to find the element.
Operations
push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
isEmpty(): It determines whether the stack is empty or not.
isFull(): It determines whether the stack is full or not.'
peek(): It returns the element at the given position.
count(): It returns the total number of elements available in a stack.
change(): It changes the element at the given position.
display(): It prints all the elements available in the stack.
Implementation of stack can be done in multiple ways, by using an array or using a linked list.
How to implement stack using array?
In array implementations, the stack is built using arrays. All stack-related operations are performed using arrays. Let's see how to implement each operation on the stack using an array data structure.
Push Operation - Adding an element to the top of the stack is referred to as a push operation.
· Increment the variable Top so that it can now refer to the following memory location.
· Add an element at the position of incremented top. This refers to adding a new element at the top of the stack.
void push (int val,int n) //n is size of the stack
{
if (top == n )
printf("\n Overflow");
else
{
top = top +1;
stack[top] = val;
}
}
Pop Operation –
Removing an element from the top of the stack is called a pop operation. Each time an element is removed from the stack, the value of the variable top is incremented by one. The top of the stack is stored in another variable and the top is decremented by one. This operation returns the deleted value that was stored in another variable.
int pop () { if(top == -1) { printf("Underflow"); return 0; } else { return stack[top - - ]; } }
Peek operation
Peek operation involves returning the element which is present at the top of the stack without deleting it. Underflow conditions can occur if we try to return the top element in an already empty stack.
int peek() { if (top == -1) { printf("Underflow"); return 0; } else { return stack [top]; } }
How to implement stack using Linked List?
When implementing a linked list stack, the nodes are not kept contiguous in memory. Each node contains pointers to its immediate child nodes on the stack. When there is not enough space left in the memory heap to create nodes, the stack is said to overflow.
Push Operation
Adding a node to the stack is called a push operation. Pushing elements onto the stack in a linked list implementation differs from an array implementation.
void push ()
{
int val;
struct node *ptr =(struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;
}
printf("Item pushed");
}
}
Pop Operation
Removing a node from the top of the stack is called a pop operation. Deleting a node from the linked list implementation of the stack is different from the array implementation.
void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
Traversing
Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of a stack.
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}