Dynamic Array Representation of Stack

Dynamic Array representation of Stack is better implementation of stack as compare to the simple array representation.In Dynamic Array representation,we can grow the stack size as per our requirements.Initially
we can assign the array size=1 or more ,but when we need more space to store the DataElement ,then we can double the stack size when stack is full.
we can say that Dynamic array representation of Stack is the Dynamic representation, and In this representation Overflow situation can not occur.

• first we have to initialize the array with specific size limitation or just size 1.
• Declare top variables : top.
• initialize the top by -1,-1 indicates that Stack is empty.

Push & Pop (Insertion & Delete Operation)

Working Process of Push and Pop Operation is explained physically in below figure :

• We start the Push operation from left to right or from index-0 to index (n-1).and maintain one top variable to indicate the stack pointer.
• When Stack is full and we want to Push more DataElements ,then we will use the advantage of Dynamic Array and double the Array Size to make Stack size as double.

Code Implementation

                              /*Structure Implementations*/
#include <stdio.h>
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<malloc.h>
#include<conio.h>
#define SIMPLE_ARRAY_SIZE 2   // Define the Array Size
struct DynamicArrayStack       // Structure for controlling the front ,rear,QueueSize  and DataElement of Queue.
{
	int top;           // pointing to stack pointer 
	int size;          // Stack Size
	int *DynamicArray;  // Array to store the DataElement.
};
struct DynamicArrayStack* CreateDynamicArrayStack()  //Function to Create an Stack and initilize all the required Variables
{
	struct DynamicArrayStack* NewStack = (struct DynamicArrayStack*)malloc(sizeof(struct DynamicArrayStack));
	if (!NewStack)       // if Memory is not initilized for NewStack
		return NULL;
	NewStack->top = -1;
	NewStack->size = SIMPLE_ARRAY_SIZE;
	NewStack->DynamicArray = (int *)malloc(sizeof(int)*SIMPLE_ARRAY_SIZE);
	if (!NewStack->DynamicArray)  //if Array is not initilized
		return NULL;
	else
		return NewStack;
}
bool DoubleArraySize(struct DynamicArrayStack* Q)
{
	Q->size = Q->size * 2; // Double the Array Size..
	//Re-Allocation of Memory by double Size..
	Q->DynamicArray = (int*)realloc(Q->DynamicArray, Q->size * sizeof(int));
	if (!Q->DynamicArray)
		return false;
	else
		return true;
}
bool IsFullStack(struct DynamicArrayStack* Q) //Method for checking the Full state of Stack
{
	bool IsDouble = false;
	if (Q->top == Q->size - 1) //if Stack is full then return true else false
	{
		IsDouble = DoubleArraySize(Q);  // Double the Array Size when Queue is Full.
		if (IsDouble)
		{
			printf("\nQueue size has been doubled Now....\n");
			return !IsDouble;
		}
	}
	return IsDouble; //if Queue is full then return true else false
}
void Push(struct DynamicArrayStack* Q, int DataElement)   //Method of pushing the DataElement into Stack
{
	if (!IsFullStack(Q))              // check the Overflow condition of Stack.
	{
		Q->top++;
		Q->DynamicArray[Q->top] = DataElement;
		printf("DataElement %d is Pushed into the stack :\n", DataElement);
	}
	else
		printf("Stack is in Overflow Condition......\n");
}
bool IsEmptyStack(struct DynamicArrayStack* Q)  //Method for checking the Full state of Stack
{
	return Q->top == -1;
}
void Pop(struct DynamicArrayStack* Q) //Method of popping the DataElement from Stack
{
	if (!IsEmptyStack(Q))
	{
		printf("DataElement %d is Popped from Stack :\n", Q->DynamicArray[Q->top]);
		Q->DynamicArray[Q->top] = NULL;
		Q->top--;
	}
}
int main()
{
	int choice, DataElement,ChoosePushPop;
	struct DynamicArrayStack* MyStack = CreateDynamicArrayStack(); //Create one Stack
	if (!MyStack)
		printf("Sorry Your Stack is not ready....\n");
	else
	{
		do
		{
			printf("1 : for Push Operation\n");
			printf("2 : for Pop Operation\n");
			printf("Press 1 or 2 --- : ");
			std::cin >> ChoosePushPop;
			switch (ChoosePushPop)
			{
			case 1:
			{
				do
				{
					printf("Enter the data for Pushing :");
					std::cin >> DataElement;
					Push(MyStack, DataElement);
					printf("\nPress 0 for more Push Operation :");
					std::cin >> choice;
				} while (choice == 0);
				break;
			}
			case 2:
			{
				do
				{
					Pop(MyStack);
					printf("\nPress 0 for more Pop Operation :");
					std::cin >> choice;
				} while (choice == 0);
				break;
			}
			}
		} while (ChoosePushPop == 1 || ChoosePushPop == 2);
	}
	printf("Data Element after Push and Pop Operation---> ");
	while (MyStack->top >=0)
	{
		printf("%d ", MyStack->DynamicArray[MyStack->top]);
		MyStack->top--;
	}
	_getch();
	return 0;
}

Time & Space Complexity

• Push Operation Time Complexity will be O(1).
• Pop Operation Time Complexity will be O(1).
• DoubleArraySize Time Complexity will be O(1).
• IsEmptyStack Time Complexity will be O(1).
• IsFullStack Time Complexity will be O(1).
• Space Complexity will be O(n).