Question

Queue with two stacks

Implement queue with two stacks

Image uploaded from iOS (7).jpg


template<class T> 
class StackNode {
public:
    StackNode(T initVal) {
        value = initVal;
        next = NULL;
    }

    T value;
    StackNode* next;
};

template<class T>
class Stack {
public:
    Stack() { top = NULL; }
    ~Stack() {
        StackNode<T> *node = top;
        while (node) {
            StackNode<T> *next = node->next;
            delete node;
            node = next;
        }

    }
    bool isEmpty() { return (top == NULL); }
    void push(T value) {
        StackNode<T> *node = new StackNode<T>(value);
        
        if (top) {
            node->next = top;
        }
        top = node;
    }
    T pop() {
        assert(top);
        
        T val = top->value;
        StackNode<T> *next = top->next;
        delete top;
        top = next;
        return val;
    }
    StackNode<T> *top;
};

template<class T>
class Queue {
public:
    Queue() {}
    ~Queue() {}

    void add(T value) {
        inStack.push(value);
    }

    T remove() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
        
    }

    Stack<T> inStack;
    Stack<T> outStack;
};

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s