The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Stacks & Queues

Problem :-
Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity.

Solution :-
We need to maintain an additional element ( max_so_far ) in each node which stores the maximum value pushed into the stack till now. The value of max_so_far on the top node of the stack gives the maximum element in the stack. See the implementation below.

#include<iostream>
#define MAX 100
#define MIN -999999 // infinitesimal small value
using namespace std;

int max(int a,int b) {
   return ((a > b) ? a : b);
}

// structure of a stack node
typedef struct stack_node {
   int data;
   int max_so_far;// max element so far in the stack 
   struct stack_node *next;
}node;

// declare a stack data structure which also gives the max
// element apart from push and pop operations in O(1) time
class stack {
private :
   node *top;
public :
   stack() {
       // stack is empty
      top = NULL;
   }
   void push(int element); // push element
   void pop(); // pop
   int getTopElement(); // returns the top element
   int getMaxElement(); // returns max element
   void displayStack(); // displays the stack
};

// displays all the elements of a stack
void stack :: displayStack() {
   node *ptr = top;
   cout<<"\nStack elements (top to bottom)\n";
   while (ptr != NULL) {
      cout<<ptr->data<<" ";
      ptr = ptr->next;
   }
}

// pushes an element onto stack
void stack :: push(int element) {
   node *new_element = new node;
   new_element->data = element;
   new_element->next = NULL;
   if (top == NULL) {
      // first node being pushed into stack
      new_element->max_so_far = new_element->data;
      top = new_element;
   }
   else {
      new_element->max_so_far = max(top->max_so_far, new_element->data);
      new_element->next = top;
      top = new_element; // update top
   }
}

// removes the top element from stack
void stack :: pop() {
   if (top == NULL) {
      cout<<"\nStack Empty";
   }
   else {
      node *ptr = top;
      top = top->next;
      delete ptr;
   }
}

// get the top element
int stack :: getTopElement() {
   return top->data;
}

// get the max element is stack
int stack :: getMaxElement() {
   return top->max_so_far;
}

// main
int main() {
   stack s;
   s.push(11);
   s.push(33);
   s.push(77);
   s.push(49);
   s.push(55);
   s.push(99);
   s.pop();
   s.displayStack();
   cout<<"\nTop Element :: "<<s.getTopElement();
   cout<<"\nMax Element :: "<<s.getMaxElement();
   cout<<endl;
   return 0;
}

Back | Next

All problems on Stacks and Queues
* Implement a stack using an array
* Implement a queue using an array
* Implement a circular queue using an array
* Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity
* Implement a circular queue using linked list
* Implement a Queue data structure using two stacks
* Sort a Queue using two stacks
* Convert infix expression to the postfix notation
* Implement an algorithm to evaluate a postfix expression
* Given a stack with only 0s & 1s, find the majority element in the stack
* Implement an inplace algorithm to sort a stack