dynamic_stack.c File Reference

Dynamic Stack, just like Dynamic Array, is a stack data structure whose the length or capacity (maximum number of elements that can be stored) increases or decreases in real time based on the operations (like insertion or deletion) performed on it. More...

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

Include dependency graph for dynamic_stack.c:

Data Structures
struct	DArrayStack
	to verify assumptions made by the program and print a diagnostic message if this assumption is false. More...

Typedefs
typedef struct DArrayStack	DArrayStack
	to verify assumptions made by the program and print a diagnostic message if this assumption is false.

Functions
DArrayStack *	create_stack (int cap)
	Create a Stack object.
DArrayStack *	double_array (DArrayStack *ptr, int cap)
	As this is stack implementation using dynamic array this function will expand the size of the stack by twice as soon as the stack is full.
DArrayStack *	shrink_array (DArrayStack *ptr, int cap)
	As this is stack implementation using dynamic array this function will shrink the size of stack by twice as soon as the stack's capacity and size has significant difference.
int	push (DArrayStack *ptr, int data)
	The push function pushes the element onto the stack.
int	pop (DArrayStack *ptr)
	The pop function to pop an element from the stack.
int	peek (DArrayStack *ptr)
	To retrieve or fetch the first element of the Stack or the element present at the top of the Stack.
int	show_capacity (DArrayStack *ptr)
	To display the current capacity of the stack.
int	isempty (DArrayStack *ptr)
	The function is used to check whether the stack is empty or not and return true or false accordingly.
int	stack_size (DArrayStack *ptr)
	Used to get the size of the Stack or the number of elements present in the Stack.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Dynamic Stack, just like Dynamic Array, is a stack data structure whose the length or capacity (maximum number of elements that can be stored) increases or decreases in real time based on the operations (like insertion or deletion) performed on it.

In this implementation, functions such as PUSH, POP, PEEK, show_capacity, isempty, and stack_size are coded to implement dynamic stack.

Author

SahilK-027

Typedef Documentation

DArrayStack

typedef struct DArrayStack DArrayStack

to verify assumptions made by the program and print a diagnostic message if this assumption is false.

to provide a set of integer types with universally consistent definitions that are operating system-independent for IO operations for including functions involving memory allocation such as malloc

DArrayStack Structure of stack.

Function Documentation

create_stack()

DArrayStack * create_stack

(

int

cap

)

Create a Stack object.

Parameters

cap	Capacity of stack

Returns

DArrayStack* Newly created stack object pointer

{
    DArrayStack *ptr;
    ptr = (DArrayStack *)malloc(sizeof(DArrayStack));
    ptr->capacity = cap;
    ptr->top = -1;
    ptr->arrPtr = (int *)malloc(sizeof(int) * cap);
    printf("\nStack of capacity %d is successfully created.\n", ptr->capacity);
    return (ptr);
}

double_array()

DArrayStack * double_array	(	DArrayStack *	ptr,
		int	cap
	)

As this is stack implementation using dynamic array this function will expand the size of the stack by twice as soon as the stack is full.

Parameters

ptr	Stack pointer
cap	Capacity of stack

Returns

DArrayStack*: Modified stack

{
    int newCap = 2 * cap;
    int *temp;
    temp = (int *)malloc(sizeof(int) * newCap);
    for (int i = 0; i < (ptr->top) + 1; i++)
    {
        temp[i] = ptr->arrPtr[i];
    }
    free(ptr->arrPtr);
    ptr->arrPtr = temp;
    ptr->capacity = newCap;
    return ptr;
}

isempty()

int isempty

(

DArrayStack *

ptr

)

The function is used to check whether the stack is empty or not and return true or false accordingly.

Parameters

ptr	Stack pointer

Returns

int returns 1 -> true OR returns 0 -> false

