Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: implement stack and queue in C or in asm

Thread Tools

Re: implement stack and queue in C or in asm

Pascal J. Bourguignon
Posts: n/a
"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)

for all k, q_(k+1)=queue_enqueue(q_k,i_k)
==> for all l, queue_head(q_l)=i_0

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__
Reply With Quote

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Program blocked in Queue.Queue.get and Queue.Queue.put Kris Python 0 01-04-2012 03:46 PM
Re: implement stack and queue in C or in asm Dr Malcolm McLean C Programming 1 04-04-2010 08:29 AM
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
how to implement stack work as a queue asximos C Programming 0 11-24-2008 07:49 AM
Is Queue.Queue.queue.clear() thread-safe? Russell Warren Python 4 06-27-2006 03:03 PM