PythonPython · Chapterبەش 11 · Lectureوانە 11.2

Queues and Deques: First In, First Outکیووەکان و کیووە دووسەرەکان: یەکەم هاتوو، یەکەم دەرچوو

The queue and its operations, queues in computing, why list.pop(0) is slow and collections.deque is the right tool, bounded queues with is_full() or maxlen, the double-ended deque, and checking palindromes.

و کارەکانی، لە کۆمپیوتەردا، بۆچی list.pop(0) هێواشە و collections.deque ئامرازی دروستە، سنووردار بە is_full() یان maxlen، و پشکنینی پالیندرۆم.

19 min read19 خولەک خوێندنەوە · 18 stepsهەنگاو

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

Explain FIFO and the front and rear of a queue, with everyday and computing examples.
Use enqueue, dequeue, peek, is_empty, is_full and size, and recognise overflow and underflow.
Explain why list.pop(0) is slow and build queues with collections.deque.
Choose between an is_full() check and maxlen for a bounded queue.
Use a deque at both ends, as a stack or as a queue, and to check palindromes.

FIFO و پێشەوە و دواوەی ڕوون بکەیتەوە، بە نموونەی ڕۆژانە و کۆمپیوتەری.
enqueue، dequeue، peek، ⁦is_empty⁩، ⁦is_full⁩ و size بەکار بهێنیت و و بناسیتەوە.
ڕوون بکەیتەوە بۆچی list.pop(0) هێواشە و بە collections.deque دروست بکەیت.
لە نێوان پشکنینی is_full() و maxlen بۆ سنووردار هەڵبژێریت.
لە هەردوو سەرەوە بەکار بهێنیت، وەک یان و بۆ پشکنینی پالیندرۆم.

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

A queue is a linear data structure with two ends. New items join at one end, the rear (also called the tail), and items leave from the other end, the front (or head). So the item that has waited longest leaves first: FIFO, First In, First Out, or first come, first served.

هێڵییە کە دوو سەری هەیە. نوێ لە سەرێکەوە دێنە ناوی، دواوە (پێی دەوترێت کلک) و لە سەرەکەی ترەوە دەڕۆن، پێشەوە (یان سەر). کەواتە ئەو زۆرترین چاوەڕێی کردووە یەکەم جار دەڕوات: FIFO، ⁦First In, First Out⁩، واتە یەکەم هاتوو، یەکەم دەرچوو.

Definitionپێناسە

A data structure in which the first item added is the first one taken out (FIFO), like people waiting in line at a bakery. Breadth-first search keeps its frontier in a queue.

کە تێیدا یەکەم دانە کە دەخرێتە ناوی یەکەم دانەیە کە دەردەهێنرێت ⁦(FIFO)⁩، وەک ڕیزی خەڵک لەبەردەم نانەواخانەیەک. لە هەڵدەگرێت.

A bakery line is a queue: join at the rear, get served at the front.ڕیزی نانەواخانە : لە دواوە دێیتە ناوی و لە پێشەوە خزمەتت دەکرێت.CêIT

Everyday queues are everywhere: the line at a bakery for hot bread, taxis waiting their turn at a garage, cars at a one-lane road or at a petrol station, callers on hold at a phone company's support line ("your call is important to us"), and a waiting list for bus tickets, where the first waiting ticket is confirmed first when a seat becomes free.

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

The bakery lineڕیزی نانەواخانە

In the morning the baker serves whoever is at the front, and a newcomer goes to the end of the line. Nobody is served before someone who came earlier, which feels fair: first come, first served.

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

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

Real people sometimes leave the line or let an old man go first. A plain queue in a program allows neither: only the rear takes items and only the front gives them.

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

Queues in computingکیووەکان لە کۆمپیوتەردا

Whenever work arrives faster than it can be done, a queue keeps it in order until its turn comes:

هەر کاتێک کار خێراتر لەوەی بکرێت دەگات، بە ڕیزبەندی هەڵی دەگرێت تا نۆرەی دێت:

Printing: when several people send documents to one shared , the operating system puts the print jobs in a queue and sends them to the printer one by one.
The processor's jobs: a processor runs one task at a time, so the operating system lines tasks up; the simplest order is first come, first served ().
A web server: on exam-results day a results website may get thousands of requests, more than it can answer at once; waiting requests are queued (The request cycle).
The keyboard: keys you press while a program is busy wait in a small queue (a ) and appear in the right order.
Breadth-first search in AI explores places in the order it found them, with a queue: you will meet it in Breadth-first search.

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

Tipئامۆژگاری

Think about it. On results day the head of a school sends an urgent request to the same busy server. Should it wait at the back of the queue? A fairer way gives each request a priority and serves the most urgent first: a , taught with heaps in Why a priority queue?

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

Quick checkپشکنینی خێراWhich of these is a stack, not a queue?کامیان ، نەک ؟The Back button of a web browserدوگمەی Backـی تۆڕگەڕRequests waiting for a busy web serverداواکارییەکان کە چاوەڕێی ڕاژەکارێکی وێبی سەرقاڵ دەکەنPrint jobs waiting for a shared printerکارەکانی چاپ کە چاوەڕێی چاپەرێکی هاوبەش دەکەن

Queue operations: enqueue and dequeueکارەکانی کیوو: enqueue و dequeue

The two main operations are enqueue (add an item at the rear) and dequeue (remove the item at the front and give it back). The helpers are like a stack's:

دوو کارە سەرەکییەکە enqueueـن (زیادکردنی لە دواوە) و dequeue (لابردنی پێشەوە و گەڕاندنەوەی). یارمەتیدەرەکان وەک هی :

Operationکار	What it doesچی دەکات	Problemکێشە
`enqueue(x)`	adds `x` at the rear`x` لە دواوە زیاد دەکات	overflow if a fixed-size queue is full ئەگەر بە قەبارەی جێگیر پڕ بێت
`dequeue()`	removes and returns the front item پێشەوە لادەبات و دەیگەڕێنێتەوە	underflow if the queue is empty ئەگەر بەتاڵ بێت
`peek()`	returns the front item without removing it پێشەوە دەگەڕێنێتەوە بەبێ لابردنی	nothing to see if emptyئەگەر بەتاڵ بێت هیچ نییە
`is_empty()`	`True` when there is no item: check it before `dequeue()`کاتێک هیچ نییە `True`ـە: پێش `dequeue()` بیپشکنە	–
`is_full()`	`True` when a fixed-size queue has no room: check it before `enqueue()`کاتێک بە قەبارەی جێگیر جێی نییە `True`ـە: پێش `enqueue()` بیپشکنە	–
`size()`	the number of itemsژمارەی	–

Follow a queue of letters through seven operations. The front is on the left:

