Implementing a Stack Data Structure in C
A stack is a linear data structure commonly used in programming. It is a restricted linear list where insertion and deletion can only occur at one end, known as the 'top'. The opposite end is called the 'bottom'. Stacks follow the 'last in, first out' (LIFO) principle, making them useful for various applications.
Operations on a stack include:
- Pushing a element onto the stack
- Popping an element from the stack
- Initializing the stack
- Checking if the stack is empty
- Accessing the top element of the stack
The following header file defines the stack structure and function declarations:
#include <stdbool.h>
#ifndef C_STACK_H
#define C_STACK_H
#define STACK_EMPTY -1
typedef struct {
int capacity;
int top;
int *data;
} Stack, *StackPtr;
void initStack(StackPtr stackPtr, int cap);
void pushStack(StackPtr stackPtr, int item);
int popStack(StackPtr stackPtr);
int peekStack(StackPtr stackPtr);
static int *reExpansion(StackPtr stackPtr);
void clearStack(StackPtr stackPtr);
bool isFull(StackPtr stackPtr);
bool isEmpty(StackPtr stackPtr);
#endif //C_STACK_H
The implementation file contains the function definitions:
#include "stack.h"
#include "../sorting_algorithms/sort_tools.h"
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
void initStack(StackPtr stackPtr, int cap) {
stackPtr->top = STACK_EMPTY;
stackPtr->capacity = cap;
stackPtr->data = getArrayPointer(cap);
}
void pushStack(StackPtr stackPtr, int item) {
if (isFull(stackPtr)) {
printf("this stack is full!!!");
}
stackPtr->data[++stackPtr->top] = item;
}
int popStack(StackPtr stackPtr) {
int ret;
if (isEmpty(stackPtr)) {
printf("stack is empty!!!");
ret = STACK_EMPTY;
} else {
ret = stackPtr->data[stackPtr->top--];
}
return ret;
}
int peekStack(StackPtr stackPtr) {
int ret;
if (isEmpty(stackPtr)) {
printf("stack is empty!!!");
ret = STACK_EMPTY;
} else {
ret = stackPtr->data[stackPtr->top];
}
return ret;
}
static int *reExpansion(StackPtr stackPtr) {
stackPtr->capacity *= 2;
int *newData = getArrayPointer(stackPtr->capacity);
for (int i = 0; i < stackPtr->capacity / 2; ++i) {
newData[i] = (stackPtr->data)[i];
}
free(stackPtr->data);
return stackPtr->data = newData;
}
void clearStack(StackPtr stackPtr) {
stackPtr->top = STACK_EMPTY;
}
bool isFull(StackPtr stackPtr) {
return stackPtr->top + 1 == stackPtr->capacity;
}
bool isEmpty(StackPtr stackPtr) {
return stackPtr->top == STACK_EMPTY;
}