min stackの実装方法

min stackの実装方法
Q:特殊なスタックをどのように設計するか、min()操作をサポートし、スタックの最小要素を返す.
この問題は去年の面接で出会った問題に由来し、面接官は20分間このようなスタックを設計させた.当時は時間が限られていて、1つのバージョンが書かれていましたが、そのバージョンには多くの問題がありました.例えば、汎用性が足りず、int種類のデータしかサポートできませんでした.同時に、効率も低い、大量のデータコピーが存在する.
面接が终わった后にまたよく考えて、再び1つのバージョンを书いて、记录して、みんなに分かち合います!このバージョンは主に前に述べた2つの問題を解決します.汎用性2.効率
1.インタフェースの設計
汎用性の問題を解決するには、このスタックにすべてのデータ型をサポートさせるには、templateを使用する必要がある.
また、min()の動作をサポートするためには、2つの配列が必要である.配列aはpushをスタックに格納データであり、配列bは最小値を記録し、配列aは更新(pushまたはpop)するたびに、配列bは更新される.
もう一度よく考えてみると、配列bは本当に最小値を保存する必要がありますか?実は配列aには最小のコピーが存在する、b配列にもう一度保存すると空間が浪費され、スタックに格納されている非常に膨大なクラスタイプであれば、そのタイプのデータをb配列に書き込むのにもかなり時間がかかる.これは空間と時間の二重の浪費をもたらし、明らかにこれは合理的ではない.実際、b配列に実際のクラスオブジェクトを記憶する必要は全くない、そのオブジェクトのa配列におけるインデックスを記憶すればよいので、スペースを節約するとともに、速度を向上させることができる.
上記の分析に基づいて、次のインタフェースを設計することができます.

template 
class stack
{
private:
  //   top  
  int   top;           
  //    top  
  int   minTop;        
  T     buf[1024]; 
  //                     
  int   minIndex[1024];
  const int  maxsize = 1024;
public:
  int push(const T& item);
  T   pop();
  //       
  int pushMinIndex(const T& item);
  int popMinIndex();
  T   min(); //      
  stack();
  stack(const stack& s);
  stack& operator=(const stack& s);
  ~stack();
};

2.インタフェース実装
上記の設計に基づいて、コードを簡単に書くことができます.

#ifndef MY_STACK_H
#define MY_STACK_H
#include
#define ERROR -1
#define OK   0
template 
class stack
{
private:
  int     top;
  int     minTop;
  T       buf[1024];
  int     minIndex[1024];
  const int   maxsize = 1024;
public:
  int push(const T& item);
  int pushMinIndex(const T& item);
  int popMinIndex();
  T   min();
  T   pop();
  stack();
  stack(const stack& s);
  stack& operator=(const stack& s);
  ~stack();
};

template
stack::stack():top(-1), minTop(-1) 
{

}

template
stack::~stack() {}

template
int stack::push(const T& item)
{
  top++;
  if ((top >= maxsize) || (top < 0)) {
    return ERROR;
  }
  buf[top] = item;
  pushMinIndex(item);
  return OK;
}

template
T stack::pop() 
{
  assert(top >= 0);
  popMinIndex();
  return buf[top--];
}

//     ,       
template 
int stack::pushMinIndex(const T& item)
{
  minTop++;
  if ((minTop >= maxsize) || (minTop < 0)) {
    return ERROR;
  }
  if (minTop == 0) {
    minIndex[minTop] = top;
    return OK;
  }
  if (item < buf[minIndex[minTop - 1]]) {
    minIndex[minTop] = top;
  } else {
    minIndex[minTop] = minIndex[minTop - 1];
  }
  return OK;
}

template
int stack::popMinIndex()
{
  minTop--;
  return OK;
}

template
T stack::min()
{
  assert(minTop >= 0);
  return buf[minIndex[minTop]];
}

//               ,  
template
stack::stack(const stack& s):top(s.top), minTop(s.minTop)
{
  top = s.top;
  minTop = s.minTop;
  for (int i = 0; i <= top; i++) {
    buf[i] = s.buf[i];
  }
  for (int i = 0; i <= minTop; i++) {
    minIndex[i] = s.minIndex[i];
  }
}

template
stack& stack::operator=(const stack& s)
{
  top = s.top;
  minTop = s.minTop;
  for (int i = 0; i <= top; i++) {
    buf[i] = s.buf[i];
  }
  for (int i = 0; i <= minTop; i++) {
    minIndex[i] = s.minIndex[i];
  }
  return *this;
}
#endif

3.テストしてみる
自分が書いたstackが使いやすいかどうかをテストする小さな例を書きます.

#include 
#include "minstack.hpp"
using namespace std;
int main()
{
  stack s;
  double a[] = {8.1, 7.2, 9.5, 6.3, 2.5, 5.6, 3.5};
  for (int i = 0; i < 7; i++) {
    s.push(a[i]);
    cout << s.min() << " ";
  }
  cout << endl;
  stack t;
  t = s;
  cout << "---------------------------" << endl;
  for (int i = 0; i < 7; i++) {
    cout << t.min() << " ";
    t.pop();
  }
  return 0;
}

コンパイルして

g++ -g main.cpp -Wall

実行結果

$ ./a.out
8.1 7.2 7.2 6.3 2.5 2.5 2.5
---------------------------
2.5 2.5 2.5 6.3 7.2 7.2 8.1

問題ないようですね~コードはgithubにアップロードされています.リンクはここです.https://github.com/zkangHUST/CppSTL
THE END.