لە پیت لە ناو حەوت کاردا بەدوادا بچۆ. پێشەوە لای چەپە:

The letters leave in the order they came: T, E, A (checked with a small Python program)پیتەکان بەو ڕیزبەندییە دەڕۆن کە هاتن: T، E، A (بە بچووکی پشکنرا)
Operationکار	Queue after it (front … rear) دوای ئەو (پێشەوە … دواوە)	Returnedگەڕاوە
`enqueue(T)`	`T`
`enqueue(E)`	`T E`
`enqueue(A)`	`T E A`
`dequeue()`	`E A`	`T`
`enqueue(S)`	`E A S`
`dequeue()`	`A S`	`E`
`dequeue()`	`S`	`A`

A queue made from a listکیوویەک لە لیستێکەوە

The simplest queue in Python is a list: append() adds at the rear (the end) and pop(0) removes from the front (index 0). Here it is with small functions, as the textbook writes it:

سادەترین لە : append() لە دواوە (کۆتایی) زیاد دەکات و pop(0) لە پێشەوە ( ⁦0⁩) لادەبات. ئەمە بە چەند بچووکەوە، وەک کتێبەکە دەینووسێت:

A queue made from a listکیوویەک کە لە لیستێک دروستکراوەlist_queue.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def is_empty(queue):
    return len(queue) == 0

def enqueue(queue, item):
    queue.append(item)            # join at the rear (the end of the list)

def dequeue(queue):
    if is_empty(queue):
        print("Underflow: the queue is empty")
        return None
    return queue.pop(0)           # leave from the front (index 0)

def peek(queue):
    if is_empty(queue):
        return None
    return queue[0]

def size(queue):
    return len(queue)

line = []
enqueue(line, "Aram")
enqueue(line, "Shilan")
enqueue(line, "Karwan")
print(line, " front:", peek(line), " size:", size(line))
print("served:", dequeue(line))
print(line)

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

Lineدێڕی 5

append() joins at the rear.

append() لە دواوە زیاد دەکات.

Lineدێڕی 11

pop(0) leaves from the front, but see below.

pop(0) لە پێشەوە لادەبات، بەڵام خوارەوە ببینە.

A queue made from a listکیوویەک لە لیستێکەوە

The hidden cost of pop(0)تێچووی شاراوەی `pop(0)`

It works, but pop(0) has a hidden cost. A list keeps its elements in numbered places, so when the first one leaves, every other element must move one place forward to fill the gap:

کار دەکات، بەڵام pop(0) تێچوویەکی شاراوەی هەیە. لە شوێنی ژمارەداردا هەڵدەگرێت، بۆیە کاتێک یەکەمیان دەڕوات، هەموو تر دەبێت یەک شوێن بچنە پێشەوە بۆ پڕکردنەوەی بۆشاییەکە:

After pop(0) every index changesدوای ⁦pop(0)⁩ هەموو ئیندێکسێک دەگۆڕێتpop0_shift.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

queue = ["Aram", "Shilan", "Karwan", "Dilan", "Rezan"]
print("before:", [(i, name) for i, name in enumerate(queue)])
queue.pop(0)
print("after: ", [(i, name) for i, name in enumerate(queue)])

list.pop(0) moves every other element; deque.popleft() moves none.⁦list.pop(0)⁩ هەموو تر دەجووڵێنێت؛ ⁦deque.popleft()⁩ هیچیان ناجووڵێنێت.CêIT

With 5 people that is nothing. With a queue of 100,000 print jobs or requests it adds up: each pop(0) moves almost the whole list, so emptying the queue does about $n^2/2$ moves. We timed it on our computer (the exact seconds depend on the machine, the growth does not):

بە 5 کەس ئەمە هیچ نییە. بە لە ⁦100,000⁩ کاری چاپ یان کۆ دەبێتەوە: هەر pop(0)ـێک نزیکەی هەموو دەجووڵێنێت، بۆیە بەتاڵکردنەوەی نزیکەی $n^2/2$ جووڵە دەکات. لەسەر کاتمان پێوا (چرکە وردەکان بە پێی ئامێرەکە دەگۆڕێن، گەورەبوونەکە ناگۆڕێت):

pop(0) against popleft()⁦pop(0)⁩ بەرامبەر ⁦popleft()⁩timing.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

import time
from collections import deque

for n in [100_000, 200_000]:
    q = list(range(n))
    start = time.perf_counter()
    while q:
        q.pop(0)                  # list: every other item moves
    list_time = time.perf_counter() - start

    d = deque(range(n))
    start = time.perf_counter()
    while d:
        d.popleft()               # deque: nothing moves
    deque_time = time.perf_counter() - start
    print(f"{n:,} items: list pop(0) {list_time:.2f} s, deque popleft() {deque_time:.3f} s")

Correctionڕاستکردنەوە

The textbook builds its queue with list.pop(0) and does not mention the cost. Python's own tutorial says lists are not efficient as queues, because pops from the beginning are slow (all other elements have to be shifted by one), and recommends collections.deque, which was designed for fast appends and pops at both ends. Use a list for a small queue in a short program; use a deque for anything real.

کتێبەکە بە list.pop(0) دروست دەکات و باسی تێچووەکەی ناکات. فێرکاریی خودی دەڵێت وەک کارا نین، چونکە لابردن لە سەرەتاوە هێواشە (هەموو تر دەبێت یەک شوێن بگوازرێنەوە) و collections.deque پێشنیار دەکات کە بۆ زیادکردن و لابردنی خێرا لە هەردوو سەرەوە دروستکراوە. بۆ بچووک لە کورتدا بەکار بهێنە؛ بۆ هەر شتێکی ڕاستەقینە .

The right tool: collections.dequeئامرازی دروست: ⁦collections.deque⁩

Python's standard library has a ready-made structure for queues: deque in the collections module. Import it with from collections import deque (Four ways to import). Then append() adds at the rear, popleft() removes from the front, q[0] peeks at the front, q[-1] at the rear, and len(q) gives the size. Adding and removing at either end is fast, however long the queue is.

پێکهاتەیەکی ئامادەی بۆ هەیە: deque لە collectionsـدا. بە from collections import deque هاوردەی بکە (چوار ڕێگای import). پاشان append() لە دواوە زیاد دەکات، popleft() لە پێشەوە لادەبات، q[0] سەیری پێشەوە دەکات، q[-1] سەیری دواوە و len(q) قەبارەکە دەدات. زیادکردن و لابردن لە هەر دوو سەرەوە خێرایە، هەرچەند درێژ بێت.

A queue with dequeکیوویەک بە dequedeque_queue.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

line = deque()                    # an empty queue
line.append("Aram")               # enqueue at the rear
line.append("Shilan")
line.append("Karwan")
print(line)
print("front:", line[0], " rear:", line[-1], " size:", len(line))
print("served:", line.popleft())  # dequeue from the front
print("served:", line.popleft())
print(line)
line.popleft()
line.popleft()                    # one too many

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