{
    if (ptr->top == -1)
    {
        return 1;
    }
    return 0;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

{
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

peek()

int peek

(

DArrayStack *

ptr

)

To retrieve or fetch the first element of the Stack or the element present at the top of the Stack.

Parameters

ptr	Stack pointer

Returns

int Top of the stack

{
    if (ptr->top == -1)
    {
        printf("Stack is empty UNDERFLOW \n");
        return -1;
    }
    return ptr->arrPtr[ptr->top];
}

pop()

int pop

(

DArrayStack *

ptr

)

The pop function to pop an element from the stack.

Parameters

ptr	Stack pointer

Returns

int Popped value

{
    if (ptr->top == -1)
    {
        printf("Stack is empty UNDERFLOW \n");
        return -1;
    }
    int ele = ptr->arrPtr[ptr->top];
    ptr->arrPtr[ptr->top] = 0;
    ptr->top = (ptr->top - 1);
    if ((ptr->capacity) % 2 == 0)
    {
        if (ptr->top <= (ptr->capacity / 2) - 1)
        {
            ptr = shrink_array(ptr, ptr->capacity);
        }
    }
    printf("Successfully popped: %d\n", ele);
    return ele;
}

Here is the call graph for this function:

push()

int push	(	DArrayStack *	ptr,
		int	data
	)

The push function pushes the element onto the stack.

Parameters

ptr	Stack pointer
data	Value to be pushed onto stack

Returns

int Position of top pointer

{
    if (ptr->top == (ptr->capacity) - 1)
    {
        ptr = double_array(ptr, ptr->capacity);
        ptr->top++;
        ptr->arrPtr[ptr->top] = data;
    }
    else
    {
        ptr->top++;
        ptr->arrPtr[ptr->top] = data;
    }
    printf("Successfully pushed : %d\n", data);
    return ptr->top;
}

Here is the call graph for this function:

show_capacity()

int show_capacity

(

DArrayStack *

ptr

)

To display the current capacity of the stack.

Parameters

ptr	Stack pointer

Returns

int Current capacity of the stack

{ return ptr->capacity; }

shrink_array()

DArrayStack * shrink_array	(	DArrayStack *	ptr,
		int	cap
	)

As this is stack implementation using dynamic array this function will shrink the size of stack by twice as soon as the stack's capacity and size has significant difference.

Parameters

ptr	Stack pointer
cap	Capacity of stack

Returns

DArrayStack*: Modified stack

{
    int newCap = cap / 2;
    int *temp;
    temp = (int *)malloc(sizeof(int) * newCap);
    for (int i = 0; i < (ptr->top) + 1; i++)
    {
        temp[i] = ptr->arrPtr[i];
    }
    free(ptr->arrPtr);
    ptr->arrPtr = temp;
    ptr->capacity = newCap;
    return ptr;
}

stack_size()

int stack_size

(

DArrayStack *

ptr

)

Used to get the size of the Stack or the number of elements present in the Stack.

Parameters

ptr	Stack pointer

Returns

int size of stack

{ return ptr->top + 1; }

test()

static void test ( void  )

static

Self-test implementations.

Returns

void

{
    DArrayStack *NewStack;
    int capacity = 1;
    NewStack = create_stack(capacity);
    uint64_t arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
 
    printf("\nTesting Empty stack: ");
    assert(stack_size(NewStack) == 0);
    assert(isempty(NewStack) == 1);
    printf("Size of an empty stack is %d\n", stack_size(NewStack));
 
    printf("\nTesting PUSH operation:\n");
    for (int i = 0; i < 12; ++i)
    {
        int topVal = push(NewStack, arr[i]);
        printf("Size: %d, Capacity: %d\n\n", stack_size(NewStack),
               show_capacity(NewStack));
        assert(topVal == i);
        assert(peek(NewStack) == arr[i]);
        assert(stack_size(NewStack) == i + 1);
        assert(isempty(NewStack) == 0);
    }
 
    printf("\nTesting POP operation:\n");
    for (int i = 11; i > -1; --i)
    {
        peek(NewStack);
        assert(peek(NewStack) == arr[i]);
        int ele = pop(NewStack);
        assert(ele == arr[i]);
        assert(stack_size(NewStack) == i);
    }
 
    printf("\nTesting Empty stack size: ");
    assert(stack_size(NewStack) == 0);
    assert(isempty(NewStack) == 1);
    printf("Size of an empty stack is %d\n", stack_size(NewStack));
 
    printf("\nTesting POP operation on empty stack: ");
    assert(pop(NewStack) == -1);
}

Here is the call graph for this function: