I have to implement stac in Prolog, but WITHOUT using list. Each element of stack should point to before element.
Is there possible to do it? Could I define rules in runtime program? ( like: element('foo','bar'). where foo is content of element end bar is pointer to another?
views:
67answers:
2
+1
A:
Pointer in Stack? I think you have the definition mixed up. I think you mean linked list.
Linked list is a data structure where one element is pointing to next element, resulting in very flexible growth and shrinkage of data.
Stack is data structure that utilizes last in first out.
And yes stack can be written without list, and so can linked list, Array list is less versatile as linked list but none the less, it has most of linked list features.
Ankiov Spetsnaz
2010-06-04 22:19:36
... but in Stack , element has to have pointer to another element too! Stack on arrays is pointless so I meant Stack as linked list http://en.wikipedia.org/wiki/Stack_(data_structure)#Implementation
Rick
2010-06-04 22:30:38
if you make it so that next index is next element, it won't be a problem. And stack in it's nature is in array format. Having a pointer in stack is pointless.But if you really want to make a stack where it has a pointer to next element, you can do it yes, although efficiency of it is questionable.many ways to do it, but since i'm a mathmatical guy, I would have odd number as element and even number index as a pointer to next index or next element.Or you can make entirly new object with iterator.
Ankiov Spetsnaz
2010-06-04 22:37:34
@AnkiovSpetsnaz: "And stack in it's nature is in array format." Says who? Singly linked lists work perfectly well as stacks.
sepp2k
2010-06-04 23:41:35
Microsoft's OS stack implementation is clearly a stack... hence the smashing the stack attack. If my memory serves me correct all OS stack implementations are array. And yes, stack works perfectly with linked list. Motor scooter's engine works perfectly with racing car too, but it doesn't mean it's recommended. Hypothetically, if we need 1 byte for data and 1 byte for pointer, in linked list format we would need 2 bytes for each data entry, while as array, you would only need 1 bytes since no need of pointer. Thus memory efficacy of array stack is twice the linked list stack.
Ankiov Spetsnaz
2010-06-05 21:27:24
+1
A:
So what is the problem? Your question is already the answer. Your 'bar' should contain element(X,Y) or some kind of bottom.
stack_empty(bottom).
stack_push(S, X, element(X, S)).
revlist_push(S0, [], S0).
revlist_push(S0, [X|T], S):-
stack_push(S0, X, S1),
revlist_push(S1, T, S).
revlist_pop(S0, []):- stack_empty(S0). % bottom of stack
revlist_pop(S0, [X|T]):-
stack_push(S1, X, S0), % pop - is reverse push
revlist_pop(S1, T).
revlist(L0, L):-
stack_empty(S0),
revlist_push(S0, L0, S),
revlist_pop(S, L).
Actually lists in such languages like Prolog usually represented by recursive data. cons(a, cons(b, cons(c, nil))) or simply [a | [b | [c | [] ]]].
ony
2010-06-05 05:36:07