Stack Implementation in C

Today i gonna show you a simple example of stack implementation in C. The stack is a very common data structure used in programs.

"In computer science, a stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added."

Ok, but talk is cheap. Show me the code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <stdio.h> #include <malloc.h> #define MAX 50 // Maximum size of array int index = 0; // Index of values // Stack data structure typedef struct{ int value; }Structure, *Pointer; // Initializes the stack void initialize(Pointer stack[]){ for (int i = 0; i < MAX; ++i){   stack[i] = NULL; } } // Push a value on the stack void push(Pointer stack[], int value){ Pointer temp = (Pointer) malloc( sizeof(Structure) ); // Allocates memory temp->value = value; // Puts the value on the structure stack[index] = temp; // Puts the new structure on the stack index++; } // Delete a value from the stack void pop(Pointer stack[]){ stack[index] = NULL; index--; } // Shows the stack void show(Pointer stack[]){ printf("STACK : "); for (int i = 0; i < index; ++i){   printf("[%d]-", stack[i]->value); } printf("\n"); } int main(){ Pointer STACK[MAX]; initialize(STACK); push(STACK, 15); push(STACK, 55); push(STACK, 80); push(STACK, 99); push(STACK, 43); show(STACK); pop(STACK); show(STACK); pop(STACK); show(STACK); pop(STACK); show(STACK); return 0; }

If you have any questions or suggestions, please leave your comment.

Sequential Search with Sentinel

Sentinel value is a way to improve the speed of sequential search. In traditional sequential search we need to test if the value is the key we are searching, however, in the sequential search with sentinel we put the value in the array end, therefore, the value is always found.

At the end we just need to test if the value of the 'index' variable is the last position of the array, if is that true, then, the value was not found, and the method returns -1.

Take a look at the example below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def SequentialSearch(value, array): for x in xrange(0, len(array)):   if array[x] == value:     return x return -1 def SentinelSearch(value, array): array.append(value) # Puts the value at the end of the array index = 0 while array[index] != value: # While the value is different   index += 1 array.pop() # Removes the value at the end of the array if index == len(array)-1: # If the 'index' variable is the last position of the array, returns -1   return -1 return index # Else, returns the position of the value on the array array = [1, 4, 5, 2, 42, 34, 54, 98, 89, 78, 67] print SequentialSearch(54, array) print SentinelSearch(98, array)

I hope you enjoyed it.
Any questions just comment.