Home | | Object Oriented Programming and Data Structures | Give linked list implementation of stack operation

# Give linked list implementation of stack operation

Linked List Implementation of Stacks: the PUSH operation It’s very similar to the insertion operation in a dynamic singly linked list.

Give linked list implementation of stack operation.

Linked List Implementation of Stacks: the PUSH operation It’s very similar to the insertion operation in a dynamic singly linked list. The only difference is that here you'll add the new element only at the end of the list, which means addition can happen only from the TOP. Since a dynamic list is used for the stack, the Stack is also dynamic, means it has no prior upper limit set. So, we don't have to check for the Overflow condition at all!

In Step [1] we create the new element to be pushed to the Stack.

In Step [2] the TOP most element is made to point to our newly created element.

In Step [3] the TOP is moved and made to point to the last element in the stack, which is our newly added element.

Linked List Implementation of Stacks: the POP Operation

This is again very similar to the deletion operation in any Linked List, but you can only delete from the end of the list and only one at a time; and that makes it a stack. Here, we'll have a list pointer, "target", which will be pointing to the last but one element in the List (stack). Every time we POP, the TOP most element will be deleted and "target" will be made as the TOP most element.

In step[1] we got the "target" pointing to the last but one node. In step[2] we freed the TOP most element.

In step[3] we made the "target" node as our TOP most element.

Supposing you have only one element left in the Stack, then we won't make use of "target" rather we'll take help of our "bottom" pointer. See how...

Algorithm:

·        Step-1: If the Stack is empty then give an alert message "Stack Underflow" and quit; or else proceed

·        Step-2: If there is only one element left go to step-3 or else step-4

·        Step-3: Free that element and make the "stack", "top" and "bottom" pointers point to NULL and quit

·        Step-4: Make "target" point to just one element before the TOP; free the TOP most element;

make "target" as your TOP most element

Implementation:

struct node

{

int nodeval;

struct node *next;

}

struct node *stack = NULL; /*stack is initially empty*/

struct node *top = stack;

main()

{

int newvalue, delval;

..

push(newvalue);

..

delval = pop(); /*POP returns the deleted value from the stack*/

}

int pop( )

{

int pop_val = 0;

struct node *target = stack; if(stack == NULL) /*step-1*/ cout<<"Stack Underflow"; else

{

if(top == bottom) /*step-2*/

{

pop_val = top -> nodeval; /*step-3*/ delete top;

stack = NULL;

top = bottom = stack;

}

else /*step-4*/

{

while(target->next != top) target = target ->next; pop_val = top->nodeval;

delete top; top = target;

target ->next = NULL;

}

}

return(pop_val);

}

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Object Oriented Programming and Data Structure : Linear Data Structures : Give linked list implementation of stack operation |