implement stack and queue in C or in asm
in [General Programming]
|
Prev: kernels
Next: ANN: Seed7 Release 2010-04-04
From: Dr Malcolm McLean on 4 Apr 2010 04:29 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 4 Apr 2010 04:59 "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 4 Apr 2010 05:00 "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 4 Apr 2010 05:21 "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 4 Apr 2010 13:00
"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? :) |