Tasnim Zotder

Stack - Make Your Table Plates Stackable

Author: Tasnim Zotder
DSA

Stack Data Structure

First
Second
Third

Before we start, let's imagine a stack of 5 new plates on your table. Now, it's your dinner time, so you need one plate for your main dish. How do you pick your first plate. You will pick the topmost plate, right? Now, you have finished your main dish and you need a plate for your dessert. Again, you will pick the topmost plate, right? Now, your dinner is over and you need to put all the plates back to the stack. How do you do that? You will put the plates back on the stack on top of each other. This is how a stack data structure works.

From the above analogy, we observed that we can only access the topmost element of the stack. Like this when we need to put the plates back to the stack, we can only put the plates on top of each other. This method of accessing the data is called Last In First Out (LIFO) method. This is the basic principle of the stack data structure.

Stack Data Structure

Stack Implementation

Stack can be implemented using array or linked list. Let's see how we can implement stack using linked list. To learn more about linked list, you can read my article on Linked List.

To implement stack using linked list, we need to create two classes - Node and Stack. The Node class will be used to create the nodes of the linked list. The Stack class will be used to create the stack object.

Node Class

The Node class will have two properties - data and next. The data property will store the data of the node and the next property will store the reference to the next node.

class Node {
public:
    int data;
    Node *next;
 
    Node(int data) {
      this->data = data;
      this->next = NULL;
    }
};

Stack Class

The Stack class will have two properties - head and size. The head property will store the reference to the topmost node of the stack and the size property will store the size of the stack. Optionally, we can also have a tail property to store the reference to the last node of the stack.

class Stack {
public:
    Node *head;
    int size;
 
    Stack() {
      this->head = NULL;
      this->size = 0;
    }
};

Stack Operations

Now, we have the basic structure of a stack. Let's see how we can perform the basic operations on the stack. The basic operations on the stack are:

  • Push: This operation is used to add an element to the top of the stack.
  • Pop: This operation is used to remove an element from the top of the stack.
  • Peek: This operation is used to get the topmost element of the stack.
  • isEmpty: This operation is used to check if the stack is empty or not.
  • getSize: This operation is used to get the size of the stack.

Push Operation

Stack - Push Operation

The push operation is used to add an element to the top of the stack.

void push(int data) {
  Node *newNode = new Node(data);
 
  if (this->head == NULL) {
    this->head = newNode;
  } else {
    newNode->next = this->head;
    this->head = newNode;
  }
 
  this->size++;
}

Here goes the explanation:

  • We created a new node with the given data.
  • If the stack is empty, we set the head property of the stack to the new node.
  • If the stack is not empty, we set the next property of the new node to the head property of the stack. Then, we set the head property of the stack to the new node.
  • Finally, we increment the size property of the stack by 1.

Complexity Analysis:

  • Time Complexity: O(1)
  • Space Complexity: O(1)

Pop Operation

Stack - Pop Operation

The pop operation is used to remove an element from the top of the stack.

int pop() {
  if (this->head == NULL) {
    return -1;
  }
 
  int data = this->head->data;
  Node *temp = this->head;
  this->head = this->head->next;
  delete temp;
  this->size--;
 
  return data;
}

Here goes the explanation:

  • If the stack is empty, we return -1.
  • If the stack is not empty, we store the head property of the stack in a temporary variable.
  • Then, we set the head property of the stack to the next property of the head property of the stack.
  • Then, we store the data property of the temporary variable in a variable and delete the temporary variable.
  • Finally, we decrement the size property of the stack by 1 and return the data.

Complexity Analysis:

  • Time Complexity: O(1)
  • Space Complexity: O(1)

Peek Operation

Stack - Peek Operation

The peek operation is used to get the topmost element of the stack.

int peek() {
  if (this->head == NULL) {
    return -1;
  }
 
  return this->head->data;
}

Here goes the explanation:

  • If the stack is empty, we return -1.
  • If the stack is not empty, we return the data property of the head property of the stack.

Complexity Analysis:

  • Time Complexity: O(1)
  • Space Complexity: O(1)

isEmpty Operation

The isEmpty operation is used to check if the stack is empty or not.

bool isEmpty() {
  return this->head == NULL;
}

Here goes the explanation:

  • We return true if the head property of the stack is NULL.
  • We return false if the head property of the stack is not NULL.

Complexity Analysis:

  • Time Complexity: O(1)
  • Space Complexity: O(1)

getSize Operation

The getSize operation is used to get the size of the stack.

int getSize() {
  return this->size;
}

Here goes the explanation:

  • We return the size property of the stack.

Complexity Analysis:

  • Time Complexity: O(1)
  • Space Complexity: O(1)

Now, we have implemented all the basic operations on the stack. Let's see how we can use these operations:

#include <iostream>
using namespace std;
 
class Node {
public:
    int data;
    Node *next;
 
    Node(int data) {
      this->data = data;
      this->next = NULL;
    }
};
 
class Stack {
public:
    Node *head;
    int size;
 
    Stack() {
      this->head = NULL;
      this->size = 0;
    }
 
    void push(int data) {
      Node *newNode = new Node(data);
 
      if (this->head == NULL) {
        this->head = newNode;
      } else {
        newNode->next = this->head;
        this->head = newNode;
      }
 
      this->size++;
    }
 
    int pop() {
      if (this->head == NULL) {
        return -1;
      }
 
      int data = this->head->data;
      Node *temp = this->head;
      this->head = this->head->next;
      delete temp;
      this->size--;
 
      return data;
    }
 
    int peek() {
      if (this->head == NULL) {
        return -1;
      }
 
      return this->head->data;
    }
 
    bool isEmpty() {
      return this->head == NULL;
    }
 
    int getSize() {
      return this->size;
    }
};
 
int main() {
  Stack *stack = new Stack();
 
  stack->push(10);
  stack->push(20);
  stack->push(30);
 
  cout << stack->peek() << endl;
  cout << stack->pop() << endl;
  cout << stack->peek() << endl;
  cout << stack->getSize() << endl;
  cout << stack->isEmpty() << endl;
 
  return 0;
}

Applications of Stack

Stacks are used in many applications. Some of the applications of stacks are:

  • Postfix Evaluation: Stacks are used to evaluate a postfix expression.
  • Prefix Evaluation: Stacks are used to evaluate a prefix expression.
  • Redo-Undo: Stacks are used to implement the redo-undo feature in text editors.
  • Back button in web browsers: Stacks are used to implement the back button in web browsers.
  • Forward and backward feature in music players: Stacks are used to implement the forward and backward feature in music players.
  • Recursive Function Calls: Stacks are used to store the function calls in the memory.
  • Memory Management: Stacks are used to manage the memory in the operating system.

References