C++でスタックを1から実装する

プロコンのための勉強の一環としてデータ構造を学習しています。今回はスタックです。
C++の標準ライブラリに入っていますが、勉強のために自分で実装してみます。

目標

スタックを実装する。

スタックとは

後入れ先出し（LIFO: Last In First Out）を特徴とするデータ構造。後に入れたデータほど先に取り出される。格納するデータを縦に積んでいくイメージ。

標準ライブラリでは次のようなメソッドが定義されています。

size()	スタックの要素数を返す
top()	スタックの頂点の要素を返す
pop()	スタックの頂点の要素を削除する
push(x)	スタックに要素xを追加する
empty()	スタックが空であればtrue、空でなければfalseを返す

実装してみた

上の機能をC++で実装してみます。
簡単のため、スタックに格納する値は整数であるものとします。
格納されたデータのインデックスは1から始まることに注意。スタックの頂点の位置を表す変数（スタックポインタ）が0の時にスタックが空であるとみなします。スタックポインタを考えることで簡潔に実装できます。

stack.h

#ifndef _STACK_H_
#define _STACK_H_

class Stack {
 private:
  int m_top; // スタックポインタ
  int m_s[100000];  // スタックの実体となる配列

 public:
  Stack();
  int size();
  int top();
  void pop();
  void push(int x);
  bool empty();
};

#endif // _STACK_H_

stack.cpp

#include<iostream>
#include "stack.h"
using namespace std;

Stack::Stack() : m_top(0)
{  
}

int Stack::size() {
  return m_top;
}

int Stack::top() {
  return m_s[m_top];
}

void Stack::pop() {
  if (m_top == 0) {  // under flow
    cout << "Error: stack is empty." << endl;  
  } else {
    m_top--;
  }
}

void Stack::push(int x) {
  if (m_top == sizeof(m_s) / sizeof(m_s[0]) - 1) {
    cout << "Error: stack is full." << endl;
  } else {
    m_s[++m_top] = x;
  }
}

bool Stack::empty() {
  if (m_top == 0) {
    return true;
  } else {
    return false;
  }
}

main.cpp

#include<iostream>
#include "stack.h"
using namespace std;

int main(void) {
  Stack stack;

  // 空の状態
  if (stack.empty()) cout << "stack is empty" << endl;
  else cout << "stack is not empty" << endl;

  // 要素を追加
  stack.push(1);
  stack.push(2);

  if (stack.empty()) cout << "stack is empty" << endl;
  else cout << "stack is not empty" << endl;

  // 要素を取り出す
  cout << "top: " << stack.top() << " size: " << stack.size() << endl;
  stack.pop();  // トップを削除
  cout << "top: " << stack.top() << " size: " << stack.size() << endl;
  stack.pop();
  stack.pop();

  return 0;
}

実行結果：

stack is empty
stack is not empty
top: 2 size: 2
top: 1 size: 1
Error: stack is empty.

まとめ

スタックを実装しました。意外と簡単。

参考

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.