Lineدێڕی 1

deque lives in the collections module of the standard library.

deque لە collectionsـی .

Lineدێڕی 4

append(): enqueue at the rear.

append(): enqueue لە دواوە.

Lineدێڕی 9

popleft(): dequeue from the front.

popleft(): dequeue لە پێشەوە.

Lineدێڕی 13

An empty deque raises IndexError, just like an empty list.

بەتاڵ IndexError دروست دەکات، هەر وەک بەتاڵ.

Definitionپێناسە

A that lets you add and remove items at both ends, the front and the rear (say "deck"). Used from one end it works as a ; used from opposite ends, as a queue. Python's collections.deque adds and removes at both ends quickly.

کە ڕێگە دەدات لە هەردوو سەرەوە، پێشەوە و دواوە، شت زیاد بکەیت و لای بەریت (بە ئینگلیزی وەک «دێک» دەخوێنرێتەوە). ئەگەر تەنها لە یەک سەرەوە بەکار بهێنرێت وەک کار دەکات؛ ئەگەر لە دوو سەری جیاوە، وەک . collections.dequeـی لە هەردوو سەرەوە بە خێرایی زیاد دەکات و لادەبات.

Stacks & Queues - DSA Course in Python Lecture 5Greg Hogg · Englishئینگلیزی · 88K viewsبینین · 1.8K likesلایک · Partبەشی 11:39–14:58 (ofلە 14:58)
A queue in Python with collections.deque: append() adds at the right, popleft() removes from the left, and [0] and [-1] peek.
لە بە `collections.deque`: `append()` لە لای ڕاستەوە زیاد دەکات، `popleft()` لە لای چەپەوە لادەبات و `[0]` و `[-1]` سەیری هەردوو سەر دەکەن.
Watch 11:39–14:58: implementing a queue with collections.deque.
لە ⁦11:39⁩ تا ⁦14:58⁩ سەیر بکە: دروستکردنی بە `collections.deque`.

The right tool: collections.dequeئامرازی دروست: ⁦collections.deque⁩

A print queue, step by stepکیووی چاپ، هەنگاو بە هەنگاو

The animation shows the queue of a shared printer: every new job joins at the rear, and the printer always takes the job at the front.

ئەنیمەیشنەکە هاوبەش پیشان دەدات: هەر کارێکی نوێ لە دواوە دێتە ناوی و هەمیشە ئەو کارە وەردەگرێت کە لە پێشەوەیە.

Animation in eight frames of a print queue for one shared printer. Aram sends report.pdf, then Shilan sends photo.jpg and Karwan marks.xlsx: each new job joins at the rear of the queue. The printer takes the job at the front, report.pdf, and prints it. Dilan sends letter.docx, which joins at the rear behind marks.xlsx. Then photo.jpg is printed. The last frame lists the printing order: report, photo, marks, letter, first come, first served. — A shared printer serves print jobs in the order they arrived. هاوبەش کارەکانی چاپ بەو ڕیزبەندییە خزمەت دەکات کە گەیشتوون.CêIT

The same queue as a program with a deque. Each job is a string:

هەمان وەک بە . هەر کارێک :

The shared printer's queueکیووی چاپەری هاوبەشprint_queue.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

jobs = deque()
jobs.append("Aram: report.pdf")
jobs.append("Shilan: photo.jpg")
jobs.append("Karwan: marks.xlsx")
print("waiting:", list(jobs))
print("printing", jobs.popleft())
jobs.append("Dilan: letter.docx")
print("waiting:", list(jobs))
while jobs:
    print("printing", jobs.popleft())
print("waiting:", list(jobs))

Quick checkپشکنینی خێراDilan's letter.docx joins the queue after report.pdf has been printed. When is it printed?letter.docxـی دیلان دوای چاپکردنی report.pdf دێتە ناو . کەی چاپ دەکرێت؟Last, after photo.jpg and marks.xlsxلە کۆتاییدا، دوای photo.jpg و marks.xlsxNext, because it is the newestیەکسەر، چونکە نوێترینەBefore marks.xlsxپێش marks.xlsx

The right tool: collections.dequeئامرازی دروست: ⁦collections.deque⁩

A queue with a limit: is_full() or maxlenکیوویەک بە سنوور: ⁦is_full()⁩ یان maxlen

A real counter has room for only so many people. To model a fixed-size queue, check is_full() before enqueue(). A newcomer who finds it full is turned away: that is overflow. The functions also print the queue, front first:

پیشخانێکی ڕاستەقینە تەنها جێی ژمارەیەکی دیاریکراو کەسی تێدا دەبێتەوە. بۆ بە قەبارەی جێگیر، پێش enqueue() is_full() بپشکنە. کەسێکی تازە کە دەبینێت پڕە ڕەت دەکرێتەوە: ئەوە . چاپیش دەکەن، پێشەوە یەکەم:

A queue with a capacity of threeکیوویەک بە توانای سێ کەسdeque_functions.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

CAPACITY = 3                      # a counter with room for 3 people

def is_empty(queue):
    return len(queue) == 0

def is_full(queue):
    return len(queue) == CAPACITY

def enqueue(queue, item):
    if is_full(queue):
        print("Overflow: the queue is full,", item, "must wait outside")
    else:
        queue.append(item)

def dequeue(queue):
    if is_empty(queue):
        print("Underflow: the queue is empty")
        return None
    return queue.popleft()

def peek(queue):
    return None if is_empty(queue) else queue[0]

def show(queue):
    print("   front ->", ", ".join(queue) if queue else "(empty)", "<- rear")

counter = deque()
for name in ["Aram", "Shilan", "Karwan", "Dilan"]:
    enqueue(counter, name)
show(counter)
print("next:", peek(counter))
print("served:", dequeue(counter))
enqueue(counter, "Dilan")
show(counter)

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

Lineدێڕی 3

The capacity makes overflow possible.

تواناکە دەکاتە شتێکی ڕوودەر.

Lineدێڕی 11-15

enqueue() refuses when the queue is full.

enqueue() کاتێک پڕە ڕەتی دەکاتەوە.

Lineدێڕی 17-21

dequeue() reports underflow instead of crashing.

dequeue() لەبری کەوتن ڕادەگەیەنێت.

Lineدێڕی 26-27

show() lists the whole queue, front first.

show() هەموو پیشان دەدات، پێشەوە یەکەم.

A deque can also have a built-in limit: deque(maxlen=3). But it behaves differently. When it is full, a new item is still added and the oldest one silently drops off the other end. There is no overflow message:

