Describe how the following program implements the data structure know as a stack
ID: 3833235 • Letter: D
Question
Describe how the following program implements the data structure know as a stack.
// C program for array implementation of stack
#include
#include
#include
// A structure to represent a stack
struct Stack
{
int top;
unsigned capacity;
int* array;
};
// function to create a stack of given capacity. It initializes size of
// stack as 0
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
return stack;
}
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{ return stack->top == stack->capacity - 1; }
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{ return stack->top == -1; }
// Function to add an item to stack. It increases top by 1
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
printf("%d pushed to stack ", item);
}
// Function to remove an item from stack. It decreases top by 1
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
// Driver program to test above functions
int main()
{
struct Stack* stack = createStack(100);
push(stack, 10);
push(stack, 20);
push(stack, 30);
printf("%d popped from stack ", pop(stack));
return 0;
}
Explanation / Answer
// C program for array implementation of stack
//insertion operation is called PUSH operation
//pop() Removing (accessing) an element from the stack.
//The value which is pushed at the last is stored at the top most position.
//Pop removes value from stack.
//The top most value is removed first i.e. LIFO policy.
//other description how the following program implements the data structure(stack) given in comments.
// A structure to represent a stack
struct Stack
{
int top;
unsigned capacity;
int* array;
};
// function to create a stack of given capacity. It initializes size of stack as 0
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
return stack;
}
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{ return stack->top == stack->capacity - 1; }
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{ return stack->top == -1; }
// Function to add an item to stack. It increases top by 1
void push(struct Stack* stack, int item)
{
if (isFull(stack)) //if stack is full then return without adding any element on stack
return;
stack->array[++stack->top] = item;//this will add item on top of the stack and increase the top by 1
printf("%d pushed to stack ", item);
}
// Function to remove an item from stack. It decreases top by 1
int pop(struct Stack* stack)
{
if (isEmpty(stack))//if stack is empty then return
return INT_MIN;
return stack->array[stack->top--];//this will return top of the stack value and decrease the top value by 1
}
// Driver program to test above functions
int main()
{
struct Stack* stack = createStack(100);//this will create structure of size 100 type stack
push(stack, 10); //this will call function push with input argument 10
push(stack, 20);//this will call function push with input argument 20
push(stack, 30);//this will call function push with input argument 30
printf("%d popped from stack ", pop(stack));////this will call function pop with input argument stack
return 0;
}
Output :-
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack