JavaJava · Chapterبەش 12 · Lectureوانە 12.1

LinkedList, Iterators, Stacks and QueuesLinkedList، خولپێکەرەکان، ستاکەکان و کیووەکان

Java's LinkedList with addFirst, getFirst and removeFirst; what a chain of nodes is and when it is faster or slower than ArrayList (measured); the List interface; walking and removing with an Iterator and a ListIterator; a stack with ArrayDeque's push, pop and peek, and why not the old Stack class; a queue with offer, poll and peek and the two families of queue methods; a deque used at both ends; a first look at PriorityQueue. Examples: an undo history and a print queue.

LinkedListـی Java بە addFirst، getFirst و removeFirst؛ زنجیرەی چییە و کەی لە ArrayList خێراترە یان خاوترە (بە پێوانە)؛ List؛ ڕۆیشتن و لابردن بە و ListIterator؛ بە push، pop و peekـی ArrayDeque و بۆچی کلاسی کۆنی Stack نا؛ بە offer، poll و peek و دوو خێزانەکەی ؛ کە لە هەردوو سەرەوە بەکار دێت؛ یەکەم سەیرکردنی PriorityQueue. نموونەکان: مێژووی و چاپ.

23 min read21 خولەک خوێندنەوە · 22 stepsهەنگاو

What you will learnچی فێر دەبیت

Use LinkedList's methods for both ends and explain how its chain of nodes differs from ArrayList's array.
Choose between ArrayList and LinkedList from measured facts, and write methods for the List interface.
Walk a collection with an Iterator or a ListIterator and remove elements safely during the walk.
Use an ArrayDeque as a stack (push, pop, peek) and as a queue (offer, poll, peek), and explain why it replaces the old Stack class.
Tell the throwing queue methods from those that return null, and say what a PriorityQueue does.

هەردوو سەری LinkedList بەکار بهێنیت و ڕوونی بکەیتەوە زنجیرەی چۆن لە ناو ArrayList جیاوازە.
بە پشتبەستن بە پێوانە لە نێوان ArrayList و LinkedListـدا هەڵبژێریت و بۆ List بنووسیت.
بە یان ListIteratorـێک بە ناو کۆکراوەیەکدا بڕۆیت و لە کاتی ڕۆیشتندا بە سەلامەتی لاببەیت.
ArrayDeque وەک (push، pop، peek) و وەک (offer، poll، peek) بەکار بهێنیت و ڕوونی بکەیتەوە بۆچی جێی کلاسی کۆنی Stack دەگرێتەوە.
کە فڕێ دەدەن لەوانە جیا بکەیتەوە کە null دەگەڕێننەوە و بڵێیت PriorityQueue چی دەکات.

From ArrayList to more data structuresلە ArrayListـەوە بۆ پێکهاتەی دراوەی زیاتر

You already keep many values in an ArrayList (ArrayList) and find them by key in a HashMap (HashMap). Each one is a : a way to store data together with the operations it allows (What is a data structure?).

پێشتر زۆر لە ArrayListـێکدا هەڵدەگریت (ArrayList) و بە لە HashMapـێکدا دەیاندۆزیتەوە (HashMap). هەر یەکەیان : ڕێگەیەک بۆ هەڵگرتنی لەگەڵ ئەو کارانەی ڕێگەیان پێ دەدات (پێکهاتەی دراوە چییە؟).

This lesson meets more of java.util: LinkedList, a chain of nodes; the Iterator, which walks through any collection; ArrayDeque, which works as a or a ; and, at the end, PriorityQueue. The dashed boxes are interfaces (Interfaces): promises of methods that the classes below them keep.

ئەم وانەیە زیاتر لە java.util دەناسێنێت: LinkedList، زنجیرەیەک لە ؛ Iterator کە بە ناو هەر کۆکراوەیەکدا دەڕوات؛ ArrayDeque کە وەک یان کار دەکات؛ لە کۆتاییشدا PriorityQueue. سندووقە پچڕپچڕەکان (نێوبەستەکان): بەڵێنی کۆمەڵێک کە ژێریان دەیانبەنە سەر.

The collections of this lesson and the interfaces they keepکۆکراوەکانی ئەم وانەیە و CêIT

LinkedList: working at both endsLinkedList: کارکردن لە هەردوو سەرەوە

LinkedList is in java.util and has every method of ArrayList (add, get, size …). It adds methods for the two ends: addFirst, addLast, getFirst, getLast, removeFirst and removeLast. A bus route fits it well, because stops are added and dropped at the ends:

LinkedList لە java.utilـدایە و هەموو ArrayListـی هەیە (add، get، size …). تایبەت بە دوو سەرەکەش زیاد دەکات: addFirst، addLast، getFirst، getLast، removeFirst و removeLast. هێڵی پاسێک بە باشی لەگەڵیدا دەگونجێت، چونکە وێستگەکان لە دوو سەرەکەوە زیاد دەکرێن و لادەبرێن:

BusRoute.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.LinkedList;

