From: Dr Malcolm McLean on
On 4 Apr, 09:09, "io_x" <a...(a)b.c.invalid> wrote:
> "Dr Malcolm McLean"  ha scritto nel messaggio
>
> >     However the details aren't really important.
>
> the details are important!
>
What usually matters is the behaviour and the big O complexity of the
functions. Exactly how they are written is of less importance. Micro-
optimisation can produce very significant speedups, but these vary
from platform to platform, and only make a real difference to the
running time of the program if embedded in a routine which itself
accounts for a large part of the running time of the program - almost
always you find that there is one tight inner loop which dominates
runtime.
From: io_x on

"Pascal J. Bourguignon" <pjb(a)informatimago.com> ha scritto nel messaggio
news:7ypr2gnw8z.fsf(a)informatimago.com...
> "io_x" <a(a)b.c.invalid> writes:
>
>> Xpost[alt.lang.asm,comp.lang.c,comp.programming]
>>
>> It is two days that i write little functions for handle
>> stack and queue [of 32 bits elements,
>> (pointers or unsigned or int of 32 bit)]
>> and they seems to me very good written etc
>>
>> Is there anyone that implemented these queue and stack using
>> only pointers [no indexes]?
>
> Yes. A lot of implementations use only pointers.
>
>> example for write somewhere in queue tail
>> C: *p=a; ++p;
>> etc
>> or asm:
>> mov [edx], eax
>> inc edx
>> etc
>> or
>> *r=a|++r
>>
>> I would like to know only
>> in your implementation what does should it mean head==tail?
>
> It would mean that the stack, or the queue, is empty.
>
>
>> than why stack and queue are seen from all one as
>> different data structures?
>
> This is because they're different abstract data type.
>
> A stack is defined as:
>
> stack make_stack();
> bool stack_empty(stack s);
> stack stack_push(stack s,int object);
> int stack_pop(stack s);

the functions in C or assembly could be:
%define u32 unsigned
int makestack(u32** s);
int stack_empty(u32* s);
int stack_push_tail(u32* s, u32 object);
int stack_pop_tail(u32* object, u32* s);
int stack_push_head(u32* s, u32 object);
int stack_pop_head(u32* object, u32* s);

where s is the stack, the 90% of the above functions can fail

> with these equations:
>
> stack_empty(make_stack()) == true
> stack_empty(stack_push(s,i)) == false (for all stack s and int i).
> i == stack_pop(stack_push(s,i)) (for all stack s and int i).

so i could define the stack-queue something like
u32 *s;
makestack(&s)!=0 => (stack_empty(s)!=0)
Aw,z e u32 (stack_push_tail(s, w)!=0) => (stack_pop_tail(&z, s)!=0 /\ w==z)
Aw,z e u32 (stack_push_head(s, w)!=0) => (stack_pop_head(&z, s)!=0 /\ w==z)


> The time complexity of all the stack operations is O(1).
> But to access the first element pushed, you have to pop all the others
> (O(n)), while you can get the last element in a single pop (O(1)).



From: io_x on

"Pascal J. Bourguignon" <pjb(a)informatimago.com> ha scritto nel messaggio
news:7ypr2gnw8z.fsf(a)informatimago.com...
> "io_x" <a(a)b.c.invalid> writes:
>
>> Xpost[alt.lang.asm,comp.lang.c,comp.programming]
>>
>> It is two days that i write little functions for handle
>> stack and queue [of 32 bits elements,
>> (pointers or unsigned or int of 32 bit)]
>> and they seems to me very good written etc
>>
>> Is there anyone that implemented these queue and stack using
>> only pointers [no indexes]?
>
> Yes. A lot of implementations use only pointers.
>
>> example for write somewhere in queue tail
>> C: *p=a; ++p;
>> etc
>> or asm:
>> mov [edx], eax
>> inc edx
>> etc
>> or
>> *r=a|++r
>>
>> I would like to know only
>> in your implementation what does should it mean head==tail?
>
> It would mean that the stack, or the queue, is empty.
>
>
>> than why stack and queue are seen from all one as
>> different data structures?
>
> This is because they're different abstract data type.
>
> A stack is defined as:
>
> stack make_stack();
> bool stack_empty(stack s);
> stack stack_push(stack s,int object);
> int stack_pop(stack s);

the functions in C or assembly could be:
%define u32 unsigned
int makestack(u32** s);
int stack_empty(u32* s);
int stack_push_tail(u32* s, u32 object);
int stack_pop_tail(u32* object, u32* s);
int stack_push_head(u32* s, u32 object);
int stack_pop_head(u32* object, u32* s);

where s is the stack, the 90% of the above functions can fail

> with these equations:
>
> stack_empty(make_stack()) == true
> stack_empty(stack_push(s,i)) == false (for all stack s and int i).
> i == stack_pop(stack_push(s,i)) (for all stack s and int i).

so i could define the stack-queue something like
u32 *s;
makestack(&s)!=0 => (stack_empty(s)!=0)
Aw,z e u32 (stack_push_tail(s, w)!=0) => (stack_pop_tail(&z, s)!=0 /\ w==z)
Aw,z e u32 (stack_push_head(s, w)!=0) => (stack_pop_head(&z, s)!=0 /\ w==z)


> The time complexity of all the stack operations is O(1).
> But to access the first element pushed, you have to pop all the others
> (O(n)), while you can get the last element in a single pop (O(1)).




From: io_x on

"io_x" <a(a)b.c.invalid> ha scritto nel messaggio
news:4bb85308$0$826$4fafbaef(a)reader5.news.tin.it...
> the functions in C or assembly could be:
> %define u32 unsigned
> int makestack(u32** s);
better
int makestack(u32** s, u32 Nelements);

> int stack_empty(u32* s);
> int stack_push_tail(u32* s, u32 object);
> int stack_pop_tail(u32* object, u32* s);
> int stack_push_head(u32* s, u32 object);
> int stack_pop_head(u32* object, u32* s);
>
> where s is the stack, the 90% of the above functions can fail
>
>> with these equations:
>>
>> stack_empty(make_stack()) == true
>> stack_empty(stack_push(s,i)) == false (for all stack s and int i).
>> i == stack_pop(stack_push(s,i)) (for all stack s and int i).
>
> so i could define the stack-queue something like

u32 *s, v;
Av e u32 makestack(&s, v)!=0 => (stack_empty(s, v)!=0)
> Aw,z e u32 (stack_push_tail(s, w)!=0) => (stack_pop_tail(&z, s)!=0 /\ w==z)
> Aw,z e u32 (stack_push_head(s, w)!=0) => (stack_pop_head(&z, s)!=0 /\ w==z)


From: io_x on
"Dr Malcolm McLean" ha scritto nel messaggio
On 4 Apr, 09:09, "io_x" <a...(a)b.c.invalid> wrote:
>> "Dr Malcolm McLean" ha scritto nel messaggio
>>
>> > However the details aren't really important.
>>
>> the details are important!
>>
>What usually matters is the behaviour and the big O complexity of the
>functions. Exactly how they are written is of less importance. Micro-
>optimisation can produce very significant speedups, but these vary
>from platform to platform, and only make a real difference to the
>running time of the program if embedded in a routine which itself
>accounts for a large part of the running time of the program - almost
>always you find that there is one tight inner loop which dominates
>runtime.

i not speak of "Microoptimisation" i speak of what something has to be;
it is one way of see the puzle where all piece goes in the right place;

it is one conceptual way of see the stack where all goes well.
Here i see the above with my implementation (all goes well) but it
is different from what i see in the books.

Possibly i make wrong in debugging my 3 places stack-queue? :)