Cracking The Coding Interview 3.2

本文主要是介绍Cracking The Coding Interview 3.2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.//使用一个链表来记录最小值的index 
#include <iostream>
using namespace std;
#define MAXSIZE 100
#define INIT -888888class mStack
{
public:mStack(){top = -1;mi = new min;mi->data = 0;mi->nextMin = NULL;for (int i =0 ;i<100; i++){data[i] = INIT;}}int pop(){if (top > -1){if (top == mi->data){min *t = mi;mi = mi->nextMin;delete t;}int c= data[top];data [top] = INIT;top --;return c;}elsereturn -2;}bool push(int e){if (top<MAXSIZE-1){top++;data[top] = e;if (data[mi->data] > data[top] && data[top]!= INIT){min *t = new min;t->data = top;t->nextMin = mi;mi = t;}return true;}else{return false;}}int getmin(){return data[mi->data];}private:int data[MAXSIZE];int top;struct min{int data;min *nextMin;};min *mi;};int main()
{mStack s;for (int i=0;i<10;i++){s.push(10-i);}s.pop();s.pop();cout<<s.getmin()<<endl;return 0;
}

这篇关于Cracking The Coding Interview 3.2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---