This is again very
similar to deletion in any Linked List, but you can only delete from the
end of the list and that too, 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
C 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);
..
push(newvalue);
..
delval = pop();
..
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*/
printf("Stack
Underflow");
else
{
if(top == bottom) /*step-2*/
{
pop_val =
top -> nodeval; /*step-3*/
free(top);
stack =
NULL;
top =
bottom = stack;
}
else /*step-4*/
{
while(target->next != top) target = target ->next;
pop_val =
top->nodeval;
free(top);
top =
target;
target
->next = NULL;
}
}
return(pop_val);
}
Note:-
Although, the algorithm for the POP operation should remain same
irrespective of the implementation techniques but I've deliberately
changed it a bit to make the implementation easier. Don't forget to
include the "alloc.h" file.
Related Operations:
Concept
Array Implementation - Push() and Pop()
Linked List Implementation - Push()
and Pop()
Application of Stacks
|
