Md. Jubaer Mahmud Sarker -Implementing a Stack using Linked List in C++
Md.Jubaer Mahmud Sarker ?
CS student ?? | Python ?? | Django ??? | Odoo ? | C++ ?? |
Title: Implementing a Stack using Linked List in C++
Introduction:
In computer science, a stack is a fundamental data structure that follows the Last In, First Out (LIFO) principle. One way to implement a stack is by using linked lists, and in this article, we will explore the implementation of a stack in C++ using a doubly linked list.
Understanding the Stack and Linked List:
A stack is a collection of elements with two main operations: push (adding an element to the top) and pop (removing the top element). Linked lists are dynamic data structures that consist of nodes, each containing data and a reference to the next node (and optionally, the previous node in the case of doubly linked lists).
Implementation of Stack using Doubly Linked List:
Let's examine a C++ implementation of a stack using a doubly linked list based on the provided code example:
```cpp
#include <iostream>
using namespace std;
class Node
{
public:
int val;
Node *next;
Node *prev;
Node(int val)
{
this->val = val;
this->next = nullptr;
this->prev = nullptr;
}
};
class myStack
{
public:
Node *head = nullptr;
Node *tail = nullptr;
int sz = 0;
void push(int val)
{
sz++;
Node *newNode = new Node(val);
if (head == nullptr)
{
head = newNode;
tail = newNode;
return;
}
newNode->prev = tail;
tail->next = newNode;
tail = tail->next;
}
void pop()
{
if (sz > 0)
{
sz--;
Node *deleteNode = tail;
tail = tail->prev;
if (tail == nullptr)
{
领英推荐
head = nullptr;
}
else
{
tail->next = nullptr;
}
delete deleteNode;
}
}
int top()
{
if (sz > 0)
return tail->val;
else
return -1; // Indicate an empty stack, you may choose a different way to handle this case
}
int size()
{
return sz;
}
bool empty()
{
return sz == 0;
}
};
int main()
{
myStack st;
int n;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter the elements:" << endl;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
st.push(x);
}
cout << "Elements from the top of the stack:" << endl;
while (!st.empty())
{
cout << st.top() << endl;
st.pop();
}
return 0;
}
```
Explanation:
1. Node Class: Defines a basic node structure with integer value (`val`), a pointer to the next node (`next`), and a pointer to the previous node (`prev`).
2. myStack Class: Implements the stack using a doubly linked list. It includes methods for push, pop, top, size, and empty.
3. Main Function: Demonstrates the usage of the stack by taking user input to push elements onto the stack and then printing the elements from the top of the stack while popping them off.
Conclusion:
Implementing a stack using a linked list, whether singly or doubly linked, provides a flexible and efficient way to manage data. Understanding the principles behind this implementation is crucial for building a solid foundation in data structures and algorithms. The presented C++ code serves as a practical example of how to implement a stack using a doubly linked list.