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.
In array implementation, the stack is formed by using the array. All the operations regarding the stack are performed using arrays
Adding an element into the top of the stack is referred to as push operation. Push operation involves following two steps.
Stack is overflown when we try to insert an element into a completely filled stack therefore, our main function must always avoid stack overflow condition.
begin
if top = n then stack full
top = top + 1
stack (top) : = item;
end
Deletion of an element from the top of the stack is called pop operation. The value of the variable top will be incremented by 1 whenever an item is deleted from the stack. The top most element of the stack is stored in an another variable
and then the top is decremented by 1. the operation returns the deleted value that was stored in another variable as the result.
The underflow condition occurs when we try to delete an element from an already empty stack.
begin
if top = 0 then stack empty;
item := stack(top);
top = top - 1;
end;
Peek operation involves returning the element which is present at the top of the stack without deleting it. Underflow condition can occur if we try to return the top element in an already empty stack.
Begin
if top = -1 then stack empty
item = stack[top]
return item
End
Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap
is not enough to create a node.
The top most node in the stack always contains null in its address field.
Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list implementation is different from that of an array implementation. In order to push an element onto the stack, the following steps are involved.
Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked list implementation of stack is different from that in the array implementation. In order to pop an element from the stack, we need to follow the following steps :
Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of stack. For this purpose, we need to follow the following steps.