Array Stack

A stack is a linear data structure that follows the last in first out (LIFO) philosophy. This simply means we access elements from the newest to the oldest. The insertion operation of a stack is called a push while the deletion is called a pop. These two operations have a time complexity of O(1). A stack can be implemented either as a resizable array or linked list.

Why would one choose to implement a stack as an array? One would choose to implement a stack as an array for better cache performance. Modern computers use cache to speed up the access of frequently or recently accessed data or instructions; cache works by storing frequently or recently accessed data or instructions. Whenever the CPU needs to load instructions or data from memory it first checks cache. Accessing cache is faster than accessing the main memory. This means whenever a cache miss occurs the CPU spends more resources accessing needed instructions or data.

Accessing an element in an array based stack means the CPU will load as much of that memory region into cache for future accesses because of spatial locality. Spatial locality states that data in closer proximity in memory has a higher probability of being accessed in the future than data farther away in memory. Implementing the stack as an array means we can access numerous elements quicker because the entire memory region may have been loaded into cache during the last access versus that of a linked based stack where each link may be a potential cache miss which is costly.

On the other hand, one would choose to implement a stack as a linked structure because an array based stack maybe fixed in terms of size if it is not implemented as a resizable array and even if it is implemented as a resizable array resizing is expensive. A linked structure is not fixed in terms of size. It grows as along as memory is available.

Our library has a resizable array based stack implementation which can be accessed by including the header file r2_arrstack.h.

Representation

Our array based stack is represented by this structure:

struct r2_arrstack{
        void **data;/*data array*/
        r2_uint64 top;/*position where next element will be inserted*/
        r2_uint64 ncount;/*number of elements*/
        r2_uint64 ssize;/*size of stack*/
        r2_fd fd;/*A callback function to free each item in data array*/; 
        r2_cpy cpy;/*A callback function used to copy each item in data array */
        r2_cmp cmp;/*A comparison callback function used to compare data items in array*/
};

Under no circumstances should the fields data, top, ncount, ssize be accessed or modified.

Creation

struct r2_arrstack *stack = r2_create_arrstack(size, fd, cpy, cmp);

The default and minimum allowable size is 16. To use the default size we pass 0 for the size parameter.

Destruction

r2_destroy_arrstack(stack);

Pushing

r2_arrstack_push(stack, data);

A successful push operation returns TRUE.

Popping

r2_arrstack_pop(stack);

A successful pop operation returns TRUE.

Top of stack

int *data = r2_arrstack_top(stack);
printf("\nThe last number stored on top of the stack is: %d", *data);

Linked Stack

To use our linked stack include the header file r2_stack.h.

Representation

The linked stack is represented by the structure:

struct r2_stack{
        struct r2_stacknode *top;/*top of stack*/
        r2_int64 ssize;/*number of elements in stack*/
        r2_cmp cmp;/*A callback comparison function*/
        r2_cpy cpy;/*A callback copy function*/
        r2_fd fd;/*A callback function to free memory occupied by data*/           
};

Similar to the array stack implementation the fields top and ssize should not be modified or accessed.

Creation

struct r2_stack *stack = r2_create_stack(cmp, cpy, fd);

Destruction

r2_destroy_stack(stack);

Pushing

r2_stack_push(stack, data);

A return value of TRUE means the operation was successful.

Popping

r2_stack_pop(stack);

A return value of TRUE means the operation was successful.

Top of stack

We can retrieve the top of the stack by using the function r2_stack_peek which returns a pointer of type r2_stacknode.

struct r2_stacknode *top = r2_stack_peek(stack);
/*Accessing data*/ 
int *data = top->data;
printf("\nThe last number stored on top of the stack is: %d", *data);