دەتوانێت سنوورێکی ئامادەشی هەبێت: deque(maxlen=3). بەڵام بە شێوەیەکی جیاواز ڕەفتار دەکات. کاتێک پڕە، نوێ هەر زیاد دەکرێت و کۆنترینیان بێدەنگ لە سەرەکەی ترەوە دەکەوێتە دەرەوە. هیچ پەیامێکی نییە:

maxlen keeps only the newestmaxlen تەنها نوێترینەکان دەهێڵێتەوەmaxlen_demo.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

last_orders = deque(maxlen=3)     # keep only the 3 newest orders
for order in ["tea", "coffee", "juice", "kebab", "dolma"]:
    last_orders.append(order)
    print(f"{order:7} -> {list(last_orders)}")
print(last_orders.maxlen)

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

Lineدێڕی 3

At most 3 items; the deque never grows beyond that.

زۆرترین 3 ؛ هەرگیز لەوە گەورەتر نابێت.

Lineدێڕی 5

On a full deque, append() pushes the oldest out of the front.

لەسەر پڕ، append() کۆنترین لە پێشەوە دەردەکات.

Compareبەراورد	`is_full()` checkپشکنینی `is_full()`	`deque(maxlen=n)deque(maxlen=n)`
When fullکاتێک پڕە	the new item is refused نوێ ڕەت دەکرێتەوە	the oldest item is droppedکۆنترین فڕێ دەدرێت
You are toldئاگادار دەکرێیتەوە	yes, your code prints itبەڵێ، کۆدەکەت چاپی دەکات	no, it happens silentlyنەخێر، بێدەنگ ڕوو دەدات
Good forباشە بۆ	people, orders, jobs: nobody may be lostخەڵک، داواکاری، کار: نابێت کەس ون بێت	"the last n": recent files, recent orders, undo steps«دوایین n »: ئەم دواییە، دوایین داواکارییەکان، هەنگاوەکانی

A program: serving customers in orderبەرنامەیەک: خزمەتکردنی کڕیاران بە ڕیز

A morning at a bank counter: two customers arrive, one is served, three more arrive, and then everybody left is served in order. The cashier types each person's number as they come in:

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

Serving customers in arrival orderخزمەتکردنی کڕیاران بە ڕیزبەندیی گەیشتنbank_queue.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

queue = deque()
queue.append(input("Number of the person who comes in: "))
queue.append(input("Number of the person who comes in: "))
print("Served:", queue.popleft())
print("People waiting:", len(queue))
for i in range(3):
    queue.append(input("Number of the person who comes in: "))
print("Now we serve everyone who is left:")
while queue:                      # stops when the queue is empty: no None
    print("Served:", queue.popleft())
print("The queue is empty.")

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

Lineدێڕی 4-5

Two people join at the rear.

دوو کەس لە دواوە دێنە ناوی.

Lineدێڕی 6-7

The first one is served; one is still waiting.

یەکەمیان خزمەت دەکرێت؛ یەکێک هێشتا چاوەڕێ دەکات.

Lineدێڕی 11-12

while queue: stops as soon as the queue is empty, so the program never prints None for an empty queue.

while queue: هەر کە بەتاڵ بوو دەوەستێت، بۆیە هەرگیز بۆ بەتاڵ None چاپ ناکات.

P1 was served first and P5 last: the order of arrival. The textbook's version calls dequeue() one time too many and prints None; testing while queue: avoids that.

⁦P1⁩ یەکەم جار و ⁦P5⁩ دوایین جار خزمەت کران: ڕیزبەندیی گەیشتن. وەشانەکەی کتێبەکە dequeue() یەک جار زیاتر بانگ دەکات و None چاپ دەکات؛ تاقیکردنەوەی while queue: ڕێگری لەوە دەکات.

The deque: a queue with two open endsکیووی دووسەرە: کیوویەک بە دوو سەری کراوە

A deque (say "deck": double-ended queue) lets you add and remove at both ends. It does not decide for you which end to use: use one end only and it behaves as a stack; add at one end and remove at the other and it behaves as a queue.

(بە ئینگلیزی وەک «دێک» دەخوێنرێتەوە: ⁦double-ended queue⁩) ڕێگە دەدات لە هەردوو سەرەوە زیاد بکەیت و لابەریت. بڕیار نادات کام سەر بەکار بهێنیت: تەنها یەک سەر بەکار بهێنە، وەک ڕەفتار دەکات؛ لە سەرێکەوە زیاد بکە و لە سەرەکەی ترەوە لابەرە، وەک ڕەفتار دەکات.

Everyday deques. Someone who has already bought a bus ticket comes back to ask a question and is let in at the front. At a toll gate with several lanes, when one lane is empty, the cars at the rear of the other lanes leave them and move to the free one.
Deques in computing. A list of recently closed browser tabs or recently opened files with a fixed size (the newest is reopened first; when it is full, the oldest falls off the other end); undo and redo with a limited number of steps; checking palindromes (next screen).

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

The deque: a queue with two open endsکیووی دووسەرە: کیوویەک بە دوو سەری کراوە

Deque operations in Pythonکارەکانی کیووی دووسەرە لە Pythonـدا

The textbook's insertFront, insertRear, deletionFront, deletionRear, getFront and getRear, in PythoninsertFront، insertRear، deletionFront، deletionRear، getFront و getRearـی کتێبەکە لە
Operationکار	With a dequeبە	With a list (textbook)بە (کتێبەکە)
insert at the frontزیادکردن لە پێشەوە	`d.appendleft(x)`	`lst.insert(0, x)`: slow`lst.insert(0, x)`: هێواش
insert at the rearزیادکردن لە دواوە	`d.append(x)`	`lst.append(x)`
delete from the frontلابردن لە پێشەوە	`d.popleft()`	`lst.pop(0)`: slow`lst.pop(0)`: هێواش
delete from the rearلابردن لە دواوە	`d.pop()`	`lst.pop()`
look at the front / rearسەیرکردنی پێشەوە / دواوە	`d[0] / d[-1]`	`lst[0] / lst[-1]`
is it empty? how many?بەتاڵە؟ چەندە؟	`not d / len(d)`	`not lst / len(lst)`

Both ends, then a stack and a queue from one typeهەردوو سەر، پاشان ستاک و کیوو لە یەک جۆرdeque_both_ends.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

d = deque(["B", "C"])
d.appendleft("A")                 # add at the front
d.append("D")                     # add at the rear
print(d, " front:", d[0], " rear:", d[-1])
print(d.popleft(), d.pop())       # remove from the front, then the rear
print(d)

stack = deque()                   # one end only: a stack
for x in [1, 2, 3]:
    stack.append(x)
print("stack:", stack.pop(), stack.pop(), stack.pop())

queue = deque()                   # in at one end, out at the other: a queue
for x in [1, 2, 3]:
    queue.append(x)
