Introduction

We’ve covered the concepts of a stack and a stack implemented using arrays. Now, let’s explore the implementation of a stack using pointers and discuss why it’s considered a superior approach.

You might be wondering why we need to discuss this alternative when we’ve already looked at stack implementations using arrays. Can’t we just stick to arrays?

The reason for exploring stack implementation with pointers is to address potential limitations we might encounter with array-based implementations, particularly regarding size constraints. By utilizing pointers, we can effectively circumvent such issues, ensuring a more flexible and robust solution for managing data within a stack structure.

Using pointers to implement a stack involves dynamically allocating memory for the stack elements and manipulating pointers to manage the stack structure. This approach is particularly useful when the size of the stack is not known beforehand or when memory efficiency is a concern.

Node Structure

A “node” refers to a fundamental building block used in many data structures, including linked lists, trees, graphs, and more. A node is a structure that contains two main components:

1. Data: This component holds the actual value or element that the node represents. It could be of any data type depending on the application.
2. Next Pointer (or Link): This component is a reference or pointer to the next node in the sequence. It establishes the connection between nodes in the data structure.

These code snippets define a basic node structure in different programming languages:

• C++:

  struct Node {
      Type item;
      Node* next;
  };
  

  In C++, struct is used to define a structure named Node. It contains two members:

  – item: A variable of type Type to store data.
  – next: A pointer to another Node, indicating the next node in the sequence.

• Java:

  class Node {
      Type item;
      Node next;
  }
  

  In Java, class is used to define a class named Node. Similarly, it has two members:

  – item: A variable of type Type to store data.
  – next: An object of type Node, representing the next node in the sequence.

• C#:

  class Node {
      Type item;
      Node next;
  }
  

  This is similar to Java. In C#, class is used to define a class named Node, and it also has two members:

  – item: A variable of type Type to store data.
  – next: An object of type Node, representing the next node in the sequence.

• Python:

  class Node:
      def __init__(self):
          self.item = None
          self.next = None
  

  In Python, a class named Node is defined. The __init__ method is a constructor used to initialize objects of the class. Inside the constructor:

  – self.item is initialized to None, indicating that it stores data.
  – self.next is initialized to None, indicating that it refers to the next node in the sequence.

stackTop

stackTop typically refers to the top element of a stack data structure. In the context of a stack, it is a variable or pointer that points to the topmost element of the stack, or in other words, the most recently added element.

To assign the value of stackTop to the next member of a node:

• C++:
  newNode is a pointer to a node, and stackTop is presumably another pointer to a node. This line assigns the value of stackTop to the next pointer of the newNode, effectively linking newNode to the node pointed to by stackTop.

  newNode->next = stackTop;
  

• Java, C#, Python:
  newNode is an object of type Node, and stackTop is also an object of type Node. This line assigns the reference of the object referred to by stackTop to the next field of the newNode.

  newNode.next = stackTop; // Java and C#
  
  newNode.next = stackTop // Python

To assigns the value of newNode to stackTop:
C++, Java, C#, Python:

stackTop = newNode

stackTop is a pointer to the top element of a stack implemented using pointers or dynamic memory allocation. stackTop = newNode would update stackTop to point to the newly created node newNode. This effectively makes newNode the new top element of the stack.
To creates a copy of stackTop we use the statement:

temp = stackTop

Why do we do that?

Creating a copy of stackTop (temp) allows you to safely manipulate and access the top element of the stack without affecting the original pointer, reference, or value. It provides flexibility and ensures that the original data remains intact for future use.

A Pointer-Base Implementation of the ADT Stack(linked stack) main Functions:

• push(Type newItem)
• pop()
• pop(Type& stackTop)
• getTop()
• display()
• isEmpty()