Here is my implemetation of stack with linkedlist
STACK using linked list
STACK-EMPTY:
if L.head == NIL
return True
else return False
PUSH(x):
x.next = L.head
if L.head != NIL
L.head.prev = x
L.head = x
x.prev = NIL
POP():
x = L.head
L.head = x.next
x.next.prev = L.head
return x
would you validate this? how to improve ?
thanks
You can improvement the consistency of your data structure:
prev of the list head is always NILnext and prev set to NILTaking 1. in account your POP has an inconsistency which can be source of errors: When you pop an element the prev of the head is the head itself, when you push an element the prev of the head is NIL.
Try this...
Definitions:
S.top is a pointer to some node of type X at the top of the stackX is a node having two pointers, top and baseX.top points to the next node toward the top of the stack.X.base points to the next node toward the base of the stack (bottom) First initialize the stack top pointer:
STACK-INITIAL:
S.top = NIL
return true // Never fails
Test for empty stack:
STACK-EMPTY:
return (S.top == NIL)
Push node x on stack:
PUSH(x):
x.top = NIL // Top of stack, therfore top is NIL
x.base = S.top // base is previous top
S.top = x // x is now top of stack
return true
Pop and return top of stack (this is the only 'interesting' part):
POP():
x = S.top // Top node on stack (could be NIL)
if S.top != NIL // Check in case stack was empty
S.top = x.base // New top = next node toward base
x.base = NIL // Disconnect x from stack
if S.top != NIL // Is stack now empty?
S.top.top = NIL // No, set top node's top pointer to NIL
return x // x could be NIL if stack was empty
Something to think about... I used a double linked list above because
it looked like that is what you were using. However, you only need a
single linked list where the links point to the base of the stack.
Notice that the x.top pointers in the above algorithm are pretty much
useless (set but never referenced). As long as you keep track of the stack top (S.top) the only thing
you need to do is trace back down the stack during POP operations.
Response to comments
When an element is poped off of the stack, all of its associated pointers should be set to NIL. This is because it is no longer part of the stack so should not point to any stack elements. I added that bit to my original answer (see above).
In a similar manner, the new top of stack element (unless the stack becomes empty)
needs to have its pointer to the element above it
set to NIL (since the element above it was removed).
In my example that is what the S.top.top = NIL
stuff was all about (S.top points to the top stack element so S.top.top is the
top pointer of that element). I think you would do the same with x.next.prev = NIL,
assuming x is the element you POPed and is not NIL itself. In your pseudocode it looks
like x.next.prev = L.head would leave the prev pointer of the top of stack element pointing to itself
since L.head was set to x.next (the new top of stack just before that).
Finally, I question why would use a double linked list to implement a stack, only a single linked list with pointers to the next element below it are required