print("queue:", queue.popleft(), queue.popleft(), queue.popleft())

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

Lineدێڕی 4-5

appendleft() adds at the front, append() at the rear.

appendleft() لە پێشەوە زیاد دەکات، append() لە دواوە.

Lineدێڕی 10-13

Same end in and out: last in, first out (a stack).

هەمان سەر بۆ هاتن و ڕۆیشتن: دوایین هاتوو، یەکەم دەرچوو ().

Lineدێڕی 15-18

In at the rear, out at the front: first in, first out (a queue).

لە دواوە دێتە ناو، لە پێشەوە دەڕوات: یەکەم هاتوو، یەکەم دەرچوو ().

Intermediate Python Tutorial #8 - Collections/Deque(deck)Tech With Tim · Englishئینگلیزی · 46K viewsبینین · 1.5K likesلایک · Partبەشی 1:05–8:57 (ofلە 9:55)
The deque's operations in Python: append, pop, extend, extendleft, rotate and a deque with maxlen that drops old items.
کارەکانی لە : `append`، `pop`، `extend`، `extendleft`، `rotate` و بە `maxlen` کە کۆن فڕێدەدات.
Watch 1:05–8:57: creating a deque, append and appendleft, pop and popleft, clear, extend, extendleft, reverse, rotate and maxlen (6:37). Careful at 2:47: an index in pop() works for lists, not for a deque; a deque's pop() takes none.
لە ⁦1:05⁩ تا ⁦8:57⁩ سەیر بکە: دروستکردنی ، `append` و `appendleft`، `pop` و `popleft`، `clear`، `extend`، `extendleft`، `reverse`، `rotate` و `maxlen` ⁦(6:37)⁩. ئاگادار بە لە ⁦2:47⁩: لەناو `pop()` بۆ کار دەکات، نەک بۆ ؛ `pop()`ـی هیچ وەرناگرێت.

The deque: a queue with two open endsکیووی دووسەرە: کیوویەک بە دوو سەری کراوە

Recently opened files: a deque with maxlenفایلەکان کە ئەم دواییە کراونەتەوە: کیوویەکی دووسەرە بە maxlen

An editor shows the three files you opened last, newest first. appendleft() puts each new name at the front, and maxlen=3 drops the oldest from the rear by itself:

ئەو سێ دوایین جار کردووتنەتەوە پیشان دەدات، نوێترین یەکەم. appendleft() هەر ناوێکی نوێ دەخاتە پێشەوە و maxlen=3 خۆی کۆنترینیان لە دواوە فڕێ دەدات:

The "Recent files" menuمێنیوی «⁦Recent files⁩»recent_files.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

recent = deque(maxlen=3)          # the "Recent files" list of an editor
for name in ["marks.txt", "notes.txt", "shop.csv", "photo.png"]:
    recent.appendleft(name)       # newest at the front
    print(list(recent))
print("Reopen:", recent.popleft())

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

Lineدێڕی 5

Newest at the front; when the fourth file opens, marks.txt falls off the rear.

نوێترین لە پێشەوە؛ کاتێک چوارەم دەکرێتەوە، marks.txt لە دواوە دەکەوێتە دەرەوە.

Lineدێڕی 7

Reopening takes the newest one from the front.

کردنەوەی دووبارە نوێترینیان لە پێشەوە وەردەگرێت.

Use: is it a palindrome?بەکارهێنان: ئایا پالیندرۆمە؟

A palindrome reads the same from both ends: level, racecar, and in Kurdish «نان», «کاک» and «مام». A deque checks this naturally, because it can give the first and the last letter equally easily:

پالیندرۆم (palindrome) لە هەردوو سەرەوە وەک یەک دەخوێنرێتەوە: level، racecar و بە کوردی «نان»، «کاک» و «مام». بە شێوەیەکی سروشتی ئەمە دەپشکنێت، چونکە دەتوانێت یەکەم و دوایین پیت بە هەمان ئاسانی بدات:

The algorithmئەلگۆریزمەکە

Put every letter of the word into a deque, from the first to the last (insert at the rear).
هەموو پیتێکی وشەکە بخەرە ناو ، لە یەکەمەوە تا دوایین (زیادکردن لە دواوە).
Remove one letter from the front and one from the rear.
پیتێک لە پێشەوە و پیتێک لە دواوە لابەرە.
If they differ, it is not a palindrome: stop.
ئەگەر جیاواز بوون، پالیندرۆم نییە: بوەستە.
Repeat until zero or one letter is left: then it is a palindrome.
دووبارە بکەرەوە تا سفر یان یەک پیت دەمێنێتەوە: ئەو کاتە پالیندرۆمە.

The deque while checking racecar لە کاتی پشکنینی racecar
Deque (front … rear) (پێشەوە … دواوە)	Removedلابراو	Same?وەک یەکن؟
`r a c e c a r`	`r` + `r`	✓
`a c e c a`	`a` + `a`	✓
`c e c`	`c` + `c`	✓
`e`	one letter leftتەنها یەک پیت هەیە	palindromeپالیندرۆمە

Palindromes with a dequeپالیندرۆم بە کیوویەکی دووسەرەpalindrome.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

def is_palindrome(text, show=False):
    letters = deque(ch.lower() for ch in text if ch != " ")
    while len(letters) > 1:
        if show:
            print("   ", "".join(letters))
        first = letters.popleft()     # one from the front
        last = letters.pop()          # one from the rear
        if first != last:
            return False
    return True                       # 0 or 1 letter left

print(is_palindrome("racecar", show=True))
for word in ["level", "Erbil", "Never odd or even", "نان", "کاک", "مام", "چا"]:
    print(f"{word:18} {is_palindrome(word)}")

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

Lineدێڕی 4

Lower-case letters only, without spaces, so Never odd or even counts.

تەنها پیتی بچووک، بەبێ بۆشایی، بۆیە ⁦Never odd or even⁩ دەژمێردرێت.

Lineدێڕی 8-9

One letter from each end.

پیتێک لە هەر سەرێکەوە.

Lineدێڕی 12

Zero or one letter left: every pair matched.

سفر یان یەک پیت هەیە: هەموو جووتێک یەکی گرتەوە.

This program lets the user choose where to add and where to remove. Adding at the rear and removing from the front makes it a queue; adding and removing at the same end makes it a stack. In the run below, Karwan is added at the front, so he is served before Aram even though he came last:

ئەم ڕێگە بە دەدات هەڵبژێرێت لە کوێ زیاد بکات و لە کوێ لابەرێت. زیادکردن لە دواوە و لابردن لە پێشەوە دەیکات بە ؛ زیادکردن و لابردن لە هەمان سەرەوە دەیکات بە . لە کارپێکردنی خوارەوەدا Karwan لە پێشەوە زیاد دەکرێت، بۆیە پێش Aram خزمەت دەکرێت هەرچەندە دوایین کەس هات:

