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

Stacks

Stack Using Singly-Linked List (C++)

• push() and pop() operations are designed to be done on the head of the list since both of their time complexity is O(1).

Interface

xxxxxxxxxx
39
1
//==============================================================================
2
// File     : stack.h
3
// Brief    : Interface for Stack using Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : Jun 3, 2023
6
//==============================================================================
7

8
#ifndef STACK_H
9
#define STACK_H
10

11
// Class for stack (using singly-linked list) nodes
12
class Node
13
{
14
public:
15
    int value;
16
    Node *next;
17

18
    Node(int value);                    // Constructor
19
};
20

21
// Class for stacks (using singly-linked list)
22
class Stack
23
{
24
public:    
25
    // Public interface
26
    Stack(int value);       // Constructor  
27
    void push(int value);   // Inserts a node into the top of stack
28
    int pop(void);          // Deletes a node from the top of stack
29
    int getTop(void);       // Returns the value of the top of stack
30
    int getHeight(void);    // Returns the number of nodes in the stack
31
    void printStack(void);  // Prints all nodes in the stack
32
    ~Stack();               // Destructor
33

34
private:
35
    Node *top;              // Pointer to top of stack
36
    int height;             // Number of nodes in the stack
37
};
38

39
#endif

Implementation

xxxxxxxxxx
115
1
//==============================================================================
2
// File     : stack.cpp
3
// Brief    : Implementation of Stack using Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : Jun 3, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include "stack.h"
10
#include <cstdlib>      // EXIT_FAILURE
11

12
using namespace std;
13

14
//------------------------------------------------------------------------------
15
// Implementation of Node class interface
16
//------------------------------------------------------------------------------
17

18
// Constructor
19
// T = O(1)
20
Node::Node(int value)
21
{
22
    this->value = value;
23
    next = nullptr;
24
}
25

26
//------------------------------------------------------------------------------
27
// Implementation of Stack (using singly-linked list) class interface
28
//------------------------------------------------------------------------------
29

30
// Constructor
31
// T = O(1)
32
Stack::Stack(int value)
33
{
34
    Node *newNode = new Node(value);
35
    top = newNode;
36
    height = 1;
37
}
38

39
// Inserts a node into the top of stack
40
// T = O(1)
41
void Stack::push(int value)
42
{
43
    Node *newNode = new Node(value);
44

45
    // Push a node into a (empty or non-empty) stack
46
    newNode->next = top;
47
    top = newNode;
48
    height++;
49
}
50

51
// Deletes a node from the top of stack
52
// T = O(1)
53
int Stack::pop(void)
54
{
55
    // Do not allow pop operation on an empty stack
56
    if (length == 0)
57
    {
58
        cout << "ERROR: Cannot pop from an empty stack. Terminating!" << endl;
59
        exit(EXIT_FAILURE);
60
    }
61

62
    Node *delNode = top;
63
    int poppedValue = top->value;
64
    top = top->next;
65
    delete delNode;
66
    height--;
67

68
    return poppedValue;
69
}
70

71
// Returns the value of the top of stack
72
// T = O(1)
73
int Stack::getTop(void)
74
{
75
    return top->value;
76
}
77

78
// Returns the number of nodes in the stack
79
// T = O(1)
80
int Stack::getHeight(void)
81
{
82
    return height;
83
}
84

85
// Prints all nodes in the stack
86
// T = O(n)
87
void Stack::printStack(void)
88
{
89
    Node *temp = top;
90

91
    while (temp)
92
    {
93
        cout << temp->value << " ";
94
        temp = temp->next;
95
    }
96

97
    cout << endl;
98
}
99

100
// Destructor
101
// T = O(n)
102
Stack::~Stack(void)
103
{
104
    // top, height will be destroyed by default, but the nodes will not.
105
    // So, make sure to delete them manually in the destructor.
106

107
    Node *delNode = top;
108

109
    while (top)
110
    {
111
        top = top->next;
112
        delete delNode;
113
        delNode = top;
114
    }
115
}

Test Driver

xxxxxxxxxx
40
1
//==============================================================================
2
// File     : main.cpp
3
// Brief    : Test driver for Stack using Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : Jun 3, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include "stack.h"
10

11
using namespace std;
12

13
int main(int argc, char *argv[])
14
{
15
    // Create a stack
16
    Stack *s = new Stack(4);
17
    
18
    // Push nodes to stack
19
    s->push(3);
20
    s->push(2);
21
    s->push(1);
22

23
    // Print stack information
24
    cout << "Top: " << s->getTop() << endl;         // 1
25
    cout << "Height: " << s->getHeight() << endl;   // 4
26
    cout << "Stack elements: "; s->printStack();    // 1 2 3 4
27
    
28
    cout << endl;
29
    
30
    // Pop nodes from stack
31
    s->pop();
32
    s->pop();
33

34
    // Print stack information
35
    cout << "Top: " << s->getTop() << endl;         // 3
36
    cout << "Height: " << s->getHeight() << endl;   // 2
37
    cout << "Stack elements: "; s->printStack();    // 3 4
38

39
    return 0;
40
}

xxxxxxxxxx
7
1
Top: 1
2
Height: 4
3
Stack elements: 1 2 3 4 
4

5
Top: 3
6
Height: 2
7
Stack elements: 3 4