Data Structure Notes 03 - Linked Stack

Linked Stack Data Structure

What is a Stack#

A stack is a type of linear table that follows the Last In First Out (LIFO) principle, where the tail of the table has a special meaning and is referred to as the top of the stack.

Stack Operations#

The most commonly used operations on a stack are push (inserting elements at the tail of the table) and pop (deleting elements from the tail of the table).

Stack|inline

Stack Representation#

A stack can be represented using an array, known as an array stack, or using a linked list, known as a linked stack (discussed in this article). A singly linked list allows insertion and deletion of elements at the head, tail, or any other valid position. If elements can only be inserted and deleted at the tail of a singly linked list, it can be considered as a linked stack. Therefore, we maintain a top pointer on top of the singly linked list.

Linked Stack Representation|inline

Note
The next pointer of each node in the diagram points to the next node, not the next node's pointer field.

Node Definition and Top Pointer of the Stack#

Definition of the structure representing a node of the linked stack:

typedef struct stack_node {
    struct stack_node *next;
    void *data;
} stack_node;

Definition of the structure representing the linked stack:

typedef struct stack {
    struct stack_node *top;
    int length; // represents the height of the stack
} stack;

Note that the top pointer points to a structure representing a node of the stack.

Function List#

Below are the function names used to manipulate the stack, along with their purpose and algorithmic complexity.

Function	Purpose	Algorithmic Complexity
stack_create	Create a new linked stack	O(1)
stack_release	Release the stack and its nodes	O(N)
stack_push	Push an element onto the stack	O(1)
stack_pop	Pop an element from the stack	O(1)
stack_empty	Empty the stack without releasing it	O(N)

Creating a Stack#

/* Create a stack */
stack *stack_create()
{
    stack *stack = (struct stack *)malloc(sizeof(struct stack));
    /* Equivalent syntax:
    stack *s = (stack *)malloc(sizeof(stack)); */
    if (stack == NULL)
        return NULL;
    /* Initialize */
    stack->length = 0;
    stack->top = NULL;
    return stack;
}

Pushing onto the Stack#

/* Push onto the stack */
stack *stack_push(stack *stack, void *data)
{
    /* Create a new node */
    stack_node *node = (struct stack_node *)malloc(sizeof(struct stack_node));
    if (node == NULL)
        return NULL;
    node->data = data;

    /* Insert */
    node->next = stack->top;
    stack->top = node;

    stack->length++;
    return stack;
}

When an element is pushed onto the stack, a new node is created. The insert operation is then performed by setting the successor next of the new node to the top node of the stack, followed by moving the top pointer to point to the new node node. Finally, the height of the stack is incremented by 1.

Push Operation

Popping from the Stack#

/* Pop from the stack */
void *stack_pop(stack *stack)
{
    /* Temporarily save the top node */
    stack_node *curr = stack->top;
    if (curr == NULL)
        return NULL;
    void *data = curr->data;
    stack->top = stack->top->next;

    free(curr);
    stack->length--;
    return data;
}

When popping from the stack, the top node pointer is temporarily saved to perform the release operation before returning the value of the data field of the top node. Then, the top pointer is moved to the next node of the top node. Finally, the temporary saved node is freed, the height of the stack is decremented by 1, and the data is returned, completing the pop operation.

Emptying the Stack#

/* Empty the stack without releasing it */
void stack_empty(stack *stack)
{
    int length = stack->length;
    stack_node *curr, *next;
    curr = stack->top;

    /* Determine the number of times to delete nodes based on the height of the stack */
    while (length--)
    {
        next = curr->next;
        free(curr);
        curr = next;
    }

    stack->length = 0;
    stack->top = NULL;
}

Releasing the Stack#

/* Empty the stack and release it */
void stack_release(stack *stack)
{
    stack_empty(stack);
    free(stack);
}

Testing#

Similarly, we test in the main function.

int main()
{
    char a = 'a';
    char b = 'b';
    char c = 'c';

    /* Create a stack */
    stack *stack = stack_create();

    printf("%p\n", stack_pop(stack));

    /* Push onto the stack */
    stack_push(stack, &a);
    stack_push(stack, &b);
    stack_push(stack, &c);
    /* Pop from the stack */
    while (stack->length > 0)
    {
        printf("%c\n", *(char *)stack_pop(stack));
    }

    /* Push onto the stack */
    stack_push(stack, &a);
    stack_empty(stack);
    printf("%p\n", stack_pop(stack));

    /* Release the stack */
    stack_release(stack);
    return 0;
}

Compile and output:

# gcc -fsanitize=address -fno-omit-frame-pointer -g stack.c && ./a.out
(nil)
c
b
a
(nil)

Complete Code#

For the complete code, please refer to the code listing.
https://github.com/austin2035/learn-data-structures