public class BusRoute {
    public static void main(String[] args) {
        LinkedList<String> stops = new LinkedList<>();
        stops.add("Koya");
        stops.add("Ranya");
        stops.addFirst("Hawler");         // a new first element
        stops.addLast("Qaladze");         // a new last element (the same as add)
        System.out.println(stops);
        System.out.println("First: " + stops.getFirst() + ", last: " + stops.getLast());
        System.out.println("get(1): " + stops.get(1) + ", size: " + stops.size());
        String gone = stops.removeFirst();
        stops.removeLast();
        System.out.println("Removed " + gone + " and the last stop: " + stops);
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 8-9

addLast does the same as add: a new last element.

addLast هەمان کاری add دەکات: نوێی کۆتایی.

Lineدێڕی 13-14

removeFirst and removeLast take an element away and return it.

removeFirst و removeLast لادەبەن و دەیگەڕێننەوە.

Animation. Two nodes, Koya and Ranya; each has a reference to the next node and one to the previous node; first points at Koya and last at Ranya. stops.addFirst("Hawler") makes one new node and changes only two references: Hawler's next points to Koya, Koya's previous points back to Hawler, and first moves to Hawler; nothing moves. stops.addLast("Qaladze") does the same at the other end. stops.removeFirst() moves first on to Koya and lets Hawler go. println shows [Koya, Ranya, Qaladze]: no element was shifted, which is why the two ends are fast. — addFirst and removeFirst only re-link two referencesaddFirst و removeFirst تەنیا دوو دەگۆڕنCêIT

An empty LinkedList: get or peek?LinkedListـێکی بەتاڵ: get یان peek؟

On an empty list getFirst() has nothing to give, so it throws a NoSuchElementException (Exceptions). peekFirst() and pollFirst() answer null instead:

لەسەر بەتاڵ، getFirst() هیچی نییە بیدات، بۆیە NoSuchElementException فڕێ دەدات (هەڵاوێردەکان). لە جیاتی ئەوە peekFirst() و pollFirst() بە null وەڵام دەدەنەوە:

EmptyRoute.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.LinkedList;

public class EmptyRoute {
    public static void main(String[] args) {
        LinkedList<String> stops = new LinkedList<>();
        System.out.println("peekFirst: " + stops.peekFirst());
        System.out.println("pollFirst: " + stops.pollFirst());
        System.out.println("getFirst: " + stops.getFirst());
    }
}

Use getFirst when an empty list would be a bug, and check isEmpty() before you call it. Use peekFirst or pollFirst when an empty list is normal, and test the answer for null. Queues have the same two families of methods (Two families).

کاتێک بەتاڵ هەڵەیەک بێت getFirst بەکار بهێنە و پێش بانگکردنی isEmpty() بپشکنە. کاتێک بەتاڵبوون ئاسایی بێت peekFirst یان pollFirst بەکار بهێنە و تاقی بکەرەوە ئاخۆ وەڵامەکە nullـە. هەمان دوو خێزانە هەیە (دوو خێزان).

Inside: boxes in a row, or a chain of nodesلە ناوەوە: خانە لە ڕیزێکدا، یان زنجیرەیەک نۆد

An ArrayList keeps its elements in one array: boxes side by side in memory. get(2) jumps straight to box 2. But add(0, x) must first move every element one box to the right.

ArrayList لە یەک هەڵدەگرێت: خانەکان لە لە تەنیشت یەکترن. get(2) ڕاستەوخۆ باز دەداتە خانەی 2. بەڵام add(0, x) دەبێت سەرەتا هەموو یەک خانە بەرەو ڕاست بجووڵێنێت.

A LinkedList is a : each element sits in its own , a small object that also holds two , one to the next node and one to the previous node. The list itself only remembers the first and the last node. Adding at an end makes one node and changes two references; nothing moves. But get(2) must walk from the nearer end, node by node.

LinkedList : هەر لە تایبەت بە خۆیدایە، بچووک کە هەروەها دوو هەڵدەگرێت، یەکێک بۆ دواتر و یەکێک بۆ پێشتر. خودی تەنیا یەکەم و دوایین لەبیر دەگرێت. زیادکردن لە سەرێکەوە یەک دروست دەکات و دوو دەگۆڕێت؛ هیچ شتێک ناجووڵێت. بەڵام get(2) دەبێت لە سەرە نزیکترەکەوە، بە ، بڕوات.

One array, or a chain of nodes linked both waysیەک ، یان زنجیرەیەک کە بە هەردوو ئاڕاستە بەستراونCêIT

Train wagonsواگۆنەکانی شەمەندەفەر

A train is a linked list: each wagon is coupled only to the wagon in front and the wagon behind. Adding a wagon at either end takes one coupling. To reach the tenth wagon you walk through nine. An ArrayList is more like a row of numbered lockers: you go straight to locker 10, but squeezing a new locker in at the start means moving all the others.

شەمەندەفەرێک : هەر واگۆنێک تەنیا بە واگۆنی پێشەوە و واگۆنی دواوەی خۆیەوە بەستراوە. زیادکردنی واگۆنێک لە هەر سەرێکەوە تەنیا یەک بەستنەوەی دەوێت. بۆ گەیشتن بە واگۆنی دەیەم دەبێت بە ناو نۆ واگۆندا تێپەڕیت. ArrayList زیاتر لە ڕیزێک دۆڵابی ژمارەدار دەچێت: ڕاستەوخۆ دەچیتە لای دۆڵابی ⁦10⁩، بەڵام بۆ خستنە ناوەوەی دۆڵابێکی نوێ لە سەرەتادا دەبێت هەموو ئەوانی تر بجووڵێنیت.

Where the analogy stops workingسنووری ئەم نموونەیە

A program cannot jump into the middle of the chain: it must still walk to a middle node before it can unlink it.

بەرنامە ناتوانێت باز بداتە ناوەڕاستی زنجیرەکە: هێشتا دەبێت بڕوات بۆ ناوەڕاست پێش ئەوەی لە زنجیرەکە جیای بکاتەوە.

Which is faster? Measured, not guessedکامیان خێراترە؟ بە پێوانە، نەک بە مەزەندە

You will often read that "LinkedList is faster for adding and removing". That is only half true, so we measured. ListTimes does each task n times on a fresh list. It repeats this five times and keeps the best run, because the first runs are slower while the warms up:

زۆر جار دەخوێنیتەوە کە «LinkedList بۆ زیادکردن و لابردن خێراترە». ئەمە تەنیا نیوەی ڕاستییە، بۆیە پێوانەمان کرد. ListTimes هەر کارێک n جار لەسەر نوێ دەکات. ئەمە پێنج جار دووپاتە دەکاتەوە و باشترینیان هەڵدەگرێت، چونکە یەکەم جارەکان خاوترن تا گەرم دەبێت:

ListTimes.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListTimes {
    static long sink;                                // keeps the JVM from skipping work

    static List<Integer> newList(boolean linked, int size) {
        List<Integer> list = linked ? new LinkedList<>() : new ArrayList<>();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        return list;
    }

    // one task on a fresh list; returns nanoseconds
    static long once(String task, boolean linked, int n) {
        boolean full = task.equals("get(i) for each i") || task.equals("remove at the front");
        List<Integer> list = newList(linked, full ? n : 0);
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            switch (task) {
                case "add at the end" -> list.add(i);
                case "add at the front" -> list.add(0, i);
                case "add in the middle" -> list.add(list.size() / 2, i);
                case "get(i) for each i" -> sink += list.get(i);
                case "remove at the front" -> sink += list.remove(0);
            }
        }
        return System.nanoTime() - start;
    }

    // the same task 5 times: the first runs warm the JVM up, so keep the best
    static long best(String task, boolean linked, int n) {
        long best = Long.MAX_VALUE;
        for (int round = 0; round < 5; round++) {
            best = Math.min(best, once(task, linked, n));
        }
        return best / 1_000_000;                     // milliseconds
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        String[] tasks = {"add at the end", "add at the front", "remove at the front",
                          "add in the middle", "get(i) for each i"};
        System.out.println("n = " + n + ", best of 5 runs, in milliseconds");
        System.out.printf("%-22s %10s %11s%n", "task (n times)", "ArrayList", "LinkedList");
        for (String task : tasks) {
            System.out.printf("%-22s %10d %11d%n", task, best(task, false, n), best(task, true, n));
        }
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 6

Without sink the JVM could skip work whose result is never used.

بەبێ sink دەتوانێت ئەو کارە فەرامۆش بکات کە ئەنجامەکەی هەرگیز بەکار نایەت.

Lineدێڕی 34-39

Five runs, keep the fastest.

پێنج جار، خێراترینیان هەڵبگرە.

LinkedList wins at the front and loses badly in the middleLinkedList لە سەرەتادا دەباتەوە و لە ناوەڕاستدا بە خراپی دەدۆڕێنێتCêIT

Read the pattern, not the exact numbers. At the front, ArrayList shifts every element, so doubling n makes the work about four times bigger (from 18 to 79 ms); LinkedList only changes two references. But get(i) and adding in the middle are far slower on LinkedList, because it must first walk to position i. In big-O words (Big-O), one get(i) is $O(1)$ on an ArrayList and $O(n)$ on a LinkedList.

سەیری شێوەکە بکە، نەک ژمارە وردەکان. لە سەرەتادا ArrayList هەموو دەجووڵێنێت، بۆیە دووجارکردنی n کارەکە نزیکەی چوار ئەوەندە دەکات (لە ⁦18⁩ بۆ ⁦79 ms⁩)؛ LinkedList تەنیا دوو دەگۆڕێت. بەڵام get(i) و زیادکردن لە ناوەڕاستدا لەسەر LinkedList زۆر خاوترن، چونکە سەرەتا دەبێت بڕوات بۆ شوێنی i. بە زمانی ⁦Big-O⁩ (⁦Big-O⁩)، یەک get(i) لەسەر ArrayList $O(1)$ ـە و لەسەر LinkedList $O(n)$ .

In practiceلە پراکتیکدا

Use ArrayList for ordinary lists. For a stack or a queue use ArrayDeque (below): it is fast at both ends and does not build a node object for every element. LinkedList pays off in few cases, for example when you remove many elements from the middle through an iterator while walking, or when one object must be both a List and a Deque.

بۆ ئاسایی ArrayList بەکار بهێنە. بۆ یان ArrayDeque بەکار بهێنە (لە خوارەوە): لە هەردوو سەرەوە خێرایە و بۆ هەر دروست ناکات. LinkedList تەنیا لە چەند حاڵەتێکی کەمدا سوودی هەیە، بۆ نموونە کاتێک لە کاتی ڕۆیشتندا زۆر لە ناوەڕاستەوە بە لادەبەیت، یان کاتێک یەک دەبێت هەم List بێت هەم Deque.

One method for both: the List interfaceیەک میتۆد بۆ هەردووکیان: نێوبەستەی List

Both classes keep the promises of the List interface (The List interface). So a method whose parameter type is List accepts either one, and you can switch the class later without touching the method:

هەردوو بەڵێنەکانی List دەبەنە سەر (نێوبەستەی List). کەواتە کە جۆری List بێت هەر یەکێکیان وەردەگرێت و دەتوانیت دواتر بگۆڕیت بەبێ دەستدان لە :

AnyList.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class AnyList {
    static void addCities(List<String> list) {       // any kind of List
        list.add("Duhok");
        list.add(0, "Zakho");
        list.add("Akre");
        System.out.println(list.getClass().getSimpleName() + ": " + list + ", get(1) = " + list.get(1));
    }

    public static void main(String[] args) {
        addCities(new ArrayList<>());
        addCities(new LinkedList<>());
    }
}

A List variable promises only List methods. In Java 17 addFirst belongs to LinkedList and Deque, not to List, so the compiler refuses it on a List variable:

List تەنیا بەڵێنی List دەدات. لە ⁦Java 17⁩ـدا addFirst هی LinkedList و Dequeـە، نەک هی List، بۆیە لەسەر List ڕەتی دەکاتەوە:

ListFirst.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.LinkedList;
import java.util.List;

public class ListFirst {
    public static void main(String[] args) {
        List<String> stops = new LinkedList<>();
        stops.addFirst("Hawler");
        System.out.println(stops);
    }
}

The Iterator: hasNext and nextخولپێکەر: hasNext و next

Every collection can give you an : an object that walks through it, one element at a time. Picture a that stands between the elements. hasNext() asks whether there is an element after the cursor; next() jumps over that element and returns it. Calling next() at the end throws NoSuchElementException:

هەموو کۆکراوەیەک دەتوانێت بداتە دەستت: کە بە ناویدا دەڕوات، بە . بهێنە بەرچاوت کە لە نێوان وەستاوە. hasNext() دەپرسێت ئاخۆ لە دوای هەیە؛ next() بەسەر ئەو باز دەدات و دەیگەڕێنێتەوە. بانگکردنی next() لە کۆتاییدا NoSuchElementException فڕێ دەدات:

WalkNames.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class WalkNames {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Aram", "Shilan", "Karwan"));
        Iterator<String> it = names.iterator();
        while (it.hasNext()) {                       // is there an element after the cursor?
            String name = it.next();                 // jump over it and give it back
            System.out.println(name + " has " + name.length() + " letters");
        }
        System.out.println("hasNext: " + it.hasNext());
        it.next();                                   // nothing is left
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 9-10

The usual loop: ask, then take.

باو: بپرسە، پاشان وەریبگرە.

The cursor stands between elements; next() jumps over one لە نێوان دەوەستێت؛ ⁦next()⁩ بەسەر یەکێکدا باز دەداتCêIT

A for-each loop is this while loop in short: Java turns for (String name : names) into an iterator with hasNext() and next(). That is why for-each works on every collection: lists, sets, deques (for-each).

کورتکراوەی ئەم : Java for (String name : names) دەکات بە بە hasNext() و next()ـەوە. هەر بۆیە ⁦for-each⁩ لەسەر هەموو کۆکراوەیەکی کار دەکات: ، ، (⁦for-each⁩).

Removing safely: Iterator.remove()لابردنی بێ مەترسی: ⁦Iterator.remove()⁩

You met this crash in Removing inside a loop: removing through the list inside a for-each loop. The loop's hidden iterator notices that the list changed behind its back and throws a ConcurrentModificationException, an :

ئەم تێکشکانەت لە لابردن لە ناو خولێکدا بینی: لابردن بە لە ناو . هەست دەکات کە لە پشتییەوە گۆڕاوە و ConcurrentModificationException فڕێ دەدات، کە :

ForEachRemove.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.List;

public class ForEachRemove {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(List.of(90, 45, 30, 75, 48));
        for (Integer mark : marks) {
            if (mark < 50) {
                marks.remove(mark);                  // an Integer: removes the value
            }
        }
        System.out.println(marks);
    }
}

The fix is the iterator's own remove(). It removes the element that next() just returned and keeps its own count right:

چارەسەرەکە remove()ـی خودی . ئەو لادەبات کە next() تازە گەڕاندوویەتییەوە و ژماردنەکەی خۆی ڕێک دەهێڵێتەوە:

IteratorRemove.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class IteratorRemove {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(List.of(90, 45, 30, 75, 48));
        Iterator<Integer> it = marks.iterator();
        while (it.hasNext()) {
            int mark = it.next();
            if (mark < 50) {
                it.remove();                         // removes the mark next() just gave
            }
        }
        System.out.println(marks);
    }
}

Remove through the iterator, never through the listبە لاببە، هەرگیز بە ناCêIT

No exception does not mean correctنەبوونی هەڵاوێردە واتای ڕاستبوون نییە

With three marks, [90, 45, 30], the same for-each code prints [90, 30] with no exception at all (a real run): removing 45 made the loop end early, so 30 was never checked. Do not wait for the exception to show you the bug; remove through the iterator, or with removeIf (Lambdas).

بە سێ نمرە، [90, 45, 30]، هەمان کۆدی ⁦for-each⁩ بەبێ هیچ [90, 30] چاپ دەکات (کارپێکردنی ڕاستەقینە): لابردنی ⁦45⁩ وای کرد زوو کۆتایی بێت، بۆیە ⁦30⁩ هەرگیز نەپشکنرا. چاوەڕێی مەکە تا پیشانت بدات؛ بە لاببە، یان بە removeIf (Lambda).

ListIterator: both directions, and setListIterator: هەردوو ئاڕاستە و set

A list can also give you a ListIterator. It adds hasPrevious() and previous() to walk backwards, nextIndex() for the cursor's position, set(x) to replace the element next() just returned, and add(x) to insert at the cursor. Here every mark gets 5 bonus marks, never above 100, and then the cursor walks back:

دەتوانێت ListIteratorـیشت بداتێ. hasPrevious() و previous() بۆ ڕۆیشتن بە پاشەوە زیاد دەکات، nextIndex() بۆ شوێنی ، set(x) بۆ گۆڕینی ئەو next() تازە گەڕاندوویەتییەوە و add(x) بۆ خستنە ناوەوە لە شوێنی . لێرەدا هەر نمرەیەک 5 نمرەی دیاری وەردەگرێت، هەرگیز لە ⁦100⁩ زیاتر نا، پاشان بە پاشەوە دەگەڕێتەوە:

Bonus.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Bonus {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(List.of(70, 96, 58));
        ListIterator<Integer> it = marks.listIterator();
        while (it.hasNext()) {
            int index = it.nextIndex();
            int mark = it.next();
            it.set(Math.min(100, mark + 5));         // replace the mark next() just gave
            System.out.println("index " + index + ": " + mark + " -> " + marks.get(index));
        }
        System.out.print("Backwards:");
        while (it.hasPrevious()) {                   // the cursor is at the end now
            System.out.print(" " + it.previous());
        }
        System.out.println();
    }
}

ListIterator walks both ways and can change elements on the wayListIterator بە هەردوو ئاڕاستە دەڕوات و دەتوانێت لە ڕێگادا بگۆڕێتCêIT

A stack: last in, first outستاک: دوایین هاتوو، یەکەم دەرچوو

A lets you reach only its top. You push an element onto the top, pop the top element off, and peek at the top without removing it. The last element pushed is the first one out: LIFO, last in, first out. The idea, its uses and step-by-step traces are in Stacks; here is the Java way, an ArrayDeque used through the Deque interface:

تەنیا ڕێگەت پێ دەدات دەستت بگاتە سەرەوەکەی. بە push دەخەیتە سەرەوە، بە pop سەرەوە لادەبەیت و بە peek سەیری سەرەوە دەکەیت بەبێ لابردن. دوایین کە push کرا یەکەم دانەیە کە دەردەچێت: LIFO، دوایین هاتوو، یەکەم دەرچوو. بیرۆکەکە، بەکارهێنانەکانی و بەدواداچوونی هەنگاو بە هەنگاو لە ستاکەکانـدان؛ ئەمەش ڕێگەی Javaـیە، ArrayDequeـێک لە ڕێگەی Dequeـەوە:

Plates.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Deque;

public class Plates {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("red plate");
        stack.push("blue plate");
        stack.push("green plate");
        System.out.println(stack);                       // the top is printed first
        System.out.println("peek: " + stack.peek());     // look at the top
        System.out.println("pop:  " + stack.pop());      // take the top away
        System.out.println("pop:  " + stack.pop());
        System.out.println(stack + ", size " + stack.size());
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 6

Declare the variable as Deque, create an ArrayDeque.

وەک Deque بناسێنە و ArrayDequeـێک دروست بکە.

Animation beside the code. An empty stack; push puts a red plate on the top; push again: blue is the top; the green plate pushed last is on the top, println shows [green plate, blue plate, red plate]; peek only looks at the top and nothing is removed; pop takes the green plate away and gives it back; pop again takes the blue plate: last in, first out; one plate is left and size() is 1. — push, peek and pop work only at the toppush، peek و pop تەنیا لە سەرەوە کار دەکەنCêIT

println shows the top first. pop() returns the plate it removes, so you can use it; peek() only looks.

println سەرەوە یەکەم پیشان دەدات. pop() ئەو قاپە دەگەڕێنێتەوە کە لای دەبات، بۆیە دەتوانیت بەکاری بهێنیت؛ peek() تەنیا سەیر دەکات.

The old Stack class, or ArrayDeque?کلاسی کۆنی Stack، یان ArrayDeque؟

Java also has a class named Stack, from Java 1.0. Its own documentation says to prefer a Deque such as ArrayDeque. This run shows why:

Java تریشی هەیە بە ناوی Stack، لە ⁦Java 1.0⁩ـەوە. بەڵگەنامەی خۆی دەڵێت Dequeـێکی وەک ArrayDeque باشترە. ئەم کارپێکردنە پیشان دەدات بۆچی:

OldStack.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class OldStack {
    public static void main(String[] args) {
        Stack<String> old = new Stack<>();
        Deque<String> modern = new ArrayDeque<>();
        String[] plates = {"red", "blue", "green"};
        for (String p : plates) {
            old.push(p);
            modern.push(p);
        }
        System.out.println("Stack:      " + old + "  top: " + old.peek());
        System.out.println("ArrayDeque: " + modern + "  top: " + modern.peek());
        old.add(0, "yellow");                    // a Vector method: under the bottom plate
        System.out.println("Stack after add(0, \"yellow\"): " + old);
        System.out.println("old.get(1): " + old.get(1));
    }
}

Stack is a kind of Vector (an old growable array), so it also has add(0, x) and get(i). They break the stack rule: yellow went in under the bottom plate.
It prints from the bottom up, while ArrayDeque prints from the top down.
Every Stack method is synchronized (locked for use by several threads at once), which costs time even in a simple program. The ArrayDeque documentation says it is "likely to be faster than Stack".

Stack جۆرێکە لە Vector ( کۆن کە دەتوانێت گەورە ببێت)، بۆیە add(0, x) و get(i)ـیشی هەیە. ئەمانە یاسای دەشکێنن: زەرد چووە ژێر قاپی خوارەوە.
لە خوارەوە بۆ سەرەوە چاپ دەکات، بەڵام ArrayDeque لە سەرەوە بۆ خوارەوە.
هەموو Stack synchronizedـە (بۆ بەکارهێنانی هاوکاتی چەند thread قفڵ دەکرێت)، کە تەنانەت لە سادەشدا کات دەبات. بەڵگەنامەی ArrayDeque دەڵێت «لەوانەیە لە Stack خێراتر بێت».

Use ArrayDeque for new code; Stack is legacyبۆ کۆدی نوێ ArrayDeque بەکار بهێنە؛ Stack کۆنەCêIT

Popping an empty stackpop لەسەر ستاکێکی بەتاڵ

In most programs, popping an empty stack is a bug: in a bracket checker it means a closing bracket without a partner. The old Stack throws an EmptyStackException:

لە زۆربەی ، pop لەسەر بەتاڵ : لە پشکنەرێکی کەوانەدا واتای کەوانەیەکی داخستنە بێ هاوتا. Stackـی کۆن EmptyStackException فڕێ دەدات:

EmptyStack.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.Stack;

public class EmptyStack {
    public static void main(String[] args) {
        Stack<String> plates = new Stack<>();
        System.out.println("empty: " + plates.empty());
        plates.pop();
    }
}

ArrayDeque.pop() throws a NoSuchElementException, while its peek() returns null. Check isEmpty() before you pop:

ArrayDeque.pop() NoSuchElementException فڕێ دەدات، بەڵام peek()ـەکەی null دەگەڕێنێتەوە. پێش pop isEmpty() بپشکنە:

EmptyDeque.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Deque;

public class EmptyDeque {
    public static void main(String[] args) {
        Deque<String> plates = new ArrayDeque<>();
        System.out.println("isEmpty: " + plates.isEmpty());
        System.out.println("peek: " + plates.peek());
        plates.pop();
    }
}

Example: an undo historyنموونە: مێژووی پاشگەزبوونەوە

Every editor has Ctrl+Z. Before each change, the program pushes the old text; to undo, it pops it back. The newest old version is on the top, exactly what undo needs:

هەموو ⁦Ctrl+Z⁩ـی هەیە. پێش هەر گۆڕانکارییەک دەقە کۆنەکە push دەکات؛ بۆ pop دەکات و دەیگەڕێنێتەوە. نوێترین وەشانی کۆن لە سەرەوەیە، ڕێک ئەوەی پێویستیەتی:

Editor.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Deque;

public class Editor {
    public static void main(String[] args) {
        Deque<String> undo = new ArrayDeque<>();
        String text = "Hello";
        String[] edits = {"Hello Hana", "Hello Hana!", "Hello Lana!"};
        for (String next : edits) {
            undo.push(text);                     // keep the version before the edit
            text = next;
            System.out.println("edit: " + text);
        }
        System.out.println("saved versions: " + undo);
        text = undo.pop();                       // Ctrl+Z: the newest old version
        System.out.println("undo: " + text);
        text = undo.pop();
        System.out.println("undo: " + text);
        System.out.println("one more undo would give: " + undo.peek());
    }
}

Undo pops the newest old version نوێترین وەشانی کۆن pop دەکاتCêIT

Checking brackets is the other classic job of a stack; you write it in the exercises (Bracket matching).

پشکنینی کەوانەکان کاری کلاسیکی تری ؛ لە ڕاهێنانەکاندا دەینووسیت (یەکگرتنەوەی کەوانەکان).

A queue: first in, first outکیوو: یەکەم هاتوو، یەکەم دەرچوو

A works like the line at a bakery in the morning: new people join at the back, and the person at the front is served first. That is FIFO, first in, first out. In Java, offer adds at the back, poll removes and returns the front, and peek looks at the front. The idea and its uses are in Queues. Again ArrayDeque is the class to use, through the Queue interface:

وەک ڕیزی نانەوایی لە بەیانیدا کار دەکات: خەڵکی نوێ لە دواوە دەچنە ڕیزەوە و ئەو کەسەی لە پێشەوەیە یەکەم جار نانی پێ دەدرێت. ئەمە FIFOـیە، یەکەم هاتوو، یەکەم دەرچوو. لە Javaـدا offer لە دواوە زیاد دەکات، poll ئەوەی پێشەوە لادەبات و دەیگەڕێنێتەوە و peek سەیری پێشەوە دەکات. بیرۆکەکە و بەکارهێنانەکانی لە کیووەکانـدان. دیسان ArrayDeque ئەو کە بەکاری دەهێنیت، لە ڕێگەی Queueـەوە:

Bakery.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Queue;

public class Bakery {
    public static void main(String[] args) {
        Queue<String> line = new ArrayDeque<>();
        line.offer("Aram");
        line.offer("Shilan");
        line.offer("Karwan");
        System.out.println("Line: " + line + ", front: " + line.peek());
        System.out.println("Served: " + line.poll());
        line.offer("Dilan");                         // joins at the back
        System.out.println("Served: " + line.poll());
        System.out.println("Line: " + line + ", size " + line.size());
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 12

Dilan arrives later and joins at the back.

Dilan دواتر دێت و لە دواوە دەچێتە ڕیزەوە.

Animation of a bakery queue, front on the left, back on the right. line.offer("Aram"), then Shilan and Karwan join at the back: [Aram, Shilan, Karwan]. line.peek(): Aram is at the front. line.poll(): Aram is served and leaves: [Shilan, Karwan]. line.offer("Dilan"): Dilan joins at the back. line.poll(): Shilan is served: [Karwan, Dilan]. First in, first out. — offer joins at the back; poll serves the frontoffer لە دواوە دەچێتە ڕیز؛ poll خزمەتی پێشەوە دەکاتCêIT

Two families: offer/poll/peek and add/remove/elementدوو خێزان: ⁦offer/poll/peek⁩ و ⁦add/remove/element⁩

Queue has two methods for each job. One family throws an exception when it cannot do the job; the other returns a special value, false or null. On an empty queue poll() and peek() give null, while element() throws:

Queue بۆ هەر کارێک دوو هەیە. خێزانێکیان کاتێک ناتوانێت کارەکە بکات فڕێ دەدات؛ ئەوی تر تایبەت دەگەڕێنێتەوە، false یان null. لەسەر بەتاڵ poll() و peek() null دەدەن، بەڵام element() فڕێ دەدات:

EmptyQueue.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Queue;

public class EmptyQueue {
    public static void main(String[] args) {
        Queue<String> line = new ArrayDeque<>();
        System.out.println("poll: " + line.poll());
        System.out.println("peek: " + line.peek());
        System.out.println("element: " + line.element());
    }
}

The same three jobs, two ways to failهەمان سێ کار، دوو ڕێگەی سەرنەکەوتنCêIT

Because null means "empty", ArrayDeque refuses null elements: offer(null) throws a NullPointerException. LinkedList accepts them, but the Queue documentation advises against it. Use offer/poll/peek when an empty (or full) queue is normal, and add/remove/element when it would be a bug.

چونکە null واتە «بەتاڵ»، ArrayDeque null وەرناگرێت: offer(null) NullPointerException فڕێ دەدات. LinkedList وەریان دەگرێت، بەڵام بەڵگەنامەی Queue ئامۆژگاری دەکات کە وا نەکەیت. کاتێک بەتاڵ (یان پڕ) ئاسایی بێت offer/poll/peek بەکار بهێنە و کاتێک بێت add/remove/element.

Example: a print queueنموونە: کیووی چاپ

Several people send documents to one . The jobs wait in a queue and are printed in the order they came. poll() returns null when nothing is waiting, and the program uses that to print a message (the same idea in Python: A print queue):

چەند کەسێک بەڵگەنامە دەنێرن بۆ یەک . کارەکان لە چاوەڕێ دەکەن و بە ڕیزی هاتنیان چاپ دەکرێن. کاتێک هیچ کارێک چاوەڕێ ناکات poll() null دەگەڕێنێتەوە و ئەوە بەکار دەهێنێت بۆ چاپکردنی پەیامێک (هەمان بیرۆکە لە Pythonـدا: کیووی چاپ):

PrintQueue.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Queue;

public class PrintQueue {
    public static void main(String[] args) {
        Queue<String> jobs = new ArrayDeque<>();
        String[] events = {"report.pdf", "photo.jpg", "PRINT", "letter.docx", "PRINT", "PRINT", "PRINT"};
        for (String e : events) {
            if (e.equals("PRINT")) {
                String job = jobs.poll();                // null when nothing is waiting
                if (job == null) {
                    System.out.println("Printer: nothing to print");
                } else {
                    System.out.println("Printer: printing " + job);
                }
            } else {
                jobs.offer(e);
                System.out.println("New job " + e + " -> queue " + jobs);
            }
        }
    }
}

The printer always takes the job at the front هەمیشە کاری پێشەوە وەردەگرێتCêIT

A deque: both endsکیووی دووسەرە: هەردوو سەر

ArrayDeque implements Deque, a double-ended queue (a ): it can add, remove and look at both ends. push and pop work at the front (a stack); offer adds at the back and poll takes from the front (a queue); and offerFirst, offerLast, pollFirst, pollLast, peekFirst and peekLast name the end themselves:

ArrayDeque Deque دەباتە سەر، دوو سەر (): دەتوانێت لە هەردوو سەرەوە زیاد بکات، لاببات و سەیر بکات. push و pop لە پێشەوە کار دەکەن ()؛ offer لە دواوە زیاد دەکات و poll لە پێشەوە وەردەگرێت ()؛ offerFirst، offerLast، pollFirst، pollLast، peekFirst و peekLast خۆیان ناوی سەرەکە دەبەن:

BothEnds.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Deque;

public class BothEnds {
    public static void main(String[] args) {
        Deque<String> d = new ArrayDeque<>();
        d.offerLast("B");                            // at the back
        d.offerLast("C");
        d.offerFirst("A");                           // at the front
        System.out.println(d);
        System.out.println("pollFirst: " + d.pollFirst() + ", pollLast: " + d.pollLast());
        System.out.println(d);
    }
}

A stack uses one end; a queue uses both یەک سەر بەکار دەهێنێت؛ هەردووکیانCêIT

Inside, an ArrayDeque is an array used as a ring: the front and the back move around it, so nothing is shifted at either end. That is why it beats LinkedList as a queue, as its documentation says.

لە ناوەوە، ArrayDeque کە وەک بازنەیەک بەکار دێت: پێشەوە و دواوە بە دەوریدا دەسووڕێنەوە، بۆیە لە هیچ سەرێکەوە هیچ شتێک ناجووڵێت. هەر بۆیە وەک لە LinkedList باشترە، وەک بەڵگەنامەکەی دەڵێت.

PriorityQueue: the most urgent firstPriorityQueue: بەپەلەترین یەکەم

A PriorityQueue is not first in, first out. poll() always takes the smallest element, or the largest when you create it with Comparator.reverseOrder(). Think of a hospital's emergency room, where 1 means "most urgent":

PriorityQueue «یەکەم هاتوو، یەکەم دەرچوو» نییە. poll() هەمیشە بچووکترین دەبات، یان گەورەترین کاتێک بە Comparator.reverseOrder() دروستی دەکەیت. بەشی فریاکەوتنی نەخۆشخانەیەک بهێنە بەرچاوت، کە تێیدا 1 واتە «بەپەلەترین»:

Emergency.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.Comparator;
import java.util.PriorityQueue;

public class Emergency {
    public static void main(String[] args) {
        PriorityQueue<Integer> waiting = new PriorityQueue<>();   // 1 = most urgent
        waiting.offer(3);
        waiting.offer(1);
        waiting.offer(4);
        waiting.offer(2);
        System.out.println("printed: " + waiting + ", peek: " + waiting.peek());
        System.out.print("poll order:");
        while (!waiting.isEmpty()) {
            System.out.print(" " + waiting.poll());              // always the smallest
        }
        System.out.println();

        PriorityQueue<Integer> biggest = new PriorityQueue<>(Comparator.reverseOrder());
        biggest.offer(3);
        biggest.offer(1);
        biggest.offer(4);
        biggest.offer(2);
        System.out.println("largest first: " + biggest.poll() + " " + biggest.poll());
    }
}

A heap keeps the smallest on top بچووکترین لە سەرەوە دەهێڵێتەوەCêIT

Inside is a : a tree kept in an array, with the smallest element at the top. So printing shows the heap's array, [1, 2, 4, 3], not a sorted list; only poll() and peek() promise the smallest. offer and poll take about $\log_2 n$ steps each (Heaps and priority queues).

لە ناوەوە : دارێک کە لە هەڵگیراوە و بچووکترین لە سەرەوەیە. بۆیە چاپکردن پیشان دەدات، [1, 2, 4, 3]، نەک ڕیزکراو؛ تەنیا poll() و peek() بەڵێنی بچووکترین دەدەن. هەر offer و pollـێک نزیکەی $\log_2 n$ هەنگاو دەبات (هیپەکان و کیووە پێشینەییەکان).

Which one should I use?کامیان بەکار بهێنم؟

Choose by the question your program asks most often. Most programs need an ArrayList or a HashMap. When the order of arrival matters, use an ArrayDeque; when the most urgent item matters, a PriorityQueue. Avoid Stack and Vector in new code.

بەپێی ئەو پرسیارەی زۆرتر دەیکات هەڵبژێرە. زۆربەی ArrayList یان HashMapـیان پێویستە. کاتێک ڕیزی هاتن گرنگ بێت ArrayDeque بەکار بهێنە؛ کاتێک بەپەلەترین شت گرنگ بێت PriorityQueue. لە کۆدی نوێدا خۆت لە Stack و Vector لابدە.

Start from what the program asks most oftenلەو پرسیارەوە دەست پێ بکە کە زۆرتر دەیکاتCêIT

Common mistakesهەڵە باوەکان

Mistakes with lists, iterators, stacks and queuesهەڵەکان لەگەڵ ، ، و
You wroteنووسیت	What happensچی ڕوو دەدات	Fixچارەسەر
`getFirst()` or `removeFirst()` on an empty `LinkedListgetFirst()` یان `removeFirst()` لەسەر `LinkedList`ـێکی بەتاڵ	`NoSuchElementException`	Check `isEmpty()` first, or use `peekFirst` / `pollFirst`.سەرەتا `isEmpty()` بپشکنە، یان `peekFirst` / `pollFirst` بەکار بهێنە.
`list.remove(x)` inside a for-each loop over `listlist.remove(x)` لە ناو بەسەر `list`ـدا	`ConcurrentModificationException`	`it.remove()` or `removeIf`; without an exception, an element may be skipped.`it.remove()` یان `removeIf`؛ بەبێ لەوانەیە بازی بەسەر بدرێت.
`it.remove()` twice after one `next()`دوو جار `it.remove()` دوای یەک `next()`	`IllegalStateException`	One `remove()` for each `next()`.بۆ هەر `next()`ـێک یەک `remove()`.
`it.next()` twice in one pass of the loopدوو جار `it.next()` لە یەک سووڕدا	mixes two elements, then NoSuchElementExceptionدوو تێکەڵ دەکات، پاشان NoSuchElementException	Call `next()` once and keep the result in a variable.`next()` یەک جار بانگ بکە و ئەنجامەکەی لە هەڵبگرە.
`Stack<String> s = new Stack<>();` in new code`Stack<String> s = new Stack<>();` لە کۆدی نوێدا	works, but allows `add(0, x)` and `get(i)`, and is slowerکار دەکات، بەڵام ڕێگە بە `add(0, x)` و `get(i)` دەدات و خاوترە	`Deque<String> s = new ArrayDeque<>();Deque<String> s = new ArrayDeque<>();`
`pop()` on an empty stack`pop()` لەسەر بەتاڵ	EmptyStackException (`Stack`) or NoSuchElementException (`ArrayDeque`)EmptyStackException (`Stack`) یان NoSuchElementException (`ArrayDeque`)	Check `isEmpty()` first.سەرەتا `isEmpty()` بپشکنە.
`queue.offer(null)` on an `ArrayDequequeue.offer(null)` لەسەر `ArrayDeque`	`NullPointerException`	Never put `null` in a queue: `poll()` uses it to say "empty".هەرگیز `null` مەخە ناو : `poll()` بەکاری دەهێنێت بۆ وتنی «بەتاڵ».
`System.out.println(priorityQueue)` to see the order`System.out.println(priorityQueue)` بۆ بینینی ڕیزەکە	the heap's array order, not sortedڕیزبەندیی ناوەوەی ، نەک ڕیزکراو	`poll()` in a loop.`poll()` لە ناو .
`for (int i = 0; i < n; i++) list.get(i)` on a big `LinkedListfor (int i = 0; i < n; i++) list.get(i)` لەسەر `LinkedList`ـێکی گەورە	very slow: each `get(i)` walksزۆر خاو: هەر `get(i)`ـێک دەڕوات	A for-each loop, or an `ArrayList`.، یان `ArrayList`.
`list.addFirst(x)` on a `List` variable (Java 17)`list.addFirst(x)` لەسەر `List` ⁦(Java 17)⁩	`error: cannot find symbol`	Declare it as `LinkedList` or `Deque`.وەک `LinkedList` یان `Deque` بیناسێنە.

Calling next() twice in one pass is easy to miss. The loop asked hasNext() once but took two names: "Aram is 6 letters long" mixes Aram with Shilan, and the next pass crashes:

بانگکردنی next() دوو جار لە یەک سووڕدا بە ئاسانی لە چاو ون دەبێت. یەک جار hasNext()ـی پرسی، بەڵام دوو ناوی برد: «⁦Aram is 6 letters long⁩» Aram و Shilan تێکەڵ دەکات و سووڕی دواتر تێک دەشکێت:

NextTwice.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class NextTwice {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Aram", "Shilan", "Karwan"));
        Iterator<String> it = names.iterator();
        while (it.hasNext()) {
            System.out.println(it.next() + " is " + it.next().length() + " letters long");
        }
    }
}

And remove() twice after one next(): the iterator has already removed that element, so the second call throws an IllegalStateException:

هەروەها دوو جار remove() دوای یەک next(): پێشتر ئەو لابردووە، بۆیە بانگکردنی دووەم IllegalStateException فڕێ دەدات:

RemoveTwice.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class RemoveTwice {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Aram", "Shilan", "Karwan"));
        Iterator<String> it = names.iterator();
        it.next();
        it.remove();                                 // removes Aram
        it.remove();                                 // nothing new was given out
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 10-11

The second remove() has no new element from next() to remove.

remove()ـی دووەم هیچ نوێی next()ـی نییە بۆ لابردن.

Practiceڕاهێنان

ExerciseڕاهێنانBalanced bracketsکەوانەی هاوسەنگ

Write static boolean balanced(String text). It returns true when every (, [ and { is closed by the right partner, in the right order. Test it with ((2+3)*(4/2))+2, (5+2]*3, [(1+2)*{3-1}], (() and ())(.

static boolean balanced(String text) بنووسە. کاتێک هەموو (، [ و {ـێک بە هاوتای دروست و بە ڕیزی دروست دابخرێت true دەگەڕێنێتەوە. بە ((2+3)*(4/2))+2، (5+2]*3، [(1+2)*{3-1}]، (() و ())( تاقی بکەرەوە.

Hintئاماژە

Push every opening bracket; at a closing bracket, pop and compare.

هەموو کەوانەیەکی کردنەوە push بکە؛ لە کەوانەی داخستندا pop بکە و بەراورد بکە.

Show answerوەڵامەکە پیشان بدە

Brackets.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Deque;

public class Brackets {
    static boolean balanced(String text) {
        Deque<Character> open = new ArrayDeque<>();
        for (char c : text.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                open.push(c);                        // remember every opening bracket
            } else if (c == ')' || c == ']' || c == '}') {
                if (open.isEmpty()) {
                    return false;                    // a closing bracket with no partner
                }
                char top = open.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                    return false;                    // the wrong kind of bracket
                }
            }
        }
        return open.isEmpty();                       // nothing may stay open
    }

    public static void main(String[] args) {
        String[] tests = {"((2+3)*(4/2))+2", "(5+2]*3", "[(1+2)*{3-1}]", "(()", "())("};
        for (String t : tests) {
            System.out.println(t + " -> " + balanced(t));
        }
    }
}

Every opening bracket is pushed. A closing bracket pops the newest open one and compares: the wrong kind, or an empty stack, means "not balanced". At the end nothing may stay open. The step-by-step idea is in Bracket matching.

هەموو کەوانەیەکی کردنەوە push دەکرێت. کەوانەیەکی داخستن نوێترین کەوانەی کراوە pop دەکات و بەراوردیان دەکات: جۆری هەڵە، یان بەتاڵ، واتە «هاوسەنگ نییە». لە کۆتاییدا نابێت هیچ کەوانەیەک کراوە بمێنێتەوە. بیرۆکەکە هەنگاو بە هەنگاو لە یەکگرتنەوەی کەوانەکانـدایە.

ExerciseڕاهێنانWords in reverse orderوشەکان بە ڕیزی پێچەوانە

Print the words of "Java keeps every value in order" in reverse order, using a stack.

وشەکانی "Java keeps every value in order" بە ڕیزی پێچەوانە چاپ بکە، بە بەکارهێنانی .

Show answerوەڵامەکە پیشان بدە

ReverseWords.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Deque;

public class ReverseWords {
    public static void main(String[] args) {
        String sentence = "Java keeps every value in order";
        Deque<String> stack = new ArrayDeque<>();
        for (String word : sentence.split(" ")) {
            stack.push(word);
        }
        StringBuilder out = new StringBuilder();
        while (!stack.isEmpty()) {
            out.append(stack.pop());
            if (!stack.isEmpty()) {
                out.append(" ");
            }
        }
        System.out.println(out);
    }
}

split(" ") gives the words; pushing them and popping them back reverses their order.

split(" ") وشەکان دەدات؛ push کردن و pop کردنەوەیان ڕیزەکەیان پێچەوانە دەکاتەوە.

ExerciseڕاهێنانRemove the odd numbersژمارە تاکەکان لاببە

Remove every odd number from the list [4, 7, 10, 13, 15, 22] with an Iterator.

هەموو ژمارەیەکی تاک لە [4, 7, 10, 13, 15, 22] بە Iteratorـێک لاببە.

Show answerوەڵامەکە پیشان بدە

RemoveOdd.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class RemoveOdd {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(List.of(4, 7, 10, 13, 15, 22));
        Iterator<Integer> it = numbers.iterator();
        while (it.hasNext()) {
            if (it.next() % 2 != 0) {
                it.remove();
            }
        }
        System.out.println(numbers);
    }
}

it.next() % 2 != 0 tests the number next() just gave, and it.remove() removes exactly that one.

it.next() % 2 != 0 ئەو ژمارەیە تاقی دەکاتەوە کە next() تازە دای و it.remove() ڕێک هەمان ژمارە لادەبات.

ExerciseڕاهێنانPredict the queueپێشبینیی کیووەکە بکە

Before you run it: what does this program print?

پێش ئەوەی کاری پێ بکەیت: ئەم چی چاپ دەکات؟

Tickets.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Queue;

public class Tickets {
    public static void main(String[] args) {
        Queue<String> q = new ArrayDeque<>();
        q.offer("Rebin");
        q.offer("Hana");
        q.offer("Soran");
        q.poll();
        q.offer("Lana");
        q.offer(q.poll());
        System.out.println(q + " " + q.peek());
    }
}

Show answerوەڵامەکە پیشان بدە

Outputدەرئەنجام

$ java Tickets
[Soran, Lana, Hana] Soran

Rebin, Hana and Soran join; poll() serves Rebin. Lana joins: [Hana, Soran, Lana]. q.offer(q.poll()) takes Hana from the front and puts her at the back: [Soran, Lana, Hana], so peek() is Soran.

Rebin، Hana و Soran دەچنە ڕیز؛ poll() Rebin دەبات. Lana دەچێتە ڕیز: [Hana, Soran, Lana]. q.offer(q.poll()) Hana لە پێشەوە دەبات و دەیخاتە دواوە: [Soran, Lana, Hana]، بۆیە peek() Soranـە.

ExerciseڕاهێنانPalindromes with a dequeپالیندرۆم بە کیوویەکی دووسەرە

A palindrome reads the same from both ends (level, noon). Put the letters of a word into a deque and compare the two ends until one letter or none is left. Test level, Kayak, Erbil and noon.

پالیندرۆم لە هەردوو سەرەوە یەک شت دەخوێنرێتەوە (level، noon). پیتەکانی وشەیەک بخە ناو و دوو سەرەکە بەراورد بکە تا یەک پیت یان هیچ پیتێک دەمێنێتەوە. level، Kayak، Erbil و noon تاقی بکەرەوە.

Hintئاماژە

while (d.size() > 1), then compare d.pollFirst() with d.pollLast().

while (d.size() > 1)، پاشان d.pollFirst() لەگەڵ d.pollLast() بەراورد بکە.

Show answerوەڵامەکە پیشان بدە

Palindrome.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayDeque;
import java.util.Deque;

public class Palindrome {
    static boolean isPalindrome(String word) {
        Deque<Character> d = new ArrayDeque<>();
        for (char c : word.toLowerCase().toCharArray()) {
            d.offerLast(c);
        }
        while (d.size() > 1) {
            if (!d.pollFirst().equals(d.pollLast())) {   // compare the two ends
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        for (String w : new String[] {"level", "Kayak", "Erbil", "noon"}) {
            System.out.println(w + " -> " + isPalindrome(w));
        }
    }
}

pollFirst() and pollLast() take one letter from each end; one mismatch is enough to answer false. toLowerCase() makes Kayak work. The Python version is in Palindromes.

pollFirst() و pollLast() لە هەر سەرێک پیتێک دەبەن؛ یەک ناکۆکی بەسە بۆ وەڵامی false. toLowerCase() وا دەکات Kayak کار بکات. وەشانی Python لە پالیندرۆمـدایە.

Summaryکورتە

LinkedList is a chain of nodes with references to the next and the previous node. addFirst, addLast, getFirst, getLast, removeFirst and removeLast work at the ends; getFirst on an empty list throws NoSuchElementException, peekFirst gives null.
Measured: LinkedList wins only at the front; get(i) and the middle are much slower than on ArrayList. Program to the List interface.
An Iterator is a cursor: hasNext(), next(), and remove() for safe removal while walking. ListIterator also goes backwards and has set and add.
Stack (LIFO): Deque<…> s = new ArrayDeque<>() with push, pop, peek. The old Stack class is a Vector and is not recommended.
Queue (FIFO): Queue<…> q = new ArrayDeque<>() with offer, poll, peek (they return false/null); add, remove, element throw instead.
A Deque works at both ends; a PriorityQueue always gives the smallest (a heap inside).

LinkedList زنجیرەیەک بە بۆ دواتر و پێشتر. addFirst، addLast، getFirst، getLast، removeFirst و removeLast لە سەرەکان کار دەکەن؛ getFirst لەسەر بەتاڵ NoSuchElementException فڕێ دەدات، peekFirst null دەدات.
بە پێوانە: LinkedList تەنیا لە سەرەتادا دەباتەوە؛ get(i) و ناوەڕاست لە ArrayList زۆر خاوترن. بە List بنووسە.
: hasNext()، next() و remove() بۆ لابردنی بێ مەترسی لە کاتی ڕۆیشتندا. ListIterator بە پاشەوەش دەڕوات و set و addـی هەیە.
⁦(LIFO)⁩: Deque<…> s = new ArrayDeque<>() بە push، pop، peek. کلاسی کۆنی Stack Vectorـە و پێشنیار ناکرێت.
⁦(FIFO)⁩: Queue<…> q = new ArrayDeque<>() بە offer، poll، peek (false/null دەگەڕێننەوە)؛ add، remove، element لە جیاتی ئەوە فڕێ دەدەن.
Deque لە هەردوو سەرەوە کار دەکات؛ PriorityQueue هەمیشە بچووکترین دەدات ( لە ناوەوە).

Review questionsپرسیارەکانی پێداچوونەوە

What is the difference between poll() and remove() on an empty queue?جیاوازیی poll() و remove() لەسەر کیوویەکی بەتاڵ چییە؟

poll() returns null; remove() throws NoSuchElementException.

poll() null دەگەڕێنێتەوە؛ remove() NoSuchElementException فڕێ دەدات.

Why does a for-each loop crash when you remove through the list?بۆچی خولی foreach تێک دەشکێت کاتێک بە لیستەکە لادەبەیت؟

Its hidden iterator sees that the list changed behind its back and throws ConcurrentModificationException. Remove with it.remove() or removeIf.

دەبینێت کە لە پشتییەوە گۆڕاوە و ConcurrentModificationException فڕێ دەدات. بە it.remove() یان removeIf لاببە.

Which class should a new program use for a stack?بەرنامەیەکی نوێ بۆ ستاک کام کلاس بەکار بهێنێت؟

ArrayDeque, through the Deque interface.

ArrayDeque، لە ڕێگەی Dequeـەوە.

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Sorting, Searching and Lambda Expressionsڕیزکردن، گەڕان و کردارە بێناوەکان

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.