Menu-driven dequeکیووی دووسەرە بە هەڵبژاردنی ژمارەییdeque_menu.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

items = deque()
while True:
    print("1 add at rear  2 add at front  3 remove front  4 remove rear  5 show  0 quit")
    choice = input("Choice: ")
    if choice == "0":
        break
    elif choice == "1":
        items.append(input("Value: "))
    elif choice == "2":
        items.appendleft(input("Value: "))
    elif choice in ("3", "4"):
        if not items:
            print("Underflow: nothing to remove")
        elif choice == "3":
            print("Removed from the front:", items.popleft())
        else:
            print("Removed from the rear:", items.pop())
    elif choice == "5":
        print("front ->", list(items), "<- rear")
    else:
        print("Please choose 0-5")

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

Lineدێڕی 9-12

Choices 1 and 2 add at the rear or at the front.

هەڵبژاردنی 1 و 2 لە دواوە یان لە پێشەوە زیاد دەکەن.

Lineدێڕی 13-19

Choices 3 and 4 remove, after checking for underflow.

هەڵبژاردنی 3 و 4 دوای پشکنینی لادەبەن.

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

Mistakeهەڵە	What happensچی ڕوو دەدات	Fixچارەسەر
`q.pop()` instead of `q.popleft()q.pop()` لەبری `q.popleft()`	the newest item leaves: the queue becomes a stackنوێترین دەڕوات: دەبێتە	`append()` with `popleft()` (or `appendleft()` with `pop()`)`append()` لەگەڵ `popleft()` (یان `appendleft()` لەگەڵ `pop()`)
`q.pop(0)` on a deque`q.pop(0)` لەسەر	`TypeError: deque.pop() takes no arguments (1 given)`	`q.popleft()`
`list.pop(0)` in a long loop`list.pop(0)` لە درێژدا	very slow: every other element moves each timeزۆر هێواش: هەموو جارێک هەموو تر دەجووڵێن	`collections.deque` and `popleft()collections.deque` و `popleft()`
Dequeuing or peeking at an empty queuedequeue یان peek لە بەتاڵ	`IndexError: pop from an empty deque` or `deque index out of rangeIndexError: pop from an empty deque` یان `deque index out of range`	test `if q:` or `while q:` firstسەرەتا `if q:` یان `while q:` تاقی بکەرەوە
`maxlen` where nothing may be lost`maxlen` لە شوێنێک کە نابێت هیچ شتێک ون بێت	the oldest item is dropped without a messageکۆنترین بەبێ هیچ پەیامێک فڕێ دەدرێت	an `is_full()` check that refuses and reportsپشکنینی `is_full()` کە ڕەت دەکاتەوە و ڕایدەگەیەنێت
Forgetting `from collections import deque`لەبیرکردنی `from collections import deque`	`NameError: name 'deque' is not defined`	import it at the top of the programلە سەرەوەی هاوردەی بکە
Using a queue when the newest item matters most (undo, Back)بەکارهێنانی کاتێک نوێترین گرنگترە (undo، Back)	the oldest action is undone firstکۆنترین کار یەکەم جار پاشگەز دەکرێتەوە	a stack (LIFO) for "most recent first" ⁦(LIFO)⁩ بۆ «نوێترین یەکەم»

Exercisesڕاهێنانەکان

ExerciseڕاهێنانFill in the blanksبۆشاییەکان پڕ بکەرەوە

(a) A ____ is a linear list where items are added at one end and removed at the other. (b) A queue serves its items in ____ order. (c) Adding an item to a queue is called ____ and removing one is called ____. (d) Items leave a queue from its ____. (e) A queue holds K, R, D and S, with K at the front. If they are removed one at a time, they come out in the order ____. (f) A ____ allows adding and removing at either end, but not in the middle. (g) A deque holds p, q, r, s, t (p at the front). The items come out in the order p, t, s, q, r. Which deletions were made?

(أ) ⁦____⁩ زنجیرەیەکی هێڵییە کە لە سەرێکەوە زیاد دەکرێن و لە سەرەکەی ترەوە لادەبرێن. (ب) بە ڕیزبەندیی ⁦____⁩ خزمەت دەکات. (ج) زیادکردنی بۆ پێی دەوترێت ⁦____⁩ و لابردنی یەکێک پێی دەوترێت ⁦____⁩. (د) لە ⁦____⁩ـی دەڕۆن. (هـ) K، R، D و S هەڵدەگرێت و K لە پێشەوەیە. ئەگەر یەک یەک لابرێن، بەم ڕیزبەندییە دەردەچن: ⁦____⁩. (و) ⁦____⁩ ڕێگە دەدات لە هەر دوو سەرەوە زیاد بکەیت و لابەریت، بەڵام نەک لە ناوەڕاستەوە. (ز) p، q، r، s، t هەڵدەگرێت (p لە پێشەوە). بەم ڕیزبەندییە دەردەچن: p، t، s، q، r. کام لابردنانە کراون؟

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

(a) queue; (b) first in, first out (FIFO); (c) enqueue, dequeue; (d) front; (e) K, R, D, S; (f) deque.
(g) front (p), rear (t), rear (s), front (q), then front or rear (r is the only one left).

(أ) ؛ (ب) یەکەم هاتوو، یەکەم دەرچوو ⁦(FIFO)⁩؛ (ج) enqueue، dequeue؛ (د) پێشەوە؛ (هـ) K، R، D، S؛ (و) .
(ز) پێشەوە ⁦(p)⁩، دواوە ⁦(t)⁩، دواوە ⁦(s)⁩، پێشەوە ⁦(q)⁩، پاشان پێشەوە یان دواوە (تەنها r هەیە).

Checked with popleft() and pop()بە ⁦popleft()⁩ و ⁦pop()⁩ پشکنرا

['K', 'R', 'D', 'S']
['p', 't', 's', 'q', 'r']

ExerciseڕاهێنانQueue or stack?کیوو یان ستاک؟

Compare a queue with a stack. How does FIFO describe a queue?

لەگەڵ بەراورد بکە. FIFO چۆن باسی دەکات؟

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

Compareبەراورد	Stack	Queue
Open endsسەرە کراوەکان	one: the topیەک: سەر	two: rear (in) and front (out)دوو: دواوە (هاتن) و پێشەوە (ڕۆیشتن)
Orderڕیزبەندی	last in, first out (LIFO)دوایین هاتوو، یەکەم دەرچوو ⁦(LIFO)⁩	first in, first out (FIFO)یەکەم هاتوو، یەکەم دەرچوو ⁦(FIFO)⁩
Operationsکارەکان	push, pop, peekpush، pop، peek	enqueue, dequeue, peekenqueue، dequeue، peek
Python	list: `append()`, `pop()`: `append()`، `pop()`	deque: `append()`, `popleft()`: `append()`، `popleft()`
Examplesنموونە	undo, Back button, call stack, bracketsundo، دوگمەی Back، ، کەوانە	print jobs, web requests, bakery lineکارەکانی چاپ، وێب، ڕیزی نانەواخانە

