C++ でのスタックの実装

Stackは線形データ構造これは、LIFO(後入れ先出し)ルールに従って挿入および削除されるオブジェクトのコンテナーとして機能します。

Stackには3つの主要な操作があります。 push, pop、と peek。これらの操作については、前回の投稿で説明しました。アレイと Stackデータ構造のリンクリスト実装この記事では、Stackデータ構造のC++実装についてクラスを使用して説明します。

以下は、以下の操作をカバーするC++でのStack実装です。

push: Stackの一番上、現在の一番上の要素の上に新しい要素を挿入します。
pop: Stackの一番上の要素を削除し、それによってそのサイズを1つ減らします。
isEmpty: Stackが空の場合、つまりサイズがゼロの場合はtrueを返します。それ以外の場合は、falseを返します。
isFull: Stackがいっぱいの場合、つまり、Stackのサイズが割り当てられた最大容量に達した場合にtrueを返します。それ以外の場合は、falseを返します。
peek: Stackを変更せずに、Stackに存在する最上位の要素を返します。
size: Stackに存在する要素の数を返します。

Practice this problem

アレイを使用したStackの実装：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <iostream>

#include <cstdlib>

using namespace std;

//Stackのデフォルト容量を定義します

#define SIZE 10

//Stackを表すクラス

class Stack

{

int *arr;

int top;

int capacity;

public:

Stack(int size = SIZE); //コンストラクタ

~Stack(); //デストラクタ

void push(int);

int pop();

int peek();

int size();

bool isEmpty();

bool isFull();

};

//Stackを初期化するコンストラクタ

Stack::Stack(int size)

{

arr = new int[size];

capacity = size;

top = -1;

}

//Stackに割り当てられたメモリを解放するデストラクタ

Stack::~Stack() {

delete[] arr;

}

//要素`x`をStackに追加するユーティリティ関数

void Stack::push(int x)

{

if (isFull())

{

cout << "Overflow\nProgram Terminated\n";

exit(EXIT_FAILURE);

}

cout << "Inserting " << x << endl;

arr[++top] = x;

}

//Stackから最上位の要素をポップするユーティリティ関数

int Stack::pop()

{

//Stackのアンダーフローをチェックします

if (isEmpty())

{

cout << "Underflow\nProgram Terminated\n";

exit(EXIT_FAILURE);

}

cout << "Removing " << peek() << endl;

//Stackサイズを1減らし、(オプションで)ポップされた要素を返します

return arr[top--];

}

//Stackの最上位要素を返すユーティリティ関数

int Stack::peek()

{

if (!isEmpty()) {

return arr[top];

}

else {

exit(EXIT_FAILURE);

}

//Stackのサイズを返すユーティリティ関数

int Stack::size() {

return top + 1;

}

//Stackが空かどうかをチェックするユーティリティ関数

bool Stack::isEmpty() {

return top == -1; //また return size() == 0;

}

//Stackがいっぱいかどうかをチェックするユーティリティ関数

bool Stack::isFull() {

return top == capacity - 1; //また return size() == capacity;

}

int main()

{

Stack pt(3);

pt.push(1);

pt.push(2);

pt.pop();

pt.push(3);

cout << "The top element is " << pt.peek() << endl;

cout << "The stack size is " << pt.size() << endl;

pt.pop();

if (pt.isEmpty()) {

cout << "The stack is empty\n";

}

else {

cout << "The stack is not empty\n";

}

return 0;

}

ダウンロードコードを実行する

Output:

Inserting 1
Inserting 2
Removing 2
Removing 1
Inserting 3
The top element is 3
The stack size is 1
Removing 3
The stack is empty

すべてのStack操作の時間計算量は一定です。 O(1).

STLの使用：

C++標準ライブラリのコンテナタイプのいくつかには push_back と pop_back 次のようなLIFOセマンティクスを使用した操作 std::stack, std::list.

std::stack

#include <iostream>

#include <stack>

using namespace std;

// `std::stack`を使用したC++でのStack実装

int main()

{

stack<string> s;

s.push("A"); //`A`をStackに挿入します

s.push("B"); //`B`をStackに挿入します

s.push("C"); //`C`をStackに挿入します

s.push("D"); //`D`をStackに挿入します

//Stackに存在する要素の総数を返します

cout << "The stack size is " << s.size() << endl;

//Stackの一番上を出力します( `D`)

cout << "The top element is " << s.top() << endl;

s.pop(); //一番上の要素を削除します( `D`)

s.pop(); //次のトップを削除します( `C`)

cout << "The stack size is " << s.size() << endl;

//Stackが空かどうかを確認します

if (s.empty()) {

cout << "The stack is empty\n";

}

else {

cout << "The stack is not empty\n";

}

return 0;

}

ダウンロードコードを実行する

std::list

#include <iostream>

#include <list>

using namespace std;

// `std::list`を使用したC++でのStack実装

int main()

{

list<string> s;

s.push_front("A"); //`A`をStackに挿入します

s.push_front("B"); //`B`をStackに挿入します

s.push_front("C"); //`C`をStackに挿入します

s.push_front("D"); //`D`をStackに挿入します

//Stackに存在する要素の総数を返します

cout << "The stack size is " << s.size() << endl;

//Stackの一番上を出力します( `D`)

cout << "The top element is " << s.front() << endl;

s.pop_front(); //一番上の要素を削除します( `D`)

s.pop_front(); //次のトップを削除します( `C`)

cout << "The stack size is " << s.size() << endl;

//Stackが空かどうかを確認します

if (s.empty()) {

cout << "The stack is empty\n";

}

else {

cout << "The stack is not empty\n";

}

return 0;

}

ダウンロードコードを実行する

Output:

The top element is D
The stack size is 2
The stack is not empty

こちらも参照:

JavaでのStack実装

PythonでのStack実装