2019年3月23日SHAREツイートシェアはてブLINEPocketこのページではスタックとキューについての解説と、それぞれをC言語で実装したときのソースコードについて紹介していきたいと思います。スポンサーリンクContentsスタックスタックの特徴PUSHPOPスタックのC言語での実装キューキューの特徴エンキューデキューC言語での実装まとめスタックスタックとはデータ構造のひとつです。英語では”stack”と書きます。日本語に訳すと「積み重ねる」や「積み重ね」といった意味の単語になります。特徴は、データを積み重ねるようにして管理し、後に入力されたデータから先に出力するようにデータを管理することです。イメージしやすいのは買い物でのレジ待ちの行列です。先に並んだ人から先に会計してもらえますよね?キューではこういった感じに、先入先出方式でデータを管理します。Out)とも言いますスタックでは下記のPUSHとPOPの仕組みにより先入先出方式を実現しています。PUSHデータをスタックに追加することをPUSHと呼びます。PUSHでは必ずスタックの一番上にデータを追加します。POPデータをスタックから取り出すことをPOPと呼びます。POPではスタックの一番上のデータを取り出します。スタックのC言語での実装このページではスタックを配列を用いて実装したソースコードを紹介したいと思います。配列によるスタック実装のイメージを図で表すと下のようになります。ポイント配列の要素0がスタックの一番下であり、配列の要素num-1(numはスタックに存在しているデータ数)がスタックの最後尾となります。要素num以降はデータを入れる箱としては存在していますが、何も入っていない空の状態になります。そのため、PUSHは「一番上のnum-1よりも1つ上の要素num」にデータを格納することで実現することが可能です。スタックに入っているデータ数が1増えますので、PUSH時にはデータ数を表すnumも1増やす必要があります。POPはスタックの一番上の要素num-1を取得する処理になります。スタックのデータ数が1減りますので、numも1減らす必要があります。ソースコードC言語でスタックを配列により実装した時のソースコードは下のようになります。続いてキューに移ります。キューとはデータ構造のひとつであり、待ち行列とも言います。英語では”queue”と書きます。特徴は、先に入力されたデータから先に出力するようにデータを管理することです。イメージしやすいのは買い物でのレジ待ちの行列です。先に並んだ人から先に会計してもらえますよね?キューではこういった感じに、先入先出方式でデータを管理します。Out)とも言いますキューでは下記のエンキューとデキューの仕組みにより先入先出方式を実現しています。エンキューデータをキューに追加することをエンキューと呼びます。エンキューでは必ずキューの最後尾にデータを追加します。デキューデータをキューから取り出すことをデキューと呼びます。デキューでは必ずキューの先頭のデータを取り出します。C言語での実装このキューの実装方法はたくさん存在すると思いますが、このページでは配列による実装とポインタによる実装のソースコードを紹介したいと思います。配列によるキューの実装のイメージを図で表すと下のようになります。ポイント配列の要素0がキューの先頭であり、配列の要素num-1(numはキューに存在しているデータ数)がキューの最後尾となります。要素num以降はデータを入れる箱としては存在していますが、何も入っていない空の状態になります。そのため、エンキューは「最後尾のnum-1よりも後ろの要素num」にデータを格納することで実現することが可能です。最後尾も後ろにずれる点に注意です。デキューはちょっとだけややこしいです。データの取得先はキューの先頭である配列の要素0になります。取得するだけだと列が進みませんので、配列の要素0を取り出した後は配列の要素1以降のデータを先頭に向かってひとつずつ進めてやる必要があります。ソースコードC言語でキューを配列により実装した時のソースコードは下のようになります。続いてポインタによる実装について解説していきます。ポインタが苦手という方は是非下のページも合わせて読んでみてください。徹底図解!C言語ポインタを初心者向けに分かりやすく解説ポインタによるキューの実装のイメージを図で表すと下のようになります。ポイントheadポインタとtailポインタを用意し、それぞれがキューの先頭と最後尾を指すようにします。キューのデータそれぞれに、次のデータを指すnextポインタを持たせ、各データをリスト構造的につなぎ合わせることでキューを実現します。エンキューは下記の3つの処理を行うことで実現します。追加データをメモリ空間に確保tailポインタが指しているデータのnextポインタを追加データのアドレスにセットtailポインタを追加データのアドレスにセットこれにより、追加分のデータはキューの最後尾に追加されることになります。デキューは下記の4つの処理を行うことで実現します。取得したデータのnextポインタの指すアドレス退避headポインタの指す先のデータを削除headポインタを退避していたアドレスにセットこれにより取得したデータは削除され、先頭の次に追加されたデータが先頭に並ぶようになります。ソースコードC言語でキューをポインタにより実装した時のソースコードは下のようになります。0;}スポンサーリンクまとめこのページでは、キューとスタックについて解説し、C言語で実装した時のソースコードと実装のポイントを説明しました。スタックやキューなどのデータ構造について学びたい方は下記の書籍がオススメです。スタックやキューだけでなく、リスト構造も学べますし、アルゴリズムも探索・ソート法などをC言語と一緒に学ぶことができます。楽天ブックスAmazone-hon他のデータ構造についてリスト構造の解説やC言語ソースコードも下記で解説しています。コメントをキャンセルメールアドレスが公開されることはありません。記事C言語のアロー演算子(->)を分かりやすく、そして深く解...プライバシーポリシーだえうホームページのプライバシーポリシー・免責事項についてはこちらに記載しております。