Stack implementation using weak linked lists

Stacks are one of the simplest data structures to use and implement. Stacks are a type of list container where elements can only be accessed from one end. The basic operations of stacks include:

  • Push: Insert an element at the end of the container
  • Pop: Retrieve and remove an element at the end of the container
  • Peek: Retrieve an element at the end of the container without removing it

Other operations standard to list containers that a stack might include are:

  • Clear: Remove all elements
  • Size: Get the number of elements in the container
  • Swap: Swap the contents of this container with the contents of another

At a low abstraction level, stacks are used to keep track of nested function calls and recursion. When a function is called, the address of the current function is saved on a stack before jumping to the address of the new function. And when returning from a function, the first address residing on the stack is popped off and used as the returning address to jump back to. In Assembly language, the stack is the primary data structure for manipulating memory. The stack is not only used for keeping track of function calls, but also for storing local variables relative to the current function. This means that if any local variables are allocated on a stack, the current function is responsible for removing those variables from the stack so that the correct return address lies at the end of the stack before returning.

Stacks can be implemented with pretty much any list container. For this post, I’m going to implement it using a weak linked list. Weak linked lists have every element be a separate allocated node. Each node contains the element value and a pointer to the next node. A regular linked list would contain two pointers to the previous and next nodes. Since stacks can only be manipulated from one end, a regular linked list with two pointers per node won’t be necessary.

First, lets define the node structure:

struct _stack_node {
struct _stack_node *next;
char data[0];
};

typedef struct _stack_node stack_node;

That is what a typical weak linked list node looks like. Notice the array of 0 char member. We use this because the size of the element is not known. Remember this node will be dynamically allocated, so the size of the node will be sizeof(struct _stack_node) + sizeof(element). To retrieve the element from this node just cast data as a pointer to that element type and dereference it.

The actual stack data structure will contain a pointer to the next node to pop off and other bookkeeping information:

struct _stack {
stack_node *top;
int count;
int element_size;
};
typedef struct _stack stack;

count will keep track of the number of elements in the stack and element_size is the number of extra bytes to allocate per node to make room for the element value.

This is what the push function might look like:

void stack_push(stack *s, const void *data) {
stack_node *node;
node = (stack_node*)malloc(sizeof(stack_node) + s->element_size);
memcpy(node->data, data, s->element_size);

node->next = s->top;
s->top = node;
++s->count;
}

In English, this function creates a new node and stores the new value in the node. Since this new node is going to be placed at the top of the stack, the next node it points to will be the node that is currently at the top of the stack right now.

Here’s the pop function:

int stack_pop(stack *s, void *data) {
stack_node *next;
if (s->top == NULL) return -1;
memcpy(data, s->top->data, s->element_size);
next = s->top->next;
free(s->top);
s->top = next;
--s->count;
return 0;
}

This function will simply copy the element at the top of the stack to the user’s defined memory location. Then the top of the stack will point to the next node and the current node will be deleted.

If you would like to see more the rest of the code for this stack, visit http://github.com/jakash3/C-Stack/

 

 

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: