CareerCup

Here is the code. The basic idea is to keep an extra pointer in each node to the max element. 

/* Implement a stack using a linked list. we should also be able to figure out the max at all times. max should be an O(1) operation. 
 */ 

#include <iostream>
using namespace std; 

struct NODE
{
	int value; 
	NODE* max; /* Always points to the max */  
	NODE* next; 
}; 

class Stack
{
public: 
	Stack() { head = NULL; }
	~Stack(); 
	void Push(int value); 
	int  Pop(void); 
	int Max(void); 
	bool IsEmpty() { return head == NULL ? true : false; } 
private:
   NODE* head; 	
}; 

Stack::~Stack()
{
	NODE* temp;
	if( head )
	{
		while( head )
		{
			temp = head;
			head = head->next; 
			delete temp; 
		}
		head = NULL; 
	}
}

void Stack::Push(int value)
{
	NODE* newNode = new NODE; 
	newNode->value = value; 
	newNode->next = NULL; 

	if( !head )
	{
		/* First node */ 
		newNode->max = newNode; 
		head = newNode; 
	}
	else
	{
		/* Second node onwards */ 
		newNode->next = head; 
		/* adjust max pointer */ 
		if( head->max->value > newNode->value )
			newNode->max = head->max; 
		else
			newNode->max = newNode; 

		head = newNode; 
	}
}

int Stack::Pop(void)
{
	if( IsEmpty() )
		return -1; 

	int value; 

	NODE* temp = head; 
	head = head->next; 
	value = temp->value; 
	delete temp; 
	return value; 
}

int Stack::Max(void)
{
	if( IsEmpty() )
		return -1; 
	return head->max->value; 
}

int main()
{
	/* lets use the stack */ 
	Stack s; 
	int array[] = { 1,2,20,5,7,6}; 

	for( int i=0; i<sizeof(array)/sizeof(array[0]); i++)
		s.Push(array[i]); 


	while( !s.IsEmpty() )
	{
		cout << "max is " << s.Max() << endl;
		cout << s.Pop() << endl; 
	}

	return 0; 
}

there is a bug in the code I believe, push 3 6 7 8 1 9 and do a pop 9 then what will be the max in above code?

class Node
    {
        public int value;
        public Node nextNode;
        public Node(int _value)
        {
            value = _value;
        }
    }

 class stack
    {
        Node topNode; Node maxNode;

        public int count = 0;
        public stack(int _value)
        {
            topNode = new Node(_value);
            maxNode = topNode;
            ++count;
        }

        public void push(int _value)
        {
            Node newNode = new Node(_value);
            
            if(!(maxNode.value < _value))
            {
            maxNode = topNode;
            newNode.nextNode = topNode;
            topNode = newNode;
            }
           else
           {
            newNode.nextNode = topNode;
            topNode = newNode;
           }
            ++count;
        }
public Node maxNode()
{
return maxNode;
}
        public int pop()
        {
            int retval = topNode.value;
            topNode = topNode.nextNode;
            --count;
            return retval;
        }

        public void sort()
        {
            Node currentNode = topNode;
            while (currentNode != null)
            {
                Node runnerNode = currentNode.nextNode;
                while (runnerNode != null)
                {
                    if (currentNode.value > runnerNode.value)
                    {
                        int temp = currentNode.value;
                        currentNode.value = runnerNode.value;
                        runnerNode.value = temp;

                    }
                    runnerNode = runnerNode.nextNode;
                }


                currentNode = currentNode.nextNode;
            }
        }

        public void print()
        {
            Console.WriteLine("Values of the node are");

            Node currentNode = topNode;
            while (currentNode != null)
            {
                Console.WriteLine(currentNode.value);
                currentNode = currentNode.nextNode;
            }
        }


    }

For the max()with 0(1), we need to maintain one more linked list that holds the nodes of maximum values and pop() it whenever requested.So the stack implementation requires 2 linked lists

while pushing only we need check for max....
s and top are pointers of type struct abc (.....struct abc *s)

//structure defn ......
/*
struct abc
{
int info;
struct abc * next;
};

struct abc *top=NULL;
struct abc *s; */

//code for checking max number
if(s->info > top->info)
max=(s->info)
else
max=(top->info)

same can be applied for finding minimum also......

while pushing only we need check for max....
s and top are pointers of type struct abc (.....struct abc *s)

//structure defn ......
/*
struct abc
{
int info;
struct abc * next;
};

struct abc *top=NULL;
struct abc *s; */

//code for checking max number
if(s->info > top->info)
max=(s->info)
else
max=(top->info)

same can be applied for finding minimum also......

The max value should be up to date after each pop as well... Say the maximum element was popped out, then you need to update the max value with the new maximum - how do you do that in your implementation ??

I'd say keep another field in each node saying max which is stored with the max value at the time it is being pushed onto the stack.... And always return the top's max value when max() function is called....

When you say return the node, what exactly does it mean ?Does it mean the address of the node ?
Is it necessary that we have to maintain the max element at the top of the stack. This is a linked list, so we can probably just store the address of the node containing the maximum values in a pointer.
Does that satisfy the requirement ?

use second stack

above code is correct