Home | Projects | Notes > Data Structures & Algorithms > Stacks

Stacks

Introduction

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements are added (push) and removed (pop) only from the top of the stack. It can be implemented using arrays, linked lists, or other containers, and is widely used in function call management, undo operations, and parsing expressions.

Pros:

• Simple and Fast: O(1) time for push and pop operations.

• Easy to Implement: Can be built using arrays or linked lists.

• Useful in Algorithms: Backtracking, recursion, depth-first search (DFS), etc.

• Memory-Efficient with Linked List: Grows dynamically without resizing.

Cons:

• Limited Access: Only the top element is accessible; no random access.

• Fixed Size (Array-Based): Requires resizing or limits capacity.

• Not Ideal for Search or Arbitrary Removal: Inefficient for operations other than LIFO.

Compared to Queues:

• Better: For backtracking, recursion, nested structure parsing.

• Worse: When first-in elements must be accessed or preserved.

Implementation (C++)

Header (stack.hpp)

30
1
#ifndef STACK_HPP
2
#define STACK_HPP
3

4
class node
5
{
6
public:
7
    node(int val) : data(val), p_next(nullptr) {}
8

9
    int data;
10
    node *p_next;
11
};
12

13
class stack
14
{
15
public:
16
    stack();
17
    ~stack();
18
    void push(const int val);
19
    void pop();
20
    int top() const;
21
    bool empty() const;
22
    int size() const;
23
    void clear();
24

25
private:
26
    node *p_top;
27
    int cnt;
28
};
29

30
#endif

Source (stack.cpp)

69
1
#include "stack.hpp"
2
#include <stdexcept>
3

4
stack::stack()
5
    : p_top(nullptr), cnt(0)
6
{
7
    // Do nothing
8
}
9

10
stack::~stack()
11
{
12
    while (!empty())
13
    {
14
        pop();
15
    }
16
}
17

18
void stack::push(const int val)
19
{
20
    node *p_new = new node(val);
21
    p_new->p_next = p_top;
22
    p_top = p_new;
23
    ++cnt;
24
}
25

26
void stack::pop()
27
{
28
    if (empty())
29
    {
30
        throw std::runtime_error("Stack underflow");
31
    }
32

33
    node *p_del = p_top;
34
    p_top = p_top->p_next;
35
    delete p_del;
36
    --cnt;
37
}
38

39
int stack::top() const
40
{
41
    if (empty())
42
    {
43
        throw std::runtime_error("Stack is empty");
44
    }
45

46
    return p_top->data;
47
}
48

49
bool stack::empty() const
50
{
51
    return 0 == cnt;
52
}
53

54
int stack::size() const
55
{
56
    return cnt;
57
}
58

59
void stack::clear()
60
{
61
    while (nullptr != p_top)
62
    {
63
        node *p_del = p_top;
64
        p_top = p_top->p_next;
65
        delete p_del;
66
    }
67

68
    cnt = 0;
69
}

Test Driver

22
1
#include <iostream>
2
#include "stack.hpp"
3

4
int main(int argc, char *argv[])
5
{
6
    stack s;
7

8
    s.push(1);
9
    s.push(2);
10
    s.push(3);
11
    s.push(4);
12
    s.push(5);
13
    
14
    std::cout << s.top() << std::endl;      // 5
15
    std::cout << s.size() << std::endl;     // 5
16
    std::cout << s.empty() << std::endl;    // 0
17

18
    s.clear();
19
    std::cout << s.size() << std::endl;     // 0
20

21
    return 0;
22
}

4
1
5
2
5
3
0
4
0

Stack Using Singly-Linked List (C)

Interface

27
1
#ifndef STACK_H
2
#define STACK_H
3

4
#include <stdbool.h>
5

6
typedef struct node
7
{
8
    int data;
9
    struct node *p_next;
10
} node;
11

12
typedef struct
13
{
14
    node *p_top;
15
    int cnt;
16
} stack;
17

18
// Public interface
19
void stack_init(stack *s);
20
void stack_push(stack *s, const int val);
21
void stack_pop(stack *s);
22
int stack_top(const stack *s);
23
bool stack_empty(const stack *s);
24
int stack_size(const stack *s);
25
void stack_clear(stack *s);
26

27
#endif

Implementation

68
1
#include "stack.h"
2
#include "stdio.h"
3
#include "stdlib.h"
4

5
void stack_init(stack *s)
6
{
7
    s->p_top = NULL;
8
    s->cnt = 0;
9
}
10

11
void stack_push(stack *s, const int val)
12
{
13
    node *p_new = (node *)malloc(sizeof(node));
14

15
    if (!p_new)
16
    {
17
        fprintf(stderr, "Failed to allocate memory for new node\n");    
18
        exit(EXIT_FAILURE);
19
    }
20

21
    p_new->data = val;
22
    p_new->p_next = s->p_top;
23
    s->p_top = p_new;
24
    s->cnt++;
25
}
26

27
void stack_pop(stack *s)
28
{
29
    if (stack_empty(s))
30
    {
31
        fprintf(stderr, "Stack underflow\n");
32
        exit(EXIT_FAILURE);
33
    }
34

35
    node *p_del = s->p_top;
36
    s->p_top = s->p_top->p_next;
37
    free(p_del);
38
    s->cnt--;
39
}
40

41
int stack_top(const stack *s)
42
{
43
    if (stack_empty(s))
44
    {
45
        fprintf(stderr, "Stack is empty\n");
46
        exit(EXIT_FAILURE);
47
    }
48

49
    return s->p_top->data;
50
}
51

52
bool stack_empty(const stack *s)
53
{
54
    return 0 == s->cnt;
55
}
56

57
int stack_size(const stack *s)
58
{
59
    return s->cnt;
60
}
61

62
void stack_clear(stack *s)
63
{
64
    while (s->p_top)
65
    {
66
        stack_pop(s);
67
    }
68
}

Test Driver

7
1
5
2
0
3
5
4
4
5
4
6
1
7
0