Can I post a book problem that I am confused with on this forum? It's driving me in circles for a correct answer??
Printable View
Can I post a book problem that I am confused with on this forum? It's driving me in circles for a correct answer??
try posting it and also what r your thoughts on it so far.
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
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.
Can you help with the directions/wording/pseudo code on this? thanks
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.
thanks qqqqxxxx
Moved from C to C++