FIFO, first in, first out, says that the item which has waited longest is always the next to leave.

FIFO، یەکەم هاتوو، یەکەم دەرچوو، دەڵێت ئەو زۆرترین چاوەڕێی کردووە هەمیشە داهاتووە کە دەڕوات.

ExerciseڕاهێنانThe shuttlecock tubeقوتووی تۆپی بادمینتن

A badminton club keeps shuttlecocks in a tube that is open at both ends: new ones are pushed in at the bottom, and players take one out at the top, so the oldest is used first. A tube holds 12. Write a menu-driven program: 1 put a new one in, 2 take one out, 3 show the tube, 0 quit.

یانەیەکی بادمینتن تۆپەکانی بادمینتن (shuttlecock) لە قوتوویەکدا هەڵدەگرێت کە هەردوو سەری کراوەیە: تۆپی نوێ لە خوارەوە دەخرێتە ناوی و یاریزانان لە سەرەوە یەکێک دەردەهێنن، بۆیە کۆنترینیان یەکەم جار بەکار دێت. قوتوویەک ⁦12⁩ تۆپ دەگرێت. بە هەڵبژاردنی ژمارەیی بنووسە: 1 تۆپێکی نوێ بخەرە ناو، 2 یەکێک دەربهێنە، 3 قوتووەکە پیشان بدە، 0 دەرچوون.

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

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

from collections import deque

TUBE_SIZE = 12                    # a tube holds 12 shuttlecocks
tube = deque()
number = 0
while True:
    choice = input("1 put a new one in  2 take one out  3 show  0 quit: ")
    if choice == "0":
        break
    if choice == "1":
        if len(tube) == TUBE_SIZE:
            print("The tube is full")
        else:
            number += 1
            tube.append(number)   # new ones go in at the bottom (rear)
    elif choice == "2":
        if tube:
            print("Play with shuttlecock", tube.popleft())   # the oldest comes out at the top
        else:
            print("The tube is empty")
    elif choice == "3":
        print("top ->", list(tube), "<- bottom")

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

Lineدێڕی 15

New shuttlecocks join at the rear (the bottom).

تۆپە نوێیەکان لە دواوە (خوارەوە) دێنە ناوی.

Lineدێڕی 18

The oldest comes out at the front (the top): a queue.

کۆنترینیان لە پێشەوە (سەرەوە) دەردەچێت: .

ExerciseڕاهێنانTrace a queueبەدوای کیوویەکدا بچۆ

First say how a queue differs from a deque. Then show the queue after each operation, starting empty: enqueue(15), enqueue(40), enqueue(7), dequeue(), enqueue(22), peek(), dequeue(), dequeue(), dequeue(), dequeue(), enqueue(9).

سەرەتا بڵێ چۆن لە جیاوازە. پاشان دوای هەر کارێک پیشان بدە، بە بەتاڵی دەست پێ بکە: ⁦enqueue(15)⁩، ⁦enqueue(40)⁩، ⁦enqueue(7)⁩، ⁦dequeue()⁩، ⁦enqueue(22)⁩، ⁦peek()⁩، ⁦dequeue()⁩، ⁦dequeue()⁩، ⁦dequeue()⁩، ⁦dequeue()⁩، ⁦enqueue(9)⁩.

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

A queue adds only at the rear and removes only at the front; a deque may add and remove at both ends.

تەنها لە دواوە زیاد دەکات و تەنها لە پێشەوە لادەبات؛ دەتوانێت لە هەردوو سەرەوە زیاد بکات و لابەرێت.

Traced with a dequeبە کیوویەکی دووسەرە بەدواداچوونی بۆ کراوە

enqueue(15)   front -> 15
enqueue(40)   front -> 15 40
enqueue(7)    front -> 15 40 7
   dequeue() gives 15
dequeue()     front -> 40 7
enqueue(22)   front -> 40 7 22
   peek() gives 40
peek()        front -> 40 7 22
   dequeue() gives 40
dequeue()     front -> 7 22
   dequeue() gives 7
dequeue()     front -> 22
   dequeue() gives 22
dequeue()     front -> (empty)
   dequeue(): underflow, the queue is empty
dequeue()     front -> (empty)
enqueue(9)    front -> 9

The fourth dequeue() in a row finds the queue empty: underflow. peek() only looks, so the queue does not change.

چوارەم dequeue()ـی یەک لە دوای یەک بە بەتاڵی دەبینێت: . peek() تەنها سەیر دەکات، بۆیە ناگۆڕێت.

ExerciseڕاهێنانTrace a dequeبەدوای کیوویەکی دووسەرەدا بچۆ

Starting with an empty deque, show it after each operation: get_front(), insert_front(5), insert_rear(30), delete_front(), insert_rear(18), delete_rear(), delete_front(), delete_rear(). Mark every underflow.

بە بەتاڵ دەست پێ بکە و دوای هەر کارێک پیشانی بدە: ⁦get_front()⁩، ⁦insert_front(5)⁩، ⁦insert_rear(30)⁩، ⁦delete_front()⁩، ⁦insert_rear(18)⁩، ⁦delete_rear()⁩، ⁦delete_front()⁩، ⁦delete_rear()⁩. هەموو دیاری بکە.

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

Traced with appendleft(), append(), popleft() and pop()بە ⁦appendleft()⁩، ⁦append()⁩، ⁦popleft()⁩ و ⁦pop()⁩ بەدواداچوونی بۆ کراوە

   get_front(): underflow, empty
get_front()      front -> (empty)
insert_front(5)  front -> 5
insert_rear(30)  front -> 5 30
   removed 5
delete_front()   front -> 30
insert_rear(18)  front -> 30 18
   removed 18
delete_rear()    front -> 30
   removed 30
delete_front()   front -> (empty)
   delete_rear(): underflow, empty
delete_rear()    front -> (empty)

Two underflows: get_front() at the start and the last delete_rear(), both on an empty deque.

دوو : get_front() لە سەرەتادا و دوایین delete_rear()، هەردووکیان لەسەر بەتاڵ.

ExerciseڕاهێنانPalindromes with punctuationپالیندرۆم لەگەڵ خاڵبەندی

Change is_palindrome() so that it ignores everything except letters, so that Was it a car or a cat I saw? counts as a palindrome.

