Dynamic stacks using C language.

Credits

What Will I Learn?

• Create a dynamic stack in c language.
• Create a node.
• Add a node to the stack.
• Extract a node to the stack.
• Destroy the stack and its nodes.

Requirements

• PC (Laptop or Desktop)
• Dev-C++ (C/C++ IDE)

Difficulty

• Intermediate

Tutorial Contents

• Pointers

A pointer is a variable that contains the memory address of a variable. Pointers can be used to reference and manipulate data structures, to reference dynamically assigned memory blocks and to provide the passage of arguments by references in function calls.

• Structs

A struct in C is a composite data type declaration that defines a physically grouped list of variables to be placed under one name in a block of memory, allowing the different variables to be accessed via a single pointer, or the struct declared name which returns the same address.

• Stack

Is an ordered list or data structure that allows you to store and retrieve data, the access mode to its elements is of type LIFO (Last In, First Out). This structure is applied in many cases in the area of information technology due to its simplicity and ability to respond to numerous processes.

In the following image we will see a diagram of a stack.

Credits

Implementation

• Structures definition:

First we define two structures, one for the stack nodes and other for the stack itself. The structure of the stack nodes needs to have all the attributes desired, in this case, we only want a number because we have to create a stack of entire numbers. The nodes also need a pointer to the prev node (the element that is below the actual node). The prev pointer of the first node that was added to the stack always points to NULL.

The structure of the stack needs only one pointer, one to the upper node of the stack. This is because we want to add and extract nodes at the end of the stack with the Last In First Out principle (LIFO)

---

typedef struct node_str{

int number;

struct node_str* prev;

}node_t;

typedef node_t* node;

typedef struct stack_str{

node first; //top node

}stack_t;

typedef stack_t* stack;

---

We will be working with pointers because we have to use dynamic memory (the size of a stack used to be unkonwn). That's why we create the pointer types of the structures defined above.

• Creating a node

This function reserves the memory space to the node n and assigns the number that we want to add. Remember that the prev pointer of the first node always points to NULL.

---

node new_node(int num){

node n;

n=(node)malloc(sizeof(node_t));

n->number = num;

n->prev = NULL;

return n;

}

---

• Creating a Stack

This function reserves the memory space to the stack s and assigns NULL to the first pointer because a new stack is empty so it doesn't have nodes. The The pointer first points to the top node of the stack.

---

stack new_stack(){

stack s;

s=(stack)malloc(sizeof(stack_t));

s->first = NULL;

return s;

}

---

• Adding a node

This function adds a number to the stack. So inside it, we create a node with the number num and we place that node above the top node. Remember that if the stack is empty, first points to NULL.

---

void add_stack_node(stack s , int num)
{

node n = new_node(num);

n->prev = s->first;

s->first = n;

}

---

• Extracting a node

This function extracts a number to the stack.

• If the first node pointer of the stack points to NULL, means that the stack is empty, so we don't extract any node.
• If it doesn't point to NULL, we assing the first node to an auxiliary variable because we are going to lose the reference to that node.
• Then we change the first pointer to the prev node of the stack.
• We save the node's information into the variable n and free the node's allocated memory. It is important to save the value before losing the reference of the pointer.
• Finally the node extracted is returned so we can use it's attributes for whatever we want.

---

node_t extract_stack_node(stack s)
{

node aux;

node_t n;

if (s->first != NULL)
{

aux = s->first;

s->first = s->first->prev;

n = *aux;

free(aux);

}

return n;

}

---

• Destroying a stack

Before the program's end, it is necessary to destroy the stack and its nodes and liberate the allocated memory. So we use the extract_stack_node function to liberate all the nodes and print the numbers (this is not necessary, it is just for example). Finally we liberate the memory allocated for the stack.

---

void destroy_stack(stack s)
{

node_t n;

while(s->first != NULL)

{

n = extract_stack_node(s);

printf("%d\n", n.number);

}

free(s);

}

---

Now let's show how the queue works.

Work Result

First, let’s create a stack with 4 numbers (1-4). First we have to reserve the memory to the stack, so we use the new_stack() function and save the result into a stack data type variable. Then we add the elements with the add_stack_node() function (this function reserves the memory for all individual nodes). Finally we are going to extract two elements with the extract_stack_node() function from the stack before destroying it.

Code of the main function.

---

int main()
{
stack s = new_stack(); //Reserving memory

add_stack_node(s,1); //add element

add_stack_node(s,2); //add element

add_stack_node(s,3); //add element

add_stack_node(s,4); //add element

extract_stack_node(s); //Remove element

extract_stack_node(s); //Remove element

printf("Final Stack\n");

destroy_stack(s); //Liberate all allocated memory

return 0;

}

---

the final result for this test is as follows:

We see that the elements of the stack were extracted in the reverse order to which they were added. it just has the elements 2 and 1 because 4 and 3 were extracted (in that order).

Full Code

#include 
#include 

typedef struct node_str
{
    int number;
    struct node_str* prev;
    
}node_t;

typedef node_t* node;

typedef struct stack_str
{
    node first;             //top node
    
}stack_t;

typedef stack_t* stack;

node new_node(int num)
{
    node n;
    n=(node)malloc(sizeof(node_t));
    n->number = num;
    n->prev   = NULL;
    return n;
}

stack new_stack()
{
    stack s;
    s=(stack)malloc(sizeof(stack_t));
    s->first = NULL;
    return s;
} 

void add_stack_node(stack s , int num)
{
    node n = new_node(num);
    n->prev = s->first;
    s->first = n;
}

node_t extract_stack_node(stack s)
{
    node aux;
    node_t n;

    if (s->first != NULL)
    {
        aux = s->first;
        s->first = s->first->prev;
        n = *aux;
        free(aux);
    }
    return n;
}

void destroy_stack(stack s)
{
    node_t n;
    while(s->first != NULL)
    {
        n = extract_stack_node(s);
        printf("%d\n", n.number);
    }
    free(s);
}

int main()
{
    stack s = new_stack();//Reserving memory
    add_stack_node(s,1);  //add element
    add_stack_node(s,2);  //add element
    add_stack_node(s,3);  //add element
    add_stack_node(s,4);  //add element
    extract_stack_node(s); //Remove element
    extract_stack_node(s); //Remove element
    printf("Final Stack\n");
    destroy_stack(s);     //Liberate all allocated memory
    return 0;
}

try to run the code and start to learn.

Curriculum

• Tutorial 1
• Tutorial 2

---

Posted on Utopian.io - Rewarding Open Source Contributors

---