スタックとキュー:
通常、これはプログラマーがアルゴリズムの概念を支援するツールとして使用され、ライフサイクルが短く、実行時にのみ作成されます。
アクセスは制限されており、特定の瞬間に、1つのデータのみを読み取るか削除できます。
これは抽象的な構造であり、アレイやリンクリストを使用してスタックを実装するなど、ユーザーには見えない内部実装メカニズムがあります。
スタック構造をシミュレートします
同時に、1つのデータのみにアクセスすることが許可されており、スタック内と外出の両方の後半での後半の時間の複雑さはO(1)です。つまり、スタック内のデータ項目の数に依存しません。操作は、スタックのストレージ構造として配列を使用して、比較的速いです
パブリッククラススタック<t> {private int max;プライベートT [] ary;プライベートINTトップ; //ポインター、スタックパブリックスタック(int size)の最上位要素への添え付け{this.max = size; ary =(t [])new Object [max]; TOP = -1; } // stack public void push(t data){if(!isfull())ary [++ top] = data; } // stack public t pop(){if(isempty()){return null; } return ary [top-]; } //スタックの上部を表示public t peek(){return ary [top]; } // Stack empty public boolean isempty(){return top == -1; } //はスタックフルパブリックブールisfull(){return top == max -1; } //サイズpublic int size(){return top + 1; } public static void main(string [] args){stacks <integer> stack = new stacks <integer>(3); for(int i = 0; i <5; i ++){stack.push(i); System.out.println( "size:" + stack.size()); } for(int i = 0; i <5; i ++){integer peek = stack.peek(); System.out.println( "Peek:" + Peek); System.out.println( "size:" + stack.size()); } for(int i = 0; i <5; i ++){integer pop = stack.pop(); System.out.println( "pop:" + pop); System.out.println( "size:" + stack.size()); } system.out.println( "----"); for(int i = 5; i> 0; i--){stack.push(i); System.out.println( "size:" + stack.size()); } for(int i = 5; i> 0; i--){integer peek = stack.peek(); System.out.println( "Peek:" + Peek); System.out.println( "size:" + stack.size()); } for(int i = 5; i> 0; i--){integer pop = stack.pop(); System.out.println( "pop:" + pop); System.out.println( "size:" + stack.size()); }}}上記の例では、配列のサイズにする必要があるため、最大規制があります。制限がない場合は、ストレージに他の構造を使用できます。もちろん、新しい長さの配列も新しいことができます。
たとえば、LinkedListストレージを使用してスタックを実装します
public class stackss <t> {private linkedlist <t> datas; public stackss(){datas = new linkedlist <t>(); } // Stack public void push(t data){datas.addlast(data); } //スタックpublic top(){return datas.removelast(); } //スタックの上部をチェックpublic teek(){return datas.getLast(); } //スタックが空であるかどうかのpublic boolean isempty(){return datas.isempty(); } // size public int size(){return datas.size(); } public static void main(string [] args){stacks <integer> stack = new stacks <integer>(3); for(int i = 0; i <5; i ++){stack.push(i); System.out.println( "size:" + stack.size()); } for(int i = 0; i <5; i ++){integer peek = stack.peek(); System.out.println( "Peek:" + Peek); System.out.println( "size:" + stack.size()); } for(int i = 0; i <5; i ++){integer pop = stack.pop(); System.out.println( "pop:" + pop); System.out.println( "size:" + stack.size()); } system.out.println( "----"); for(int i = 5; i> 0; i--){stack.push(i); System.out.println( "size:" + stack.size()); } for(int i = 5; i> 0; i-){stack.push(i); System.out.println( "size:" + stack.size()); } for(int i = 5; i> 0; i--){integer peek = stack.peek(); System.out.println( "Peek:" + Peek); System.out.println( "size:" + stack.size()); } for(int i = 5; i> 0; i--){integer pop = stack.pop(); System.out.println( "pop:" + pop); System.out.println( "size:" + stack.size()); }}}たとえば、statck構造を使用した単語逆方向の順序
public class wordReverse {public static void main(string [] args){reverse( "co。、ltd。"); } static void Reverse(string word){if(word == null)return; stackss <character> stack = new stackss <character>(); char [] chararray = word.tochararray(); int len = chararray.length; for(int i = 0; i <len; i ++){stack.push(chararray [i]); } stringbuilder sb = new StringBuilder(); while(!stack.isempty()){sb.append(stack.pop()); } system.out.println( "反転後:" + sb.toString()); }}印刷:
逆転後:ソーシャルスタイル
シミュレーションキュー(一般的なキュー、両端のキュー、優先キュー)
列:
最初に、キューイングの問題に対処します。最初のキュー、最初のプロセス、1行目、2行目など。前のプロセスが完了し、挿入および除去操作の時間の複雑さはO(1)です。背面から挿入し、正面から両端のキューを取り外します。
つまり、キューの両端に挿入して削除できます:InsertLeft、Insertright、Removeleft、Removeright
スタックとキューを含む関数。 InsertLeftとRemoveleftを削除すると、スタックと同じになります。 InsertLeftとRemoverightを削除すると、キューと同じになります。一般的に、使用頻度は低く、時間の複雑さo(1)
優先キュー:
優先順位でソートされた内部シーケンスを維持します。挿入するときは、挿入位置、時間の複雑さo(n)、削除o(1)を比較して見つける必要があります
/**最初にキューすると、ポインターは挿入位置を示し、ポインターはデータ項目が取り出される位置を示します*/ public class queueq <t> {private int max;プライベートT [] ary;プライベートイントフロント; //チームのヘッドは、プライベートINTリアが取り出されているデータ項目の位置を示します。 //チームのテールは、プライベートinitemsが挿入されているデータ項目の位置を示します。 //実際のデータ項目パブリックQueueq(int size){this.max = size; ary =(t [])new Object [max]; front = 0;リア= -1; nitems = 0; } //キューパブリックボイドインサート(t t)のテールを挿入{if(rece == max -1){//実際のキューの終わりに達し、最初から開始、rece = -1; } ary [++リア] = t; nitems ++; } //チームの頭を削除しますpublic public t remove(){t temp = ary [front ++]; if(front == max){//キューは終わりに達し、最初から開始し、最初から開始、最初から開始、最初から開始、0。 } nitems-; return temp; } //チームの責任者を表示しますpeek(){return ary [front]; } public boolean isempty(){return nitems == 0; } public boolean isfull(){return nitems == max; } public int size(){return nitems; } public static void main(string [] args){queueq <integer> queue = new queuq <integer>(3); for(int i = 0; i <5; i ++){queue.insert(i); system.out.println( "size:" + queue.size()); } for(int i = 0; i <5; i ++){integer peek = queue.peek(); System.out.println( "Peek:" + Peek); system.out.println( "size:" + queue.size()); } for(int i = 0; i <5; i ++){integer remove = queue.remove(); system.out.println( "remove:" + remove); system.out.println( "size:" + queue.size()); } system.out.println( "----"); for(int i = 5; i> 0; i-){queue.insert(i); system.out.println( "size:" + queue.size()); } for(int i = 5; i> 0; i--){integer peek = queue.peek(); System.out.println( "Peek:" + Peek); system.out.println( "size:" + queue.size()); } for(int i = 5; i> 0; i-){integer remove = queue.remove(); system.out.println( "remove:" + remove); system.out.println( "size:" + queue.size()); }}} /**両端のキュー<SPAN STYLE = "Whiteスペース:pre"> </span>両端で挿入および削除*/public class queueqt <t> {private linkedlist <t> list; public queueqt(){list = new linkedlist <t>(); } //キューヘッドのpublic void insertleft(t t){list.addfirst(t); } //キューテールを挿入public public void insertright(t t){list.addlast(t); } //キューヘッドのpublic t removeleft(){return list.removefirst(); } //チームの終わりを削除public t removeright(){return list.removelast(); } //チームの責任者を表示しますpeekleft(){return list.getFirst(); } //チームの終わりを表示しますpeekright(){return list.getLast(); } public boolean isempty(){return list.isempty(); } public int size(){return list.size(); }} /**優先キューは優先度でソートされ、注文されたキューです*/ public class queueqp {private int max; private int [] ary;プライベートインターメント; //実際のデータ項目パブリックQueueQP(int size){this.max = size; ary = new int [max]; nitems = 0; } //キューの端を挿入public public void insert(int t){int j; if(nitems == 0){ary [nitems ++] = t; } else {for(j = nitems-1; j> = 0; j-){if(t> ary [j]){ary [j + 1] = ary [j]; //前のものを次のものに割り当てることは、挿入ソートの使用と同等です。指定されたシーケンスは当初注文されているため、効率o(n)} else {break; }} ary [j + 1] = t; nitems ++; } system.out.println(arrays.toString(ary)); } //チームの首長を削除public int remove(){return ary [ - nitems]; //小さな優先度を削除} //チームの最優先事項を表示public int peekmin(){return ary [nitems -1]; } public boolean isempty(){return nitems == 0; } public boolean isfull(){return nitems == max; } public int size(){return nitems; } public static void main(string [] args){queueqp queue = new queueqp(3); queue.insert(1); queue.insert(2); queue.insert(3); int remove = queue.remove(); system.out.println( "remove:" + remove); }}