スタック

概要

スタックは後入れ先出し(LIFO:Last In First Out)が保証されたデータ構造です。
スタックはデータの追加、取得ができるようになっており、
データの取得は最後に追加したデータが取得できるようになっています。
この時にデータを追加することを「Push」、取得することを「Pop」といいます。



食器棚に積まれたお皿を例として使われることが多いです。
食器棚に積まれたお皿は使うときは上から取り、洗った後のお皿は棚の上に重ねます。
このように後に乗せたものを先に使用するのがスタックの原理です。

サンプル

スタックを実装したサンプルをこちらに用意しています。


	
開発環境
	

		
 言語 
		
 Visual Studio 
	
	

		
 C/C++
		
 Visual Studio 2017 

	

実装方法

スタックの実装方法は様々な方法があります。
今回紹介しているのは「配列」「リスト」「std::list使用」の方法です。
各内容でも更に様々な方法があるのであくまで方法の１つとして認識してください。

配列

配列を使用したスタックはサイズの制限がありますが、
必要な知識という意味では最も簡単に作成ができます。
サイズの制限もreallocなどでサイズを変更できるのでその問題の解消も可能です。
ただし、サイズ変更の処理コストが多大にかかるので
できる限り最初のサイズで配列を使いまわすことを意識します。
サンプルのArraySampleプロジェクトにコードがあります。

メリット

・リストに比べて高速

デメリット

・最初に作成した配列のサイズに制限がある
・サイズを変更する際の処理コストが高い

リスト

リストを使用したスタックはサイズの制限がないので、
好きなだけ、プッシュをすることが可能です。
ただし、プッシュをするたびに動的にデータを確保する必要があるので、
確保時に処理コストがかかったり、ポップをした際に解放をしないと
メモリリークになるなど、配列に比べると技術的コストがかかります。
サンプルのListSampleプロジェクトにコードがあります。

メリット

・サイズに制限がないのでメモリがある限りプッシュできる

デメリット

・プッシュのたびにデータを確保する必要があるので遅い
・ポップする際にデータを解放する必要がある
　解放しないとメモリリークになる

std::list使用

C++やC#では簡易的にリストの挙動ができる仕様があり、
今回使用しているstd::listもその１つです。
このように言語が用意している機能を使用してスタックの機能を作成することもできます。
サンプルのStdListSampleプロジェクトにコードがあります。

メリット

・リストなどを自作する必要がない
・多機能ことが多い

デメリット

・使用方法を理解する必要がある