第4章：stack - コンテナアダプタ
はじめに
stackは、既存のコンテナを包んでLIFO（Last In, First Out）の動作を提供するコンテナアダプタです。本章では、アダプタパターンとstackの実装を学びます。
---
1. コンテナアダプタとは
1.1 デザインパターン：アダプタ
アダプタパターン:
既存のインターフェースを別のインターフェースに変換
+--------+ +--------+ +--------+
| Client | --> | Adapter| --> |Adaptee |
+--------+ +--------+ +--------+
STLでの例:
stack, queue, priority_queue
これらは新しいデータ構造ではなく、
既存のコンテナ（vector, deque, list）を
特定のインターフェースで包む
1.2 stackの特性
LIFO (Last In, First Out):
後から入れたものが先に出る
Push: Pop:
+-----+ +-----+
| 3 | ← top | |
+-----+ +-----+
| 2 | | 2 | ← new top
+-----+ +-----+
| 1 | | 1 |
+-----+ +-----+
操作:
- push: 上に追加
- pop: 上から削除
- top: 一番上を参照
1.3 使用例
ft::stack<int> s;
s.push(1); // [1]
s.push(2); // [1, 2]
s.push(3); // [1, 2, 3]
s.top(); // 3
s.pop(); // [1, 2]
s.top(); // 2
s.size(); // 2
s.empty(); // false
---
2. 実装
2.1 クラス定義
namespace ft {
template<typename T, typename Container = ft::vector<T> >
class stack {
public:
typedef T value_type;
typedef Container container_type;
typedef size_t size_type;
protected:
container_type c;
public:
// コンストラクタ
explicit stack(const container_type& ctnr = container_type())
: c(ctnr) {}
// 容量
bool empty() const {
return c.empty();
}
size_type size() const {
return c.size();
}
// 要素アクセス
value_type& top() {
return c.back();
}
const value_type& top() const {
return c.back();
}
// 変更
void push(const value_type& val) {
c.push_back(val);
}
void pop() {
c.pop_back();
}
// フレンド宣言（比較演算子のため）
template<typename T1, typename C1>
friend bool operator==(const stack<T1, C1>&, const stack<T1, C1>&);
template<typename T1, typename C1>
friend bool operator<(const stack<T1, C1>&, const stack<T1, C1>&);
};
} // namespace ft
2.2 比較演算子
template<typename T, typename Container>
bool operator==(const stack<T, Container>& lhs,
const stack<T, Container>& rhs) {
return lhs.c == rhs.c;
}
template<typename T, typename Container>
bool operator!=(const stack<T, Container>& lhs,
const stack<T, Container>& rhs) {
return !(lhs == rhs);
}
template<typename T, typename Container>
bool operator<(const stack<T, Container>& lhs,
const stack<T, Container>& rhs) {
return lhs.c < rhs.c;
}
template<typename T, typename Container>
bool operator<=(const stack<T, Container>& lhs,
const stack<T, Container>& rhs) {
return !(rhs < lhs);
}
template<typename T, typename Container>
bool operator>(const stack<T, Container>& lhs,
const stack<T, Container>& rhs) {
return rhs < lhs;
}
template<typename T, typename Container>
bool operator>=(const stack<T, Container>& lhs,
const stack<T, Container>& rhs) {
return !(lhs < rhs);
}
---
3. 基底コンテナの要件
3.1 必要なインターフェース
stackが使用するコンテナは、以下のメンバを持つ必要があります：
// 必須メンバ
empty() // 空かどうか
size() // サイズ
back() // 末尾の要素
push_back() // 末尾に追加
pop_back() // 末尾を削除
// これを満たすコンテナ:
// - vector
// - deque
// - list
3.2 異なるコンテナでの使用
// デフォルト（vector）
ft::stack<int> s1;
// dequeを使用
ft::stack<int, std::deque<int> > s2;
// listを使用
ft::stack<int, std::list<int> > s3;
// 独自のコンテナも可能
// （必要なインターフェースを持っていれば）
---
4. protected継承について
4.1 なぜprotectedか
STL標準では、基底コンテナはprotectedメンバとして定義されます：
protected:
container_type c;
理由：
- 派生クラスがアクセス可能: 拡張が可能
- 外部からは非公開: カプセル化を維持
- 標準準拠: STL仕様に従う
4.2 比較演算子のフレンド
比較演算子は非メンバ関数ですが、cにアクセスする必要があります：
template<typename T1, typename C1>
friend bool operator==(const stack<T1, C1>&, const stack<T1, C1>&);
---
5. 計算量
| 操作 | 計算量（vectorの場合） | |------|------------------------| | push | 償却O(1) | | pop | O(1) | | top | O(1) | | size | O(1) | | empty | O(1) |
---
6. 実用例
6.1 括弧のバランスチェック
bool isBalanced(const std::string& str) {
ft::stack<char> s;
for (size_t i = 0; i < str.size(); ++i) {
char c = str[i];
if (c == '(' || c == '[' || c == '{') {
s.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (s.empty())
return false;
char top = s.top();
s.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return s.empty();
}
6.2 逆ポーランド記法（RPN）計算機
int evalRPN(const std::vector<std::string>& tokens) {
ft::stack<int> s;
for (size_t i = 0; i < tokens.size(); ++i) {
const std::string& token = tokens[i];
if (token == "+" || token == "-" ||
token == "*" || token == "/") {
int b = s.top(); s.pop();
int a = s.top(); s.pop();
if (token == "+") s.push(a + b);
else if (token == "-") s.push(a - b);
else if (token == "*") s.push(a * b);
else if (token == "/") s.push(a / b);
} else {
s.push(atoi(token.c_str()));
}
}
return s.top();
}
6.3 深さ優先探索（DFS）
void dfs(Graph& graph, int start) {
ft::stack<int> s;
std::set<int> visited;
s.push(start);
while (!s.empty()) {
int node = s.top();
s.pop();
if (visited.count(node))
continue;
visited.insert(node);
std::cout << node << " ";
// 隣接ノードをスタックに追加
for (int neighbor : graph.neighbors(node)) {
if (!visited.count(neighbor)) {
s.push(neighbor);
}
}
}
}
---
7. queueとの比較
7.1 queue（参考）
// queueはFIFO（First In, First Out）
template<typename T, typename Container = std::deque<T> >
class queue {
protected:
Container c;
public:
// 先頭と末尾の両方にアクセスが必要
value_type& front() { return c.front(); }
value_type& back() { return c.back(); }
void push(const value_type& val) { c.push_back(val); }
void pop() { c.pop_front(); }
};
7.2 違い
| | stack | queue | |--|-------|-------| | 方式 | LIFO | FIFO | | 追加 | 上(back) | 後ろ(back) | | 削除 | 上(back) | 前(front) | | アクセス | top (back) | front, back | | デフォルト | vector | deque |
---
まとめ
本章で学んだこと：
- コンテナアダプタ: 既存コンテナを包むパターン
- stackの実装: シンプルなラッパー
- 基底コンテナの要件: back, push_back, pop_back
- 計算量: すべてO(1)（または償却O(1)）
- 実用例: 括弧チェック、RPN、DFS
次章では、イテレータとユーティリティを学びます。