implement stack and queue in C or in asm
in [General Programming]
|
Prev: kernels
Next: ANN: Seed7 Release 2010-04-04
From: io_x on 3 Apr 2010 14:26 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]? 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? than why stack and queue are seen from all one as different data structures? there is a push in the tail and a pop in the tail (stack) but could be a push in the head and a pop in the head too. Buona Pasqua
From: Pascal J. Bourguignon on 3 Apr 2010 15:58 "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); 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). 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)). While a queue is defined as: queue make_queue(); bool queue_empty(queue q); queue queue_enqueue(queue q,int object); int queue_head(queue q); queue queue_dequeue(queue q); with these equations: queue_empty(make_queue()) == true queue_empty(queue_enqueue(q,i)) == false (for all queue q and int i) q0=make_queue() for all k, q_(k+1)=queue_enqueue(q_k,i_k) ==> for all l, queue_head(q_l)=i_0 q0=make_queue() for all k, q_(k+1)=queue_enqueue(q_k,i_k) ==> for all l>0, queue_head(queue_dequeue(q_l))=i_l The time complexity of all the queue operations is O(1). So you can access the first element enqueued in a single operation (O(1)), but to get the last element enqueued, you have to dequeue all the others (O(n)). As you can see, these two abstract data types are quite different. By the way, you could implement a queue using two stacks, keeping the same time complexities, but AFAIK, while you could implement a stack with two queues, you couldn't keep the same time complexities with a finite number of queues. (These are exercises, do implement queue with stacks, and then stack with queues). Now these abstract data types have to be implemented, and for this you can use vectors, lists, or whatever else you fancy. In the case of lists, you can keep pointers to both the head and the tail of the list, and you can use either single linked lists or double-linked lists. Then you can indeed implement an abstract data type where it is possible to remove elements from both ends (and possibly add elements to both ends). But it wouldn't be a stack or a queue anymore, would it? > there is a push in the tail and a pop in the tail =(stack) > but could be > a push in the head and a pop in the head too. In the case of linked lists, you would need double-linked lists to be able to remove from both ends. So you have the following exercises: - define the abstract data types for: - single-linked lists, - double-linked lists, - single-linked circular lists, - double-linked circular lists. In each case, define an abstract data type for the nodes alone (so that we can manipulate the chains of nodes, eg.inserting a node after another, or removing a node after another), and define an abstract data type of the list as a whole (a list "header"), with either a single pointer to a node (the head or the tail), or two pointers to two nodes (the head and the tail). In each case, describe what is possible or not possible to do to the list, starting from the list "header". - implement the queue and stack abstract data type with three different kinds of list abstract data types of your choice, and two different types of node chains. - define an abstract data type for a data structure that can be pushed and poped from both ends. Implement it thrice, using: - a node ADT of your choice (justify), - a list ADT of your choice (justify), - stacks or queues. -- __Pascal Bourguignon__ http://www.informatimago.com
From: Dr Malcolm McLean on 4 Apr 2010 02:17 On 3 Apr, 19:26, "io_x" <a...(a)b.c.invalid> wrote: > > than why stack and queue are seen from all one as > different data structures? > there is a push in the tail and a pop in the tail (stack) > but could be > a push in the head and a pop in the head too. > The obvious way to implement a stack is with a memory buffer which grows in one direction, either upwards or downwards in memory, and with a single "top" index or pointer. The obvious way to implement a queue is with a fixed-size memory buffer which grows from one end and shrinks from the other, eventually looping back on itself in a circle, and with "head" and "tail" indices or pointers. However the details aren't really important. You can implement both with linked lists, for example. The reason we use the structures is because of the algorithms. An algorithm that traverse a tree will naturally use a stack. An algorithm that schedules jobs to be passed to another process will naturally use a queue.
From: io_x on 4 Apr 2010 04:09 "Dr Malcolm McLean" ha scritto nel messaggio > The obvious way to implement a stack is with a memory buffer which > grows in one direction, either upwards or downwards in memory, and > with a single "top" index or pointer. The obvious way to implement a > queue is with a fixed-size memory buffer which grows from one end and > shrinks from the other, eventually looping back on itself in a circle, > and with "head" and "tail" indices or pointers. > However the details aren't really important. the details are important! > You can implement > both with linked lists, for example. The reason we use the structures > is because of the algorithms. An algorithm that traverse a tree will > naturally use a stack. An algorithm that schedules jobs to be passed > to another process will naturally use a queue. >
From: io_x on 4 Apr 2010 04:09
"io_x" <a(a)b.c.invalid> ha scritto nel messaggio news:4bb7863e$0$1108$4fafbaef(a)reader2.news.tin.it... > Xpost[alt.lang.asm,comp.lang.c,comp.programming] > Is there anyone that implemented these queue and stack using > only pointers [no indexes]? > example for write somewhere in queue tail > C: *p=a; ++p; > etc > or asm: > mov [edx], eax > inc edx > etc > or > *r=a|++r it is easy for me doing some error error: or asm: mov [edx], eax add edx, 4 or *r=a|r+=4 > I would like to know only > in your implementation what does should it mean head==tail? |