Explain Array implementation of Stack?

Array implementation of Stack

In array implementation, the stack is formed by using the array. All the operations regarding the stack are performed using arrays. Lets see how each operation can be implemented on the stack using array data structure.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push operation involves following two steps.

1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new element at the top of the stack.

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.

Algorithm:

1. begin   
2.     if top = n then stack full   
3.     top = top + 1  
4.     stack (top) : = item;  
5. end   

Time Complexity : o(1)

implementation of push algorithm in C language

1. void push (int val,int n) //n is size of the stack   
2. {  
3.     if (top == n )   
4.     printf("\n Overflow");   
5.     else   
6.     {  
7.     top = top +1;   
8.     stack[top] = val;   
9.     }   
10. }   

Deletion of an element from a stack (Pop operation)

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.

Algorithm :

1. begin   
2.     if top = 0 then stack empty;   
3.     item := stack(top);  
4.     top = top ? 1;  
5. end;    

Time Complexity : o(1)

Implementation of POP algorithm using C language

1. int pop ()  
2. {   
3.     if(top == -1)   
4.     {  
5.         printf("Underflow");  
6.         return 0;  
7.     }  
8.     else  
9.     {  
10.         return stack[top - - ];   
11.     }    
12. }   

Visiting each element of the stack (Peek operation)

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.

Algorithm :

PEEK (STACK, TOP)

1. Begin   
2.     if top = -1 then stack empty    
3.     item = stack[top]   
4.     return item  
5. End    

Time complexity: o(n)

Implementation of Peek algorithm in C language

1. int peek()  
2. {  
3.     if (top == -1)   
4.     {  
5.         printf("Underflow");  
6.         return 0;   
7.     }  
8.     else  
9.     {  
10.         return stack [top];  
11.     }  
12. }  

C program

1. #include <stdio.h>   
2. int stack[100],i,j,choice=0,n,top=-1;  
3. void push();  
4. void pop();  
5. void show();  
6. void main ()  
7. {  
8.       
9.     printf("Enter the number of elements in the stack ");   
10.     scanf("%d",&n);  
11.     printf("*********Stack operations using array*********");  
12.   
13. printf("\n----------------------------------------------\n");  
14.     while(choice != 4)  
15.     {  
16.         printf("Chose one from the below options...\n");  
17.         printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");  
18.         printf("\n Enter your choice \n");        
19.         scanf("%d",&choice);  
20.         switch(choice)  
21.         {  
22.             case 1:  
23.             {   
24.                 push();  
25.                 break;  
26.             }  
27.             case 2:  
28.             {  
29.                 pop();  
30.                 break;  
31.             }  
32.             case 3:  
33.             {  
34.                 show();  
35.                 break;  
36.             }  
37.             case 4:   
38.             {  
39.                 printf("Exiting....");  
40.                 break;   
41.             }  
42.             default:  
43.             {  
44.                 printf("Please Enter valid choice ");  
45.             }   
46.         };  
47.     }  
48. }   
49.   
50. void push ()  
51. {  
52.     int val;      
53.     if (top == n )   
54.     printf("\n Overflow");   
55.     else   
56.     {  
57.         printf("Enter the value?");  
58.         scanf("%d",&val);         
59.         top = top +1;   
60.         stack[top] = val;   
61.     }   
62. }   
63.   
64. void pop ()   
65. {   
66.     if(top == -1)   
67.     printf("Underflow");  
68.     else  
69.     top = top -1;   
70. }   
71. void show()  
72. {  
73.     for (i=top;i>=0;i--)  
74.     {  
75.         printf("%d\n",stack[i]);  
76.     }  
77.     if(top == -1)   
78.     {  
79.         printf("Stack is empty");  
80.     }  
81. }  

Java Program

