Re: implement stack and queue in C or in asm

Discussion in 'C Programming' started by Pascal J. Bourguignon, Apr 3, 2010.

  1. "io_x" <> 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__
    Pascal J. Bourguignon, Apr 3, 2010
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Russell Warren
    Jun 27, 2006
  2. Kceiw
    Jim Langston
    Mar 14, 2006
  3. asximos

    how to implement stack work as a queue

    asximos, Nov 24, 2008, in forum: C Programming
    Nov 24, 2008
  4. Dr Malcolm McLean

    Re: implement stack and queue in C or in asm

    Dr Malcolm McLean, Apr 4, 2010, in forum: C Programming
    Dr Malcolm McLean
    Apr 4, 2010
  5. Kris

Share This Page