C Program to Implement Two Stacks in a Single Array

«
»
This C Program Implements two Stacks using a Single Array & Check for Overflow & Underflow. A Stack is a linear data structure in which a data item is inserted and deleted at one record. A stack is called a Last In First Out (LIFO) structure. Because the data item inserted last is the data item deleted first from the stack.

To implement two stacks in one array, there can be two methods.

First is to divide the array in to two equal parts and then give one half two each stack. But this method wastes space.

So a better way is to let the two stacks to push elements by comparing tops of each other, and not up to one half of the array.

Push and Pop functions of both stack in the following code has their Time Complexity as O(1). They take constant time.

Print is O(n), where n is the number of elements in the stack.

advertisement
advertisement

The program has an array of size 10. 6 values are pushed in stack 1 and 4 in two. All conditions are being checked.

Here is source code of the C Program to Implement two Stacks using a Single Array & Check for Overflow & Underflow. The C program is successfully compiled and run on gcc-4.3.2 on a Linux system. The program output is also shown below.

  1. //This is a C Program to Implement two Stacks using a Single Array & Check for Overflow & Underflow
  2. #include <stdio.h>
  3. #define SIZE 10
  4.  
  5.  
  6. int ar[SIZE];
  7. int top1 = -1;
  8. int top2 = SIZE;
  9.  
  10. //Functions to push data
  11. void push_stack1 (int data)
  12. {
  13.   if (top1 < top2 - 1)
  14.   {
  15.     ar[++top1] = data;
  16.   }
  17.   else
  18.   {
  19.     printf ("Stack Full! Cannot Push\n");
  20.   }
  21. }
  22. void push_stack2 (int data)
  23. {
  24.   if (top1 < top2 - 1)
  25.   {
  26.     ar[--top2] = data; 
  27.   }
  28.   else
  29.   {
  30.     printf ("Stack Full! Cannot Push\n");
  31.   }
  32. }
  33.  
  34. //Functions to pop data
  35. void pop_stack1 ()
  36. {
  37.   if (top1 >= 0)
  38.   {
  39.     int popped_value = ar[top1--];
  40.     printf ("%d is being popped from Stack 1\n", popped_value);
  41.   }
  42.   else
  43.   {
  44.     printf ("Stack Empty! Cannot Pop\n");
  45.   }
  46. }
  47. void pop_stack2 ()
  48. {
  49.   if (top2 < SIZE)
  50.   {
  51.     int popped_value = ar[top2++];
  52.     printf ("%d is being popped from Stack 2\n", popped_value);
  53.   }
  54.   else
  55.   {
  56.     printf ("Stack Empty! Cannot Pop\n");
  57.   }
  58. }
  59.  
  60. //Functions to Print Stack 1 and Stack 2
  61. void print_stack1 ()
  62. {
  63.   int i;
  64.   for (i = top1; i >= 0; --i)
  65.   {
  66.     printf ("%d ", ar[i]);
  67.   }
  68.   printf ("\n");
  69. }
  70. void print_stack2 ()
  71. {
  72.   int i;
  73.   for (i = top2; i < SIZE; ++i)
  74.   {
  75.     printf ("%d ", ar[i]);
  76.   }
  77.   printf ("\n");
  78. }
  79.  
  80. int main()
  81. {
  82.   int ar[SIZE];
  83.   int i;
  84.   int num_of_ele;
  85.  
  86.   printf ("We can push a total of 10 values\n");
  87.  
  88.   //Number of elements pushed in stack 1 is 6
  89.   //Number of elements pushed in stack 2 is 4
  90.  
  91.   for (i = 1; i <= 6; ++i)
  92.   {
  93.     push_stack1 (i);
  94.     printf ("Value Pushed in Stack 1 is %d\n", i);
  95.   }
  96.   for (i = 1; i <= 4; ++i)
  97.   {
  98.     push_stack2 (i);
  99.     printf ("Value Pushed in Stack 2 is %d\n", i);
  100.   }
  101.  
  102.   //Print Both Stacks
  103.   print_stack1 ();
  104.   print_stack2 ();
  105.  
  106.   //Pushing on Stack Full
  107.   printf ("Pushing Value in Stack 1 is %d\n", 11);
  108.   push_stack1 (11);
  109.  
  110.   //Popping All Elements From Stack 1
  111.   num_of_ele = top1 + 1;
  112.   while (num_of_ele)
  113.   {
  114.     pop_stack1 ();
  115.     --num_of_ele;
  116.   }
  117.  
  118.   //Trying to Pop From Empty Stack
  119.   pop_stack1 ();
  120.  
  121.   return 0;
  122. }

Output :

gcc TwoStacksSingleArray.c
./a.out
We can push a total of 10 values
Value Pushed in Stack 1 is 1
Value Pushed in Stack 1 is 2
Value Pushed in Stack 1 is 3
Value Pushed in Stack 1 is 4
Value Pushed in Stack 1 is 5
Value Pushed in Stack 1 is 6
Value Pushed in Stack 2 is 1
Value Pushed in Stack 2 is 2
Value Pushed in Stack 2 is 3
Value Pushed in Stack 2 is 4
6 5 4 3 2 1 
4 3 2 1 
Pushing Value in Stack 1 is 11
Stack Full! Cannot Push
6 is being popped from Stack 1
5 is being popped from Stack 1
4 is being popped from Stack 1
3 is being popped from Stack 1
2 is being popped from Stack 1
1 is being popped from Stack 1
Stack Empty! Cannot Pop

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.