is_palindrome() بگۆڕە بۆ ئەوەی جگە لە پیت هەموو شتێک پشتگوێ بخات، بۆ ئەوەی ⁦Was it a car or a cat I saw?⁩ وەک پالیندرۆم بژمێردرێت.

Hintئاماژە

Use ch.isalpha() instead of ch != " " when you fill the deque.

لە کاتی پڕکردنەوەی ch.isalpha() لەبری ch != " " بەکار بهێنە.

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

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

from collections import deque

def is_palindrome(text):
    letters = deque(ch.lower() for ch in text if ch.isalpha())   # letters only
    while len(letters) > 1:
        if letters.popleft() != letters.pop():
            return False
    return True

for s in ["Was it a car or a cat I saw?", "Step on no pets!", "Erbil, Kurdistan", "نان", "کاک"]:
    print(f"{s!r:32} {is_palindrome(s)}")

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

Lineدێڕی 4

isalpha() keeps letters only, Kurdish letters too.

isalpha() تەنها پیتەکان دەهێڵێتەوە، پیتە کوردییەکانیش.

Summaryپوختە

A queue adds at the rear and removes at the front: first in, first out (FIFO).
Operations: enqueue, dequeue, peek, is_empty, size, and is_full for a fixed size. Enqueue on a full queue is overflow; dequeue on an empty one is underflow.
Queues order print jobs, processor tasks, web requests and key presses; urgent work needs a priority queue.
list.pop(0) works but moves every other element; use collections.deque with append() and popleft().
deque(maxlen=n) silently drops the oldest item; an is_full() check refuses the newest.
A deque adds and removes at both ends: one end used alone is a stack, opposite ends make a queue. It also checks palindromes and keeps "recent" lists.

لە دواوە زیاد دەکات و لە پێشەوە لادەبات: یەکەم هاتوو، یەکەم دەرچوو ⁦(FIFO)⁩.
کارەکان: enqueue، dequeue، peek، ⁦is_empty⁩، size و ⁦is_full⁩ بۆ قەبارەی جێگیر. enqueue لەسەر پڕ ؛ dequeue لە بەتاڵ .
کارەکانی چاپ، کارەکانی پرۆسێسەر، وێب و داگرتنی دوگمەکان ڕیز دەکەن؛ کاری بەپەلە پێویستی بە هەیە.
list.pop(0) کار دەکات بەڵام هەموو تر دەجووڵێنێت؛ collections.deque لەگەڵ append() و popleft() بەکار بهێنە.
deque(maxlen=n) بێدەنگ کۆنترین فڕێ دەدات؛ پشکنینی is_full() نوێترینیان ڕەت دەکاتەوە.
لە هەردوو سەرەوە زیاد دەکات و لادەبات: یەک سەر بە تەنها ، دوو سەری جیاواز دروست دەکەن. هەروەها پالیندرۆم دەپشکنێت و شتە تازەکان هەڵدەگرێت.

Next in this chapter come two lessons on algorithms that work on lists: sorting and searching.

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

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

Which deque methods make a queue?کام میتۆدەکانی کیووی دووسەرە کیوویەک دروست دەکەن؟

append() to enqueue at the rear and popleft() to dequeue from the front.

append() بۆ enqueue لە دواوە و popleft() بۆ dequeue لە پێشەوە.

Why not list.pop(0) for a big queue?بۆچی list.pop(0) بۆ کیوویەکی گەورە نا؟

Every remaining element must move one place, so a long queue becomes very slow.

هەموو تر دەبێت یەک شوێن بجووڵێن، بۆیە درێژ زۆر هێواش دەبێت.

What happens when a deque(maxlen=3) is full and you append()?کاتێک deque(maxlen=3) پڕە و append() دەکەیت چی ڕوو دەدات؟

The new item is added and the oldest falls off the front, with no message.

نوێ زیاد دەکرێت و کۆنترینیان لە پێشەوە دەکەوێتە دەرەوە، بەبێ هیچ پەیامێک.

How does a deque check a palindrome?کیوویەکی دووسەرە چۆن پالیندرۆم دەپشکنێت؟

It compares the letter from the front with the letter from the rear, pair by pair, until zero or one is left.

پیتی پێشەوە لەگەڵ پیتی دواوە بەراورد دەکات، جووت بە جووت، تا سفر یان یەک پیت دەمێنێتەوە.

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

Queues in 3 minutesMichael Sambol · Englishئینگلیزی · 138K viewsبینین · 2.7K likesلایک
A queue in three minutes: first in, first out, enqueue at the back, dequeue at the front, and Python's collections.deque.
لە سێ خولەکدا: FIFO (یەکەم هاتوو یەکەم دەڕوات)، enqueue لە دواوە، dequeue لە پێشەوە و `collections.deque` لە .
A 3-minute overview of the queue, with code that uses collections.deque.
پێداچوونەوەیەکی 3 خولەکی بۆ ، لەگەڵ کۆدێک کە `collections.deque` بەکاردەهێنێت.

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

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

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

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

Bubble Sort, Insertion Sort and How Fast Sorting Isڕیزکردنی بڵقی، ڕیزکردن بە تێخستن و خێرایی ڕیزکردن

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 ن.

Queues and Deques: First In, First Outکیووەکان و کیووە دووسەرەکان: یەکەم هاتوو، یەکەم دەرچوو

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

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

Queues in computingکیووەکان لە کۆمپیوتەردا

Queue operations: enqueue and dequeueکارەکانی کیوو: enqueue و dequeue

A queue made from a listکیوویەک لە لیستێکەوە

The hidden cost of pop(0)تێچووی شاراوەی pop(0)

The right tool: collections.dequeئامرازی دروست: ⁦collections.deque⁩

A print queue, step by stepکیووی چاپ، هەنگاو بە هەنگاو

A queue with a limit: is_full() or maxlenکیوویەک بە سنوور: ⁦is_full()⁩ یان maxlen

A program: serving customers in orderبەرنامەیەک: خزمەتکردنی کڕیاران بە ڕیز

The deque: a queue with two open endsکیووی دووسەرە: کیوویەک بە دوو سەری کراوە

Deque operations in Pythonکارەکانی کیووی دووسەرە لە Pythonـدا

Recently opened files: a deque with maxlenفایلەکان کە ئەم دواییە کراونەتەوە: کیوویەکی دووسەرە بە maxlen

Use: is it a palindrome?بەکارهێنان: ئایا پالیندرۆمە؟

A menu program: one deque, two behavioursبەرنامەیەک بە هەڵبژاردنی ژمارەیی: یەک کیووی دووسەرە، دوو ڕەفتار

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

Exercisesڕاهێنانەکان

Summaryپوختە

Watch a videoسەیری ڤیدیۆیەک بکە

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

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

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

The hidden cost of pop(0)تێچووی شاراوەی `pop(0)`