Stack implementation using Arrays in C

Stack data structure using arrays

A stack is a data structure which allows insertion and removal of elements only at the top. Think of it as a stack of plates in a kitchen sink. You can only add at the top (push) and when you want to remove them you must remove each one from the top, one at a time (pop).

stack

So, a data structure to be considered a stack it must support the following features:
1. Initialize the stack
2. Find if it’s empty or not
3. Determine if the stack is full or not
4. Push at the top
5. Peek at the node at the top
6. Pop the node at the top

We are going to implement it in C using this struct as a base element:

struct Stack {
	int c[size]; //write a number here instead of "size", a global variable or #define size 10 just below the include statements
	int top;
};
Initialization

We use a *pointer to a struct in order to modify it’s data. See here more exactly why.

void initializeStack(Stack* s) {
	s->top = -1;
}
Finding if it’s empty

If s->top is -1 this means is still empty (just initialized) so it will return true. Otherwise it will return false.

bool isEmpty(Stack* s) {
	return (s->top == -1);
}
Finding if it’s full

To see if it’s full we check if the top is equal to array’s size minus one (because arrays starts at zero, so max element in array of 5 is array[4]).

bool isFull(Stack* s) {
	return (s->top == size - 1);
}
Push operation

We check if the stack is full using our function, then if not, we increment the top (s->top is no longer -1 is 0 now). So s->c[s->top] means set c[0] inside of s struct to value item

void push(Stack* s, int item) {
	if (isFull(s)) {
		printf("Cannot push, the stack is full.\n");
		return;
	}
	s->top++;
	s->c[s->top] = item;
}
Peek at the top element

If the stack is not empty we return the value that stands at the top of the stack.

int peek(Stack *s) {
	if (!isEmpty(s)) {
		return s->c[s->top];
	} else {
		printf("Stack is empty!\n");
		return -1;
	}
}
Pop the top element

To pop an element we check if the stack is not empty then we retrieve the element at the top (just as we did when we peeked) and assign it to a variable which we return. We decrement the top so the next push operation will be put in the place of the currently removed item.

int pop(Stack* s) {
	int data;
	if (isEmpty(s)) {
		printf("Cannot pop, the stack is empty.\n");
		return NULL;
	}
	data = s->c[s->top];
	s->top--;
	return data;
}
Stack test
void main() {
	Stack stack;
	int data;

	initializeStack(&stack);
	
	push(&stack, 1);
	push(&stack, 2);
	push(&stack, 3);
	push(&stack, 4);
	push(&stack, 5);
	push(&stack, 6);
	push(&stack, 7);

	data = pop(&stack);
	printf("Popped element is: %d\n", data);
	printf("Now top element is: %d\n", peek(&stack));
	
	printf("\n");

	printf("Popped element is: %d\n", pop(&stack));
	printf("Now top element is: %d\n", peek(&stack));
}

Output:

Popped element is: 7
Now top element is: 6

Popped element is: 6
Now top element is: 5

We popped the last element (7), this means it’s removed from the stack. Then we peeked at the top element which is 6 (note this does not remove the element). Then we pop again so we get 6. This time 6 is actually removed so the top element of the stack is 5.

FacebookTwitterLinkedin