Hot Topics
Data Structure
Stack Using Doubly Linked List
Intution:
We know stack follow LIFO principle.A node of doubly linked list holds the address of previous node,data of that node and the address of next node.So when the stack is empty and we are inserting the first node we have to point the previous part of node to NULL.The consequent nodes will store the address of previous node.Top will store the address of the last node inserted in stack.
Algorithm
1.Create a class whose data members contains previous pointer which holds the address of previous node,data and next pointer which holds the address of next node.
2.push():To push the node into stack we might have two cases:
Case 1:When the stack is empty Create a node and add data to it. Point the previous pointer and the next pointer to NULL as it is the first ever node inserted into the stack.
Case 2:When the stack has at least one node in it Add data to the node. Assign the previous pointer to the top of earlier node inserted in stack and next pointer to NULL. Point the last node inserted in stack using top pointer.
3.pop():
Case 1:When there is only one node present in stack Remove that node and point the top node to NULL
Case 2:When there is more than one node present To remove the last node we need to point the next pointer of the second last node in stack to NULL and assign the second last node as the top node.
4.top():The top node holds the address of the last entered node in stack.
5.display():Take a pointer at the starting node and let it traverse until it reaches NULL.
Here is the code:
#include
using namespace std;
// creating a node of doubly linked list
struct Node
{
struct Node *next;
int data;
struct Node *prev;
};
Node *top = NULL;
// checking if stack is empty
bool isEmpty()
{
// the top pointing to NULL means stack is empty
if (top == NULL)
return true;
return false;
}
// getting the top most element in stack
void topElement()
{
if (isEmpty())
cout <<”Stack is empty” << endl;
/*when there is atleast one element present then we can get that
element as top element of stack*/
else
cout <<”The top element of stack is ”<data <data = data;
// when the stack is empty we are inserting the first node in stack
if (isEmpty())
{
// the prev and next part of node will have NULL in it
temp->prev = NULL;
temp->next = NULL;
// reassigning top to the node we inserted
top = temp;
}
// when there is atleast one node present in stack
else
{
temp->next = top;
top->prev = temp;
temp->prev = NULL;
top = temp;
}
}
void pop()
{
// creating a new node and attaching a pointer to it
struct Node *temp = new Node();
// when the stack is empty we can’t delete anything
if (isEmpty())
cout <<”Stack is empty” <next == NULL && top->prev == NULL)
{
temp = top;
top = NULL;
delete (top);
}
// removing a node when more than one node present in stack
else
{
temp = top;
top = top->next;
top->prev = NULL;
delete (temp);
}
}
// display the elements in stack
void display()
{
// attaching a pointer to the top
struct Node *curr = top;
cout <<”Elements in stack are”
// iterating through elements in stack until it reaches NULL
while (curr != NULL)
{
cout <data <next;
}
cout << endl;
}
int main()
{
push(1);
push(2);
push(3);
push(4);
push(5);
display();
topElement();
pop();
display();
pop();
display();
topElement();
return 0;
}
Output:
Elements in stack are 5 4 3 2 1
The top element of stack is 5
Elements in stack are 4 3 2 1
Elements in stack are 3 2 1
The top element of stack is 3
Automata Fixing