Thread: Stacks

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    4

    Stacks

    Can I post a book problem that I am confused with on this forum? It's driving me in circles for a correct answer??

  2. #2
    Registered User
    Join Date
    Feb 2006
    Posts
    155
    try posting it and also what r your thoughts on it so far.

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    4
    In this question you are going to define the pop() function for a stack ADT, given that you only have a FIFO Queue to work with. The push() operation consists of simply doing an enqueue() operation on the queue. Please explain in words and pseudo code, an algorithm for the pop() function. You are not allowed to use a stack as a helper data structure.

    I am trying to find my answer in this code but maybe i ain't even goin in the right direction!
    Code:
    //
    //*****************************************************************************
    //* C++ stack using templates.  Note that everything is here; there is no
    //* implementation CC file.
    //*****************************************************************************
    //
    
    #ifndef _STACKT_H_
    #define _STACKT_H_
    
    // This is a template class.  The name T stands for any type.  By saying
    // Stack<whatever>, we create a stack of whatevers.
    template <class T>
    class Stack
    {
     private:
            // Nodes.
            struct Node
            {
             public:
                    T data;         // Note: Data field is a whatever.
                    Node *next;
                    Node(T e, Node *n = 0) {
                            data = e;
                            next = n;
                    };
            };
    
            // Head of the list.
            Node *head;
     public:
            // Create an empty stack.
            Stack() { head = 0; }
    
            // Destroy the stack.  The pointers to data are not deleted.
            ~Stack() {
                    while(!empty()) { pop(); }
            }
    
            // Add an element to the stack.  Note that you must send a pointer,
            // and the stack actually stores the pointer.
            void push(T e)
            {
                    head = new Node(e, head);
            }
    
            // Pop the stack and return the top item pointer.  If the stack is
            // empty, return the null pointer.
            T pop();
    
            // Return the top item pointer.  If none, return the null pointer.
            T top() {
                    if(head == 0) return 0;
                    return head->data;
            }
    
            // Tell if the stack is empty.
            bool empty() { return head == 0; }
    };
    
    // Pop the stack.
    template <class T>
    T Stack<T>::pop() {
            if(head == 0) return 0;                 // Take care of empty.
    
            Node *zombie = head;                    // Save list head.
            head = head->next;                      // Advance the list head.
            T retval = zombie->data;                // Remember data.
            delete zombie;                          // Free the old node.
    
            return retval;
    }
    // Note: Templates usually must be in header files.  This is a compiler
    // implementation issue (I think).  
    
    #endif

  4. #4
    Registered User
    Join Date
    Feb 2006
    Posts
    155
    that is a code for a stack adt,but u dont have to use a stack adt,u have to implement the pop() function using a fifo queue adt.

    it can be easily implemented using two fifo queues.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    4
    Can you help with the directions/wording/pseudo code on this? thanks

  6. #6
    Registered User
    Join Date
    Feb 2006
    Posts
    155
    when there is a pop call,
    u deque all the values from the first queue and place them on the second queue.(except the last value)
    then deque the last value and return this as the pop call return value.

    and then deque all the values from the second queue back to the first queue.

  7. #7
    Registered User
    Join Date
    Mar 2006
    Posts
    4
    thanks qqqqxxxx

  8. #8
    &TH of undefined behavior Fordy's Avatar
    Join Date
    Aug 2001
    Posts
    5,793
    Moved from C to C++

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please Help Me With This Code Of Implementing Stacks
    By raghu_equinox in forum C Programming
    Replies: 3
    Last Post: 10-19-2006, 07:22 AM
  2. ...multiplication using stacks
    By iiwhitexb0iii in forum C Programming
    Replies: 1
    Last Post: 10-09-2006, 01:28 AM
  3. Avioding Stacks
    By LoafOfBread34 in forum C++ Programming
    Replies: 8
    Last Post: 12-08-2004, 06:20 AM
  4. Dumping singly linked list into 2 stacks.
    By strotee76 in forum C++ Programming
    Replies: 5
    Last Post: 05-16-2004, 05:48 PM
  5. Stacks stacks stacks
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 06-06-2002, 02:01 AM