1. import java.util.Scanner;  
2. class Stack   
3. {  
4.     int top;   
5.     int maxsize = 10;  
6.     int[] arr = new int[maxsize];  
7.       
8.       
9.     boolean isEmpty()  
10.     {  
11.         return (top < 0);  
12.     }  
13.     Stack()  
14.     {  
15.         top = -1;  
16.     }  
17.     boolean push (Scanner sc)  
18.     {  
19.         if(top == maxsize-1)  
20.         {  
21.             System.out.println("Overflow !!");  
22.             return false;  
23.         }  
24.         else   
25.         {  
26.             System.out.println("Enter Value");  
27.             int val = sc.nextInt();  
28.             top++;  
29.             arr[top]=val;  
30.             System.out.println("Item pushed");  
31.             return true;  
32.         }  
33.     }  
34.     boolean pop ()  
35.     {  
36.         if (top == -1)  
37.         {  
38.             System.out.println("Underflow !!");  
39.             return false;  
40.         }  
41.         else   
42.         {  
43.             top --;   
44.             System.out.println("Item popped");  
45.             return true;  
46.         }  
47.     }  
48.     void display ()  
49.     {  
50.         System.out.println("Printing stack elements .....");  
51.         for(int i = top; i>=0;i--)  
52.         {  
53.             System.out.println(arr[i]);  
54.         }  
55.     }  
56. }  
57. public class Stack_Operations {  
58. public static void main(String[] args) {  
59.     int choice=0;  
60.     Scanner sc = new Scanner(System.in);  
61.     Stack s = new Stack();  
62.     System.out.println("*********Stack operations using array*********\n");  
63.     System.out.println("\n------------------------------------------------\n");  
64.     while(choice != 4)  
65.     {  
66.         System.out.println("\nChose one from the below options...\n");  
67.         System.out.println("\n1.Push\n2.Pop\n3.Show\n4.Exit");  
68.         System.out.println("\n Enter your choice \n");        
69.         choice = sc.nextInt();  
70.         switch(choice)  
71.         {  
72.             case 1:  
73.             {   
74.                 s.push(sc);  
75.                 break;  
76.             }  
77.             case 2:  
78.             {  
79.                 s.pop();  
80.                 break;  
81.             }  
82.             case 3:  
83.             {  
84.                 s.display();  
85.                 break;  
86.             }  
87.             case 4:   
88.             {  
89.                 System.out.println("Exiting....");  
90.                 System.exit(0);  
91.                 break;   
92.             }  
93.             default:  
94.             {  
95.                 System.out.println("Please Enter valid choice ");  
96.             }   
97.         };  
98.     }  
99. }  
100. }  

C# Program

1. using System;  
2.   
3. public class Stack  
4. {  
5.     int top;  
6.     int maxsize=10;  
7.     int[] arr = new int[10];  
8.     public static void Main()  
9.     {  
10.     Stack st = new Stack();  
11.     st.top=-1;  
12.     int choice=0;  
13.     Console.WriteLine("*********Stack operations using array*********");  
14.     Console.WriteLine("\n----------------------------------------------\n");  
15.     while(choice != 4)  
16.     {  
17.         Console.WriteLine("Chose one from the below options...\n");  
18.         Console.WriteLine("\n1.Push\n2.Pop\n3.Show\n4.Exit");  
19.         Console.WriteLine("\n Enter your choice \n");         
20.         choice = Convert.ToInt32(Console.ReadLine());  
21.         switch(choice)  
22.         {  
23.             case 1:  
24.             {   
25.                 st.push();  
26.                 break;  
27.             }  
28.             case 2:  
29.             {  
30.                 st.pop();  
31.                 break;  
32.             }  
33.             case 3:  
34.             {  
35.                 st.show();  
36.                 break;  
37.             }  
38.             case 4:   
39.             {  
40.             Console.WriteLine("Exiting....");  
41.                 break;   
42.             }  
43.             default:  
44.             {  
45.                 Console.WriteLine("Please Enter valid choice ");  
46.                 break;  
47.             }   
48.         };  
49.     }  
50. }   
51.   
52. Boolean push ()  
53. {  
54.     int val;      
55.     if(top == maxsize-1)   
56.     {  
57.           
58.         Console.WriteLine("\n Overflow");  
59.         return false;  
60.     }  
61.     else   
62.     {  
63.         Console.WriteLine("Enter the value?");  
64.         val = Convert.ToInt32(Console.ReadLine());        
65.         top = top +1;   
66.         arr[top] = val;  
67.         Console.WriteLine("Item pushed");  
68.         return true;  
69.     }   
70. }   
71.   
72. Boolean pop ()   
73. {   
74.     if (top == -1)   
75.     {  
76.         Console.WriteLine("Underflow");  
77.         return false;  
78.     }  
79.       
80.     else  
81.       
82.     {  
83.         top = top -1;  
84.         Console.WriteLine("Item popped");  
85.         return true;  
86.     }  
87. }   
88. void show()  
89. {  
90.       
91.     for (int i=top;i>=0;i--)  
92.     {  
93.         Console.WriteLine(arr[i]);  
94.     }  
95.     if(top == -1)   
96.     {  
97.         Console.WriteLine("Stack is empty");  
98.     }  
99. }  
100. }