FOR FREE YEAR SOLVED

# The stack is an abstract data type. It is a linear data structure and has a particular order of performing the operations. 

Generally, the stack uses the LIFO approach i.e. Last In First Out approach. 

# The element that is inserted at the last will be deleted at the first. There are various real-life examples of the stack. 

# The stack of plates in the kitchen can be a very simple and common example of a stack data structure. The plate which is placed at the top (i.e. which is put on the stack at last) will be taken first. 

# The bottom-most plate which has been kept first will remain there and will be taken out at the last. The insertion of any element into the stack is called ‘push’ and the deletion of an element is called ‘pop’.

Here, the array is used to implement the stack data structure. An array is also a linear data structure. First, the maximum number of elements of the stack is taken to check the boundary conditions - overflow or underflow. 

When the stack is full and someone is trying to insert an element into the stack then this condition is known as stack overflow.

Similarly, when the stack is empty and someone is trying to delete an element from the stack then this condition is known as stack underflow.

Let the stack can contain a maximum of 3 elements.

So, the stack can be represented as:

As the stack is implemented here using a linked list, first the head pointer is set to NULL as there is no element in the stack. 

Initially top=-1. 

Now, suppose the first element to be inserted into the stack is 10. Before inserting the ‘top’ will be incremented by 1. The stack will be:

For implementing this using a linked list, first, one node is to be created and the head pointer will point to that node. The linked list will be:

For the second element, the top will be incremented again by 1 and the same process will be followed. Suppose the element to be inserted is 20.

The linked list after inserting the element ‘20’ -

Similarly, the elements can be inserted into the stack as well as the array. When the stack will be full it will show the “stack overflow” error while trying to insert an element.

Now, suppose we want to pop the element from the stack, first the element ‘20’ will be popped out as it was inserted last.

For deleting the element from the linked list, a pointer is pointed at the last element of the list which is considered as ‘top’ of the stack. After that, the connection of that node with the previous node will be removed. The ‘top’ will be decremented by 1.

Now, if we make the address of the node ‘ptr1’ NULL, the link with the pointer ‘ptr’ will be de touched.

The linked list will be:

Here the variable ‘top’ is used to check the overflow and underflow condition of the stack.

INPUT: The elements of the stack
OUTPUT: The stack after pushing or popping the elements

PROCESS:
Step 1: [Defining a structure ‘node’]
	Structure node
		Data part of type ‘integer’
		Address part to store the address of the next node
[End of the structure]
Declaring a global variable ‘head’ of type ‘node’
Declaring a global variable ‘top’ of type integer
Set top<-1

Step 2: [Function ‘push()’]
	If top=n-1 then
		Print "Stack Overflow"
		return
	[End of ‘if’]
	Set p<-new node
	Print "Enter the element to be inserted: "
	Read x
	Set data[p]<-x
	Set next[p]<-NULL
	If head=NULL then
		Set head<-p	
	else
		Set ptr<-head
		While next[ptr]≠NULL repeat
			Set ptr<-next[ptr]
		[End of ‘while’ loop]
		Set next[ptr]<-p
	[End of ‘if’]
	Set top<-top+1
 [End of function ‘push()’]

Step 3: [Function ‘pop()’]
	If top=-1 then
		Print "Stack Underflow"
		return
	[End of ‘if’]
	Set ptr<-head
	While next[ptr]≠NULL repeat
		Set ptr1<-ptr
		Set ptr<-next[ptr]
	[End of ‘while’ loop]
	Set next[ptr1]<-NULL
	Free ptr
	Set top<-top-1
 [End of function ‘pop()’]

Step 4: [Function ‘display()’]
	If top=-1 then
		Print "No Element"
		return
	[End of ‘if’]
	Print "The elements of the stack are: "
	Set ptr<-head
	While ptr≠NULL repeat
		Print data[ptr]
		Set ptr<-next[ptr]
	[End of ‘while’ loop]
 [End of function ‘display()’]

Step 5: [function ‘main()’]
	Print "Enter the number of elements: "
	Read n 
	While 1 repeat 
		Print "1.PUSH 
               2.POP
               3.DISPLAY
               4.EXIT
           Enter the choice: "
		Read ch
		Switch to ch
			case 1- call the function push()
					break
			case 2-call the function pop()
					break
			case 3- call the function display()
					break
			case 4- return
			default- print "Wrong Choice"
		[End of ‘switch case’]
	[End of ‘while’ loop]
[End of function ‘main()’]

Step 6: Stop.