(57)【特許請求の範囲】
【請求項１】
データ構造内のデータ要素を両方向に成長可能に管理するための方法にして、
前記データ構造にデータ要素を入れるという指示に応答して、
前記データ構造内に最後に書き込まれたデータ要素のメモリ位置を前記データ構造の第１の端部として示すためのヘッド・ポインタを、方向フラグの状態が示す方向にメモリ位置１つ分だけ前進させることと、
前記ヘッド・ポインタが示す前記メモリ位置に新しいデータ要素を入れることと、
前記ヘッド・ポインタと、前記第１の端部の反対側にある前記データ構造の第２の端部にあるメモリ位置を示すためのベース・ポインタとをスワップすることと、
前記方向フラグの状態を逆転し、他のデータ要素の受入れに備えて反対方向の成長を示すこと
を含む方法。
【請求項２】
前記データ構造からデータ要素を除去するという指示に応答して、
前記ヘッド・ポインタと、前記ベース・ポインタとをスワップすることと、
前記方向フラグの状態を逆転することと、
前記ヘッド・ポインタが示す前記メモリ位置から前記データ要素を除去することと、
前記ヘッド・ポインタを、前記方向フラグの状態が示す方向とは反対の方向にメモリ位置１つ分だけ前進させることをさらに含む、請求項１に記載の方法。
【請求項３】
前記データ構造が先入れ後出しデータ構造である、請求項１に記載の方法。
【請求項４】
前記データ構造がスタック・データ構造である、請求項１に記載の方法。
【請求項５】
データ構造内のデータ要素を両方向に成長可能に管理するためのシステムにして、
前記データ構造にデータ要素を入れるという指示に応答して、
前記データ構造内に最後に書き込まれたデータ要素のメモリ位置を前記データ構造の第１の端部として示すためのヘッド・ポインタを、方向フラグの状態が示す方向にメモリ位置１つ分だけ前進させるとともに、前記ヘッド・ポインタが示す前記メモリ位置に新しいデータ要素を入れるための第１の手段と、
前記ヘッド・ポインタと、前記第１の端部の反対側にある前記データ構造の第２の端部にあるメモリ位置を示すためのベース・ポインタとをスワップするための第２の手段と、
前記方向フラグの状態を逆転し、他のデータ要素の受入れに備えて反対方向の成長を示すための第３の手段と
を備えるシステム。
【請求項６】
前記データ構造からデータ要素を除去するという指示に応答して、
前記ヘッド・ポインタと、前記ベース・ポインタとをスワップするための第４の手段と、
前記方向フラグの状態を逆転するための第５の手段と、
前記ヘッド・ポインタが示す前記メモリ位置から前記データ要素を除去するための第６の手段と、
前記ヘッド・ポインタを、前記方向フラグの状態が示す方向とは反対の方向にメモリ位置１つ分だけ前進させるための第７の手段とをさらに備える、請求項５に記載のシステム。システム。
【請求項７】
前記データ構造が先入れ後出しデータ構造である、請求項５に記載のシステム。
【請求項８】
前記データ構造がスタック・データ構造である、請求項５に記載のシステム。
【請求項９】
リニア・メモリ・アレイと、
前記リニア・メモリ・アレイに記憶されたスタックとを備え、
前記スタックに要素が追加されるとき、前記追加される要素のそれぞれが、前に追加された要素が置かれていたスタックの端部とは反対側のスタックの端部にある次の空のメモリ位置に入る、メモリ・システム。
【請求項１０】
前記スタックがデッド要素スタックである、請求項９に記載のメモリ・システム。
【請求項１１】
前記スタックが使用済み要素スタックである、請求項９に記載のメモリ・システム。
【請求項１２】
前記スタックから要素が除去されるとき、次に除去される要素は、前に除去された要素の位置とは反対側のスタックの端部にあるメモリ位置から除去される、請求項９に記載のメモリ・システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、改良されたデータ処理システムに関し、より具体的には、メモリ・アレイ内の改良された先入れ後出しデータ構造に関する。
【０００２】
【従来の技術】
関連出願の相互参照
本出願は、本出願と同じ譲受人に譲渡され、同じ日付で出願され、参照により本明細書に組み込まれる以下の出願に関連するものである。
「Ｓｐｌｉｔ  Ｂｉ−ｄｉｒｅｃｔｉｏｎａｌ  Ｓｔａｃｋ  ｉｎ  ａ  Ｌｉｎｅａｒ  Ｍｅｍｏｒｙ  Ａｒｒａｙ」、整理番号ＡＵＳ９−２０００−０４９０−ＵＳ１
「Ｐｒｏｐｏｒｔｉｏｎａｌｌｙ  Ｇｒｏｗｉｎｇ  Ｓｔａｃｋ  ｉｎ  ａ  Ｌｉｎｅａｒ  Ｍｅｍｏｒｙ  Ａｒｒａｙ」、整理番号ＡＵＳ９−２０００−０４９１−ＵＳ１
【０００３】
多くのコンピュータ・アプリケーションではスタックまたは先入れ後出し（ＦＩＬＯ）データ構造が使用されている。単一アプリケーションで複数のスタックが必要になる場合が多く、これらは必要に応じて付加される。というのは、アプリケーションの開始時には、いくつのスタックが必要になるかが分からないからである。コンピュータ・システム内のメモリはリニア・アレイとして配置されているので、アプリケーションは、このリニア・アレイのうち、複数のスタックを配置するために使用するセグメントを有することになる。従来よりスタックを実現する方法は、ベース・ポインタとヘッド・ポインタによるものである。５個の要素が右に成長するスタックを図１に示す。図２は、１０個の要素を備え、図１と同じスタックを示している。図３は、５個の要素を備え、左に成長するスタックを示している。より多くの要素がスタックに追加されるにつれて、図４に示すようにヘッドはメモリ内で左に移動し、同図でヘッドは要素９に移動している。
【０００４】
あるアプリケーションでは、第１のスタックは右または左成長スタックになるように選択され、スタック成長の方向とは反対側のリニア・アレイの端部に置かれる。したがって、第１のスタックが右成長スタックである場合、そのスタックの第１の要素はメモリ・アレイの左端に置かれる。この説明では、右成長スタックがまず選択されるものと想定する。追加スタックが必要になった場合、その追加スタックは左成長スタックになるように選択され、アレイの右に置かれる。したがって、図５に示す状況になり、その場合、第１のスタック３０２はメモリ・アレイ３００の左端に置かれた右成長スタックになり、第２のスタック３０４はメモリ・アレイ３００の右端に置かれた左成長スタックになる。
【０００５】
図５に示すケースでは、メモリ・アレイ３００の両端に２個のスタックが置かれ、それぞれのスタック３０２〜３０４は、反対方向から伸びる反対側スタックにぶつかる（衝突という）まで成長することができる。このケースは非常に効率がよいものと考えられている。というのは、すべてのスタック３０２〜３０４が同じ速度で成長する場合、メモリ・アレイ３００内のすべてのメモリが衝突前に消費されるからである。しかし、第３のスタックが必要になった場合、ジレンマが発生する。第３のスタックは図６に示すように最初の２個のスタックの中央に置くことができ、したがって、第４のスタック用の余地が残る。しかし、そのアプリケーションが第４のスタックを必要としない場合、スタック＃１  ３０２がそのすべての空間を使い果たすかなり前に、スタック＃３  ４０２がスタック＃２  ３０４と衝突することになる。
【０００６】
【発明が解決しようとする課題】
スタックをレイアウトするこの方法では、所与のメモリ・アレイ空間を使用するときには、偶数のスタックの方が奇数のスタックよりも効率がよいことが分かっている。したがって、そのアプリケーションがたまたま奇数のスタックを必要とする場合、そのアプリケーションは効率よくメモリを使用することにはならない。したがって、使用可能なメモリ空間を奇数のスタックと偶数のスタックのどちらにもより効率よく使用するメモリ・アレイ内のスタックを編成する方法が望ましい。
【０００７】
【課題を解決するための手段】
本発明は、両方向に成長する先入れ後出しデータ構造にデータ要素を入れたり除去するための方法を提供する。一実施形態では、データ要素をデータ構造に入れるための要求に応答して、方向フラグの状態が示す方向にメモリ位置１つ分だけヘッド・ポインタを前進させる。新しいデータ要素はヘッド・ポインタが示すメモリ位置に入る。ヘッド・ポインタおよびベース・ポインタの位置は新しいデータ要素の受入れに備えてスワップされ、方向フラグの状態は反対方向へのデータ構造の成長を示すように逆転される。データ構造からデータ要素を除去するための要求に応答して、ヘッド・ポインタとベース・ポインタはスワップされ、方向フラグの状態は逆転される。ヘッド・ポインタが指し示す位置が示す要素は除去され、ヘッド・ポインタは方向フラグが示す方向とは反対の方向にメモリ位置１つ分だけ後退する。
【０００８】
【発明の実施の形態】
次に図７を参照すると、本発明を実現可能なデータ処理システムのブロック図が示されている。データ処理システム５００は、周辺コンポーネント相互接続（ＰＣＩ）ローカル・バス・アーキテクチャを使用している。図示の例ではＰＣＩバスを使用しているが、マイクロ・チャネルやＩＳＡなどの他のバス・アーキテクチャを使用することもできる。プロセッサ５０２およびメイン・メモリ５０４はＰＣＩブリッジ５０８によりＰＣＩローカル・バス５０６に接続されている。ＰＣＩブリッジ５０８は、プロセッサ５０２用の統合メモリ・コントローラおよびキャッシュ・メモリも含むことができる。ＰＣＩローカル・バス５０６への追加接続は、直接コンポーネント相互接続によるかまたはアドイン・ボードにより行うことができる。図示の例では、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ５１０、ＳＣＳＩホスト・バス・アダプタ５１２、拡張バス・インタフェース５１４は直接コンポーネント接続によりＰＣＩローカル・バス５０６に接続されている。対照的に、オーディオ・アダプタ５１６、グラフィック・アダプタ５１８、オーディオ／ビデオ・アダプタ（Ａ／Ｖ）５１９は拡張スロットに挿入されたアドイン・ボードによってＰＣＩローカル・バス５０６に接続されている。拡張バス・インタフェース５１４は、キーボードおよびマウス・アダプタ５２０、モデム５２２、追加メモリ５２４の接続を可能にする。図示の例では、ＳＣＳＩホスト・バス・アダプタ５１２は、ハード・ディスク・ドライブ５２６、テープ・ドライブ５２８、ＣＤ−ＲＯＭドライブ５３０、ディジタル・ビデオ・ディスク読取り専用メモリ・ドライブ（ＤＶＤ−ＲＯＭ）５３２の接続を可能にする。典型的なＰＣＩローカル・バスの実施例は、３個または４個のＰＣＩ拡張スロットまたはアドイン・コネクタをサポートする。
【０００９】
オペレーティング・システムは、プロセッサ５０２上で動作し、図７のデータ処理システム５００内の様々なコンポーネントを調整し、その制御を可能にするために使用する。このオペレーティング・システムは、ＩＢＭ社より入手可能なＯＳ／２などの市販のオペレーティング・システムにすることができる。「ＯＳ／２」はＩＢＭ社の商標である。Ｊａｖａ（Ｒ）などのオブジェクト指向プログラミング・システムは、このオペレーティング・システムとともに動作することができ、データ処理システム５００上で実行されるＪａｖａ（Ｒ）プログラムまたはアプリケーションからオペレーティング・システムへの呼出しを可能にする。このオペレーティング・システム、オブジェクト指向オペレーティング・システム、アプリケーションまたはプログラムに関する命令は、ハード・ディスク・ドライブ５２６などの記憶装置上に位置し、プロセッサ５０２による実行のためにメイン・メモリ５０４にロードすることができる。
【００１０】
当業者であれば、図７のハードウェアは実施例に応じて異なる可能性があることが分かるだろう。例えば、光ディスク・ドライブなどの他の周辺装置は、図７のハードウェアに加えてまたは図７のハードウェアの代わりに使用することができる。図示の例は、本発明に関するアーキテクチャ上の制限を暗示するためのものではない。例えば、本発明のプロセスは、マルチプロセッサ・データ処理システムに適用することもできる。
【００１１】
次に図８ないし図１０を参照すると、本発明により両方向に成長する１個、２個、３個のスタックをそれぞれ含むメモリ・アレイが示されている。メモリ・アレイ６００は、例えば図７に示すメイン・メモリ５０４などのコンピュータ・メモリ内で実現することができる。本発明が提供するように、スタックまたは先入れ後出し（ＦＩＬＯ）データ構造は、一度に２方向に成長することができる。本明細書で使用するスタックおよびＦＩＬＯは同等の用語である。ＦＩＬＯデータ構造を一度に２方向に成長させることにより、奇数のスタックを伴う場合に、より効率の良いメモリ使用が可能になる。
【００１２】
図８のメモリ・アレイ６００は、２方向６０４および６０６に成長する可能性のある単一スタック６０２を含む。図８に示すように、スタック６０２はメモリ・アレイ６００のほぼ中心に位置しているので、必要に応じてメモリ・アレイ６００のエッジ６１４および６１６とスタック６０２との間に追加スタックを置くことができる。新しい要素がスタック６０２に追加されると、第１の要素は例えば右６０４に追加され、第２の要素は左６０６にある次の位置に追加される。次に第３の要素はスタック６０２の右６０４にある次の位置に追加されるだろう。その後、スタック６０２は、メモリ・アレイの限界６１４および６１６に達するまで両方向に（すなわち、右方向６０４と左方向６０６の両方に）成長し続けることができる。
【００１３】
図９では、第２のスタック６１２がメモリ・アレイ６００に追加されているので、メモリ・アレイ６００は両方向に成長する２個のスタックを含む。この例の第２のスタック６１２は、メモリ・アレイ６００の左エッジ６１４とスタック６０２とのほぼ中間点に位置するので、必要に応じてメモリ・アレイ６００のスタック６０２とスタック６１２との間ならびにエッジ６１４とスタック６１２との間に追加スタックを置くことができる。要素は、スタック６２０の場合と同様にスタック６１２に追加される。
【００１４】
図１０では、第３のスタック６２２がメモリ・アレイ６００に追加されている。スタック６２２は、メモリ・アレイ６００の右エッジ６１６とスタック６０２とのほぼ中間点に位置しているので、必要に応じてソフトウェア・アプリケーションにより追加スタックをメモリ・アレイ６００に挿入することができる。スタック６２２はスタック６０２と同様に両方向に成長する。スタック６０２、６１２、６２２は、それぞれがスタック６０２、６１２、６２２の１つと衝突するかまたはエッジ６１４および６１６と衝突するまで、両方向に成長し続けることができる。
【００１５】
各スタックが同じ速度で成長すると想定すると、図８および図１０に示すような両方向に成長する奇数のスタックは例えば図６に示すような従来技術の単方向に成長するスタックより効率よくメモリを使用することが図８および図１０から分かるだろう。しかし、図９に示すような両方向に成長する偶数のスタックは、従来技術の単方向に成長するスタックよりメモリを使用する効率が悪くなる可能性がある。
【００１６】
本発明の両方向に成長するスタックは、標準的な従来技術のスタックの実施例で使用する２つの主な機能を修正する。このような機能は押込み機能と取去り機能（ｐｏｐ  ｆｕｎｃｔｉｏｎｓ）である。押込み機能はスタックに次の要素を書き込むプロセスであり、取去り機能はスタックに書き込まれた最後の要素から順にスタックから抜き出すプロセスである。
【００１７】
マルチスタック環境の場合、各スタックに関するいくつかの情報を記録しなければならない。記録すべき情報の１つはスタック成長の方向である。これは、押込みまたは取去り動作中にヘッド・ポインタが増分されるのか減分されるのかを決定するものである。ヘッド・ポインタは、最も最近、スタックに書き込まれたデータの位置（すなわち、最後のデータ・イン）を示す。ベース・ポインタは、ヘッドとは反対側のメモリ位置を示し、したがって、ヘッド・ポインタが提供する境界（第１の端部）とは反対側のスタックの境界（第２の端部）を提供することにより、メモリ・アレイ内のスタックの範囲を示す。右成長スタックの場合、ヘッド・ポインタは、押込みの場合に増分され、取去りの場合に減分される。左成長スタックの場合はこれが逆になる。記録すべき第２および第３の情報は、スタックのヘッド・ポインタとベース・ポインタの位置である。実施例に応じて、他にも記録すべき情報が存在する可能性がある。
【００１８】
次に図１１を参照すると、本発明の方法およびデータ構造とは対照的な点を示すために、伝統的な従来技術の単方向スタックにデータを押し込む方法を示す流れ図が示されている。まず、新しいデータ要素をスタックに書き込む場合、方向フラグの状態に応じてヘッド位置を前進させる（ステップ７０２）。例えば、方向フラグが右である場合、ヘッド位置は増分される。次に、ヘッド・ポインタが指し示す位置に新しいデータ要素を入れる（ステップ７０４）。
【００１９】
次に図１２を参照すると、本発明により両方向に成長するスタックにデータを押し込むための例示的なプロセスを示す流れ図が示されている。まず、新しいデータ要素をスタックに押し込む場合、方向ポインタの状態に応じてヘッド・ポインタ位置を前進させる（ステップ７１０）。例えば、方向ポインタが右を指し示す場合、ヘッド・ポインタ位置は増分される。しかし、方向ポインタが左を指し示す場合、ヘッド・ポインタ位置は減分される。次に、ヘッド・ポインタが示す位置に新しいデータ要素を入れる（ステップ７１２）。次に、ヘッド・ポインタとベース・ポインタの位置をスワップし（ステップ７１４）、方向フラグを逆転する（ステップ７１６）。
【００２０】
次に図１３ないし図１７を参照すると、本発明によりスタックに複数回押し込んだ後のヘッド・ポインタ位置、ベース・ポインタ位置、方向フラグの一例を示すブロック図が示されている。メモリ・アレイ８００は、例えば図７に示すメイン・メモリ５０４などのデータ処理システム内のメモリ内で実現することができる。メモリ・アレイ８００内の初期スタック構成では、スタックにいかなるデータ要素も押し込まれる前に、ベース・ポインタ８５２とヘッド・ポインタ８５０の両方がメモリ・アレイ８００の初期位置８０２を指し示し、その位置はメモリ・アレイ８００のほぼ中央になっている。方向フラグ８５４は、スタック成長が右であることを示している。
【００２１】
新しいデータ要素（すなわち、データ要素０）をスタックに押し込むと、ヘッド位置は位置８０４まで位置１つ分だけ右に前進し、新しい要素が位置８０４に入り、ヘッド８５２およびベース８５０のポインタ位置が逆転し、方向フラグ８５４が示す方向が右から左に逆転する。したがって、スタックに１回押し込んだ後、ヘッド・ポインタ８５２はメモリ位置８０２を指し示し、ベース・ポインタ８５０はメモリ位置８０４を指し示し、方向フラグ８５４は成長が左であることを示す。
【００２２】
第２のデータ要素（すなわち、データ要素１）をスタックに押し込むと、ヘッド・ポインタ８５２の位置はメモリ位置８０６まで位置１つ分だけ左に前進し（すなわち、減分され）、第１のデータ要素がメモリ位置８０６に入り、ヘッド８５２およびベース８５０のポインタ位置が逆転し、方向フラグ８５４が示す方向が左から右に逆転する。したがって、２回押し込んだ後、ヘッド・ポインタ８５２はメモリ位置８０４を指し示し、ベース・ポインタ８５０はメモリ位置８０６を指し示し、方向フラグ８５４は成長が右であることを示す。
【００２３】
第３のデータ要素（すなわち、データ要素２）をスタックに押し込むと、ヘッド・ポインタ８５２の位置は再びメモリ位置８１０まで位置１つ分だけ右に前進し（すなわち、増分され）、その新しいデータ要素がメモリ位置８１０に入り、ヘッド８５２およびベース８５０のポインタ位置が逆転し、方向フラグ８５４が示す成長の方向が逆転する。したがって、３回目の押込み後、ヘッド・ポインタ８５２はメモリ位置８０６を指し示し、ベース・ポインタ８５０はメモリ位置８１０を指し示し、方向フラグ８５４が示す成長の方向は左になる。
【００２４】
第４のデータ要素（すなわち、データ要素３）をスタックに押し込むと、ヘッド・ポインタ８５２の位置はメモリ位置８１２まで位置１つ分だけ左に前進し（すなわち、減分され）、データ要素３がメモリ位置８１２に入り、ベース８５０およびヘッド８５２のポインタ位置が逆転し、方向フラグ８５４が示す成長の方向が右に切り替わる。
【００２５】
次に図１８を参照すると、本発明の方法およびデータ構造とは対照的な点を示すために、伝統的な従来技術の単方向スタックからデータを取り去る方法の一例を示す流れ図が示されている。スタックへの最後のデータ（ＦＩＬＯ）を除去する場合、ヘッド・ポインタが指し示す位置から要素を除去する（ステップ９０２）。方向フラグの状態に基づいてヘッド・ポインタの位置を後退させる（ステップ９０４）。例えば、方向フラグが右への成長を示す場合、ヘッド・ポインタは減分される。
【００２６】
次に図１９を参照すると、本発明により両方向に成長するスタックからデータ要素を除去する例示的な方法の流れ図が示されている。スタックからデータ要素を除去するようソフトウェア・アプリケーションが要求すると、ヘッドおよびベース・ポインタ位置をスワップし（ステップ９１０）、方向フラグが示す成長の方向を逆転する（ステップ９１２）。ヘッド・ポインタが示す位置にある要素を除去し（ステップ９１４）、要求側アプリケーションに送る。最後に、方向フラグの状態に基づいて、ヘッド・ポインタ位置を位置１つ分だけ後退させる（ステップ９１６）。
【００２７】
次に図２０ないし図２４を参照すると、本発明により両方向スタックから要素を除去する例示的な方法を示すブロック図が示されている。初めに、メモリ・アレイ１０００内のスタックからいかなる要素も除去される（取り去られる）前に、ベース・ポインタ１０５０はメモリ・アレイ１０００内のメモリ位置１００２にある要素３を指し示し、ヘッド・ポインタ１０５２はメモリ位置１００８にある要素２を指し示している。メモリ位置１００２にある要素３はそのスタックに最後に入れられた要素であり、スタックから最初に除去される要素になる。方向フラグ１０５４は、スタック成長が右であることを示している。
【００２８】
スタックからある要素を除去する場合、最も最近、スタックに入れられた要素がスタックから最初に除去される要素になる。したがって、この例では、ある要素を除去するようアプリケーションが要求すると、ヘッド・ポインタ１０５２とベース・ポインタ１０５０が逆転することになる。というのは、初めにヘッド・ポインタは、スタックに最後に入れられた要素（メモリ位置１００２にある要素３）を指し示すのではなく、スタックが成長し続けた場合に次の要素が置かれることになるメモリ位置の直前のメモリ位置１００８を指し示しているからである。次に方向フラグは逆転して左への成長を示し、メモリ位置１００２にある要素３が除去される。次に、方向フラグが左への成長を示しているので、ヘッド・ポインタ１０５０はメモリ位置１つ分だけ右に後退する。したがって、１回の取去り後、ヘッド・ポインタ１０５０はメモリ位置１００４にある要素１を指し示し、ベース・ポインタ１０５２はメモリ位置１００８にある要素２を指し示し、方向フラグはスタックの成長が左であることを示す。
【００２９】
メモリ・アレイ１０００内のスタックから次の要素を除去する場合、ヘッド・ポインタ１０５０とベース・ポインタ１０５２はもう一度スワップされ、方向フラグ１０５４は逆転して右への成長を示す。次にメモリ位置１００８にある要素２が除去される。というのは、これがヘッド・ポインタ１０５２が指し示す場所であるからである。次に、方向フラグが右への成長を示しているので、ヘッド・ポインタ１０５２は位置１つ分だけ左に後退する。したがって、２回の取去り後、ヘッド・ポインタ１０５２はメモリ位置１００６にある要素０を指し示し、ベース・ポインタ１０５０はメモリ位置１００４にある要素１を指し示し、方向フラグ１０５４はスタックの成長の方向が右であることを示す。
【００３０】
スタックから次の要素（要素１）を除去する場合、ヘッド・ポインタ１０５２とベース・ポインタ１０５０はもう一度スワップされ、ヘッド・ポインタ１０５２がメモリ位置１００４にある要素１を指し示し、ベース・ポインタ１０５０がメモリ位置１００６にある要素０を指し示すようになる。方向フラグ１０５４の方向は逆転し、方向フラグ１０５４が示す成長の方向が左になる。次にメモリ位置１００４にある要素１がスタックから除去され、ヘッド・ポインタ１０５２はメモリ位置１つ分だけ右に後退し、メモリ位置１０１０（空のメモリ位置）を指し示すようになる。したがって、３回の取去り後、ヘッド・ポインタ１０５２はメモリ位置１０１０を指し示し、ベース・ポインタ１０５０はメモリ位置１００６を指し示し、方向フラグ１０５４はスタック成長が左であることを示す。
【００３１】
スタックから最後の要素を除去する場合、ベース・ポインタ１０５０とヘッド・ポインタ１０５２はスワップされ、ヘッド・ポインタ１０５２がメモリ位置１００６にある要素０を指し示し、ベース・ポインタ１０５０がメモリ位置１０１０を指し示すようになる。方向フラグ１０５４の方向は逆転し、スタック成長の方向が右になることを示す。次にメモリ位置１００６にある要素０が除去され、ヘッド・ポインタ１０５２はメモリ位置１つ分だけ左に後退し、メモリ位置１０１０を指し示すようになる。したがって、４回の取去り後、すべてのデータ要素がスタックから除去されたので、ベース・ポインタ１０５０とヘッド・ポインタ１０５２はどちらもメモリ位置１０１０（空のメモリ位置）を指し示す。また、４回の取去り後、方向フラグ１０５４の方向は、スタック成長の方向が右であることを示す。
（）図１６及び図２１を訂正図面の通りに補正する。
【００３２】
主に単方向に成長するデッド要素スタックを両方向に成長するデッド要素スタックに変更するために必要な修正に関連して本発明を説明してきたが、当業者であれば、本発明を適用して他のタイプの両方向に成長するスタックを作成することができることが分かるだろう。例えば、本発明を適用して、デッド要素スタックではなく、両方向に成長する使用済み要素スタックを作成することができる。使用済み要素スタックでは、スタックの開始以前にヘッド・ポインタとベース・ポインタの両方が指し示すメモリ位置を使用して要素を記憶する。しかし、デッド要素（または空の要素）スタックでは、前述のように、要素を記憶するために、スタック開始以前にヘッド・ポインタとベース・ポインタの両方が発生するメモリ位置を使用しない。両方向に成長するスタックを作成するために、他のタイプのスタックを修正することもできる。したがって、本発明はデッド要素スタックに限定されない。
【図面の簡単な説明】
【図１】従来技術により右に成長する５個の要素を備えたスタックを示す図である。
【図２】従来技術により右に成長する１０個の要素を備えたスタックを示す図である。
【図３】従来技術により左に成長する５個の要素を備えたスタックを示す図である。
【図４】従来技術により左に成長する１０個の要素を備えたスタックを示す図である。
【図５】メモリ・アレイの両端に２個のスタックを含み、各スタックが反対方向から伸びる反対側スタックとぶつかるまで成長することができる従来技術のメモリ・アレイを示す図である。
【図６】３個のスタックを含む従来技術のメモリ・アレイを示す図である。
【図７】本発明を実現可能なデータ処理システムのブロック図である。
【図８】本発明により両方向に成長する１個のスタックを含むメモリ・アレイを示す図である。
【図９】本発明により両方向に成長する２個のスタックを含むメモリ・アレイを示す図である。
【図１０】本発明により両方向に成長する３個のスタックを含むメモリ・アレイを示す図である。
【図１１】伝統的な従来技術の単方向スタックにデータを押し込む方法を示す流れ図である。
【図１２】本発明により両方向に成長するスタックにデータを押し込むための例示的なプロセスを示す流れ図である。
【図１３】本発明によりスタックに複数回押し込んだ後のヘッド・ポインタ位置、ベース・ポインタ位置、方向フラグの一例を示す図である。
【図１４】本発明によりスタックに複数回押し込んだ後のヘッド・ポインタ位置、ベース・ポインタ位置、方向フラグの一例を示す図である。
【図１５】本発明によりスタックに複数回押し込んだ後のヘッド・ポインタ位置、ベース・ポインタ位置、方向フラグの一例を示す図である。
【図１６】本発明によりスタックに複数回押し込んだ後のヘッド・ポインタ位置、ベース・ポインタ位置、方向フラグの一例を示す図である。
【図１７】本発明によりスタックに複数回押し込んだ後のヘッド・ポインタ位置、ベース・ポインタ位置、方向フラグの一例を示す図である。
【図１８】伝統的な従来技術の単方向スタックからデータを取り去る方法の一例を示す流れ図である。
【図１９】本発明により両方向に成長するスタックからデータ要素を除去する例示的な方法の流れ図である。
【図２０】本発明により両方向スタックから要素を除去する例示的な方法を示すブロック図である。
【図２１】本発明により両方向スタックから要素を除去する例示的な方法を示すブロック図である。
【図２２】本発明により両方向スタックから要素を除去する例示的な方法を示すブロック図である。
【図２３】本発明により両方向スタックから要素を除去する例示的な方法を示すブロック図である。
【図２４】本発明により両方向スタックから要素を除去する例示的な方法を示すブロック図である。
【符号の説明】
５００  データ処理システム
５０２  プロセッサ
５０４  メイン・メモリ
５０６  ＰＣＩローカル・バス
５０８  ホスト／ＰＣＩ／キャッシュ／ブリッジ
５１０  ＬＡＮアダプタ
５１２  ＳＣＳＩホスト・バス・アダプタ
５１４  拡張バス・インタフェース
５１６  オーディオ・アダプタ
５１８  グラフィック・アダプタ
５１９  オーディオ／ビデオ・アダプタ
５２０  キーボードおよびマウス・アダプタ
５２２  モデム
５２４  メモリ
５２６  ハード・ディスク・ドライブ
５２８  テープ・ドライブ
５３０  ＣＤ−ＲＯＭドライブ
５３２  ＤＶＤ−ＲＯＭドライブ
【図１】
0003579383.tif 000002
【図２】
0003579383.tif 000003
【図３】
0003579383.tif 000004
【図４】
0003579383.tif 000005
【図５】
0003579383.tif 000006
【図６】
0003579383.tif 000007
【図７】
0003579383.tif 000008
【図８】
0003579383.tif 000009
【図９】
0003579383.tif 000010
【図１０】
0003579383.tif 000011
【図１１】
0003579383.tif 000012
【図１２】
0003579383.tif 000013
【図１３】
0003579383.tif 000014
【図１４】
0003579383.tif 000015
【図１５】
0003579383.tif 000016
【図１６】
0003579383.tif 000017
【図１７】
0003579383.tif 000018
【図１８】
0003579383.tif 000019
【図１９】
0003579383.tif 000020
【図２０】
0003579383.tif 000021
【図２１】
0003579383.tif 000022
【図２２】
0003579383.tif 000023
【図２３】
0003579383.tif 000024
【図２４】
0003579383.tif 000025