Java スタックとキューについて紹介する記事
- WBOY転載
- 2022-06-24 12:45:062023ブラウズ
この記事では、スタックとキューの定義、アプリケーション、実装と操作など、主にスタックとキューに関連する問題を整理した java に関する関連知識を提供します。皆さんのお役に立てれば幸いです。
推奨学習: 「java ビデオ チュートリアル 」
スタックとキューを学習する前に、まず線形テーブルとは何かを理解してください。一度に同じ型の 1 つの要素、および配列、リンク リスト、文字列、スタック、キューなどの複数の要素は論理的に連続です
スタックとキューは、配列であろうとリンクであろうと、実際には限定された操作を備えた線形リストです先頭での挿入と削除は末尾でも行うことができますが、スタックとキューは一方の端でのみ挿入し、一方の端でのみ削除できます
1.スタック
1. 定義
要素は一方の端にのみ挿入でき、要素を削除できるのはこの端 (スタックの最上部) にのみあります。スタックは「水のカップ」と考えることができます。また、最初に水カップに入る水はカップの底にあり、後から水カップに入る水はカップの上部にあります。水を注ぎ出すと、カップの上部の水も注ぎ出されます。スタックについても同様です。最初にスタックに押し込まれる要素がスタックの一番下にあり、押し込まれる要素はスタックの一番下にあります。スタックの先頭にあるので、最初にスタックにプッシュされた要素が最後に取り出され、最後にスタックにプッシュされた要素が最初に取り出されます。これもスタックの特徴です。スタック: 「先入れ、後出し、後入れ、先出し」後入れ先出し (LIFO)、要素はスタックの最上位でのみ取り出しおよび追加できます。
1 2 3 4 5 を一度にスタックに入れる 
2. スタック アプリケーション
1. ユビキタス アンドゥ (元に戻す) 操作
エディターで間違った内容を入力した後は、Ctrl z を使用して入力した内容に戻ります。
任意のブラウザーで [戻る] をクリックします。
すべてはこのスタック構造の応用です。
1エディタを使用して元に戻す操作を使用します。一度入力すると、内容がスタックにプッシュされます。再度入力すると、再度スタックにプッシュされます。入力エラーを見つけた場合は、元に戻す操作を使用して内容を保存します。現在のコンテンツ: スタックの最上位にあるエラー コンテンツがポップアップした場合、スタックの最上位にある現在のコンテンツが最後の入力コンテンツになります。
2. Web の閲覧は、Baidu を開く -> csdn を開く -> クリエーション センターを開くのと同じ原理に基づいており、これもスタック構造を使用します。まず、Baidu Web ページがスタックに移動すると、csdn Web ページがスタックにプッシュされ、次にクリエーション センター Web ページがスタックにプッシュされます。csdn ホーム ページに戻りたい場合は、戻る矢印を押してクリエーション センター Web ページをポップアップ表示します。現在スタックの一番上にある csdn ホームページを取り出します。
2. オペレーティング システム スタック
プログラムの再実行中に、関数 A から関数 B が呼び出され、関数 B から関数 C が呼び出されます。実行、どこから始めればよいかわかりますか? 実行を続けます、その背後にスタック構造があります
3. スタックの実装
リンク リストに基づいて実装されたスタック – 連鎖スタック
スタックの実装配列に基づく – 順次スタック (比較的More を使用)
動的配列に基づいてスタックを定義
//基于动态数组实现的顺序栈public class MyStack<e> {
//记录当前栈的元素个数
private int size;
//实际存储数据的动态数组，此时在栈中只能在数组的尾部添加和删除元素
private List<e> data = new ArrayList();
}</e></e>
4. スタック操作
1. スタックに要素を追加
スタックの最上位にのみ追加できます
/**
* 向当前栈中添加元素 -- >压栈操作
* @param val
*/
public void push(E val){
data.add(val);
size++;
}
2。現在、スタックの最上位から要素をポップしています
/**
* 弹出当前栈顶元素,返回栈顶元素的值
* @return
*/
public E pop(){
if (isEmpty()){
//栈为空无法弹出
throw new NoSuchElementException("stack is empty!cannot pop!");
}
//在数组末尾删除元素
E val = data.get(size - 1);
data.remove(size - 1);
size --;
return val;
}
3。スタックの最上位にある現在の要素を表示します。
/**
* 查看当前栈顶元素值，不弹出该元素
* @return
*/
public E peek(){
if (isEmpty()){
throw new NoSuchElementException("stack is empty!cannot peek!");
}
return data.get(size - 1);
}
2. キュー
1. 定義
キュー: 先入れ先出し (FIFO) データ構造 i. 要素は追加のみ可能キューの最後尾からキューに追加され、キューの先頭からのみデキューできます。要素のデキュー順序とエンキュー順序は維持されます。一貫しています
1 2 3 4 5 を順番にキューに入れます
2. キュー アプリケーション
実際のさまざまな「キューイング」操作
3. キューの実装
配列に基づいて実装されたキュー– シーケンシャル キュー
リンク リストに基づいて実装されたキュー – チェーン キュー
デキュー操作はキューの先頭でのみ実行できます。配列によって実装されたキューが使用されている場合、要素がデキューされるたびに、すべての要素がデキューされます。残りの要素は 1 ユニット前に移動する必要があります。このとき、リンク リストによって実装されたキューの方がキュー構造に適しています。要素を削除するには、ヘッド ノードを削除するだけで済みます。要素を末尾に追加します。リンクされたリスト
public interface Queue<e> {
//入队操作
void offer(E val);
//出队操作
E poll();
//查看队首元素
E peek();
boolean isEmpty();}</e>
スタックの場合、
FIFOキュー
両端キュー
循環キュー
優先キュー
など、キュー実装の多くのサブクラスがあります。キューは実装する必要があります
4.FIFO キュー
1.FIFO キューを定義します
// An highlighted blockvar foo = 'bar';
2.キューに要素を追加します
public void offer(E val) {
Node<e> node = new Node(val);
if (head == null){
head = tail = node;
}else{
//链表的尾插
tail.next = node;
tail = node;
}
size++;
}</e>
3。現在のキューの先頭から要素をデキューします
public E poll() {
if (isEmpty()){
throw new NoSuchElementException("queue is empty! cannot poll!");
}
//头删
E val = head.val;
Node<e> node = head;
head = head.next;
node.next = node = null;
size--;
return val;
}</e>
4。現在のキューの先頭要素を表示します
public E peek() {
if (isEmpty()){
throw new NoSuchElementException("queue is empty!cannot peek!");
}
return head.val;
}
5.循环队列
1.定义：基本上都是使用固定长度的数组来实现，数组在实现队时，若从数组头部删除元素需要频繁的移动后面的元素，效率比较低；出队和入队操作，使用两个引用，一个head，一个tail,添加元素在数组的尾部添加，删除元素只需要移动head引用指向的地址即可（逻辑删除）
2.应用：操作系统的生产消费者模型，MySQL数据库的InnoDB存储引擎的redo日志
3.循环队列就是使用长度固定的数组来实现，数组头部就是队首（head），数组的尾部就是队尾（tail），数组[head…tail)时循环队列的有效元素
head永远指向循环队列的第一个元素
tai永远指向循环队列有效元素的后一个位置
此时循环队列的有效元素就为7 9 1两个元素
循环队列出队一个元素，就只用让head引用向后移动一个位置
此时循环队列的有效元素就只有9 和 1 两个元素了
再出队一个元素，但此时head引用已经走到末尾了，所谓循环队列就是当head或者tail引用走到数组末尾时，再向后移动就是返回数组头部的操作，循环队列最大好处就是进行元素的删除的时候不需要进行数据的搬移操作，当有新的元素添加到队列中就会覆盖掉原来的元素，就只需要将tail索引位置覆盖上新的元素，再让tail再向后移动
当队列为空时,head == tail
当队列已“满”时，head == tail
循环队列需要注意的关键点
1.因此当head 和 tail相等时，没法区分此时循环队列已满，还是为空，因此在循环队列中，若(tail + 1) % n == head就认为循环队列已满
此时循环队列就已经满了，在循环队列中就会浪费一个空间，判断队列是否已满
2.head和tail的移动不能简单的 + 1，使用取模操作，取数组长度
tail = (tail + 1) % n
head = (head + 1) % n
对数组长度取模的本质：
当head和tai走到数组最后一个索引位置时，下一次要返回数组头部，就必须用 + 1对数组长度取模
3.head == tail时，认为队列为空
6.循环队列的操作
1.定义一个循环队列
//基于整形的循环队列public class LoopQueue implements Queue<integer> {
//定长数组
private Integer[] data;
//指向队首元素
int head;
//指向队尾元素的下一个元素
int tail;
public LoopQueue(int size){
data = new Integer[size + 1];
}}</integer>
2.向循环队列中添加一个元素
@Override public void offer(Integer val) {
if (isFull()){
throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
}
data[tail] = val;
tail = (tail + 1) % data.length;
}
3.从循环队列中出队一个元素
@Override public Integer poll() {
if (isEmpty()){
throw new NoSuchElementException("loopQueue is empty!cannot poll!");
}
Integer val = data[head];
head = (head + 1) % data.length;
return val;
}
4.查看当前循环队列队首元素
@Override public Integer peek() {
if (isEmpty()){
throw new NoSuchElementException("loopQueue is empty!cannot peek!");
}
return data[head];
}
5.判断当前循环队列是否为空
@Override public boolean isEmpty() {
return head == tail;
}
6.判断当前循环队列是否已满
public boolean isFull(){
return (tail + 1) % data.length == head;
}
7.toString方法
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("front [");
//最后一个有效元素的索引
int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
for (int i = head; i != tail;) {
sb.append(data[i]);
if (i != lsatIndex){
sb.append(", ");
}
i = (i + 1) % data.length;
}
sb.append("] tail");
return sb.toString();
}
7.双端队列
双端队列：Deque是Queue的子接口，这个队列既可以尾插，头出；也可以头插，尾出
双端队列的一个常用子类就是LinkedList，不管使用栈还是队列，都可以统一使用双端队列接口
1.现在需要一个栈
2.现在需要一个队列
推荐学习：《java视频教程》
以上がJava スタックとキューについて紹介する記事の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。