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);
}
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.