Prev: peter-bochs-debugger is a GUI debugger for bochs
Next: entry point of lib.so
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?



 |  Next  |  Last
Pages: 1 2
Prev: peter-bochs-debugger is a GUI debugger for bochs
Next: entry point of lib.so