"io_x" <(E-Mail Removed)> 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