StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Tuesday, July 10, 2012

Implement a minimum stack

 July 10, 2012     Programming problems in CPP     No comments   

Write a program to implement a stack that can return a minimum value of the current elements at any instance

The Approach:-
  1. Have a second stack instance which will hold the minimum values.
  2. During a push operation if the new data is smaller than the top value in minimum stack push the data into the minimum stack.
  3. During a pop operation if the popped out value is same as top value in minimum stack pop the top element from minimum stack.
  4. At any given instance the top element in the minimum stack is the minimum value of all elements in the stack.

C++ program to implement a stack that can return a minimum value of the current elements at any instance

#include <iostream>
#include <list>
using namespace std;

// Basic stack using list
class Stack {
 private:
  list<int> mData;
  int count;
 public:
  Stack() { count = 0; }
  ~Stack() {}
  void push(int data) {
   mData.push_front(data);
   count++;
  }
  int top() {
   return mData.front();   
  }
  void pop() {
   mData.pop_front();
   count--;
  }
  bool empty() {
   return (count == 0) ? true : false;
  }
  int size() {
   return count;
  }
};

// Min stack
class MinStack : public Stack {
 private:  
  Stack* mMin;
 public:
  MinStack() { mMin = new Stack(); }

  ~MinStack() { delete mMin; }

  void mpush(int data) {
   if ( mMin->size() == 0 ) 
    mMin->push(data);
   else {
    if ( data < mMin->top() )
     mMin->push(data);
   }
   push(data);
  }

  void mpop() {
   int val = top();
   if ( val == mMin->top() )
    mMin->pop();
   pop();
  }

  int mmin() {
   return mMin->top();
  }
};

// Test program
int main() {
 MinStack* ms = new MinStack();
 ms->mpush(10);
 ms->mpush(20);
 ms->mpush(30);
 cout << "Minimum value in stack = " << ms->mmin() << endl;
 ms->mpush(5);
 cout << "Minimum value in stack = " << ms->mmin() << endl;
 ms->mpop();
 cout << "Minimum value in stack = " << ms->mmin() << endl;
 delete ms;
}
Output:-
Minimum value in stack = 10
Minimum value in stack = 5
Minimum value in stack = 10
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk