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