Стек, навбат, deque

Рӯйхат дар Python ҳама чизро метавонад: дар ҳар ҷо илова ва нест кардан. Вале дар бисёр масъалаҳо танҳо ду тарзи кор бо маълумот лозим аст, ва онҳо номҳои худро доранд — стек ва навбат. Агар онҳоро дар масъала шиносӣ, ҳал аксар вақт равшан мешавад.

Стек

Стек — тӯдаи табақҳост: ба боло мегузорем ва аз боло мегирем. «Охирин омад — аввал рафт» (бо англисӣ LIFO).

Дар Python стек — рӯйхати оддӣ аст, ки бо он танҳо аз охир кор мекунанд:

stack = []
stack.append("a")     # ба боло гузоштан
stack.append("b")
stack.append("c")
print(stack[-1])      # c — ба боло нигоҳ кардан
print(stack.pop())    # c — болоро гирифтан
print(stack.pop())    # b
print(len(stack))     # 1

append ва pop() аз охир фаврӣ кор мекунанд. Пеш аз pop() санҷ, ки стек холӣ нест: if stack: — вагарна хатои IndexError мешавад.

Стек дар куҷо лозим аст

Стек вақте кумак мекунад, ки «ба охирин нотамом баргаштан» лозим аст:

• бекор кардани амалҳо (Ctrl+Z) — амали охирин бекор мешавад;
• сохторҳои дарунӣ — қавсҳо, тегҳои HTML, даъватҳои функсияҳо;
• гузариш «ба чуқурӣ».

Мисол: баръакс кардани сатр тавассути стек.

stack = []
for ch in "абв":
    stack.append(ch)
res = ""
while stack:
    res += stack.pop()
print(res)    # вба

Мисоли мураккабтар: ҳисобкунак барои навиште, ки дар он амал пас аз ададҳо навишта мешавад (3 4 + 2 * маънои (3 + 4) * 2-ро дорад):

tokens = "3 4 + 2 *".split()
stack = []
for t in tokens:
    if t in "+-*":
        b = stack.pop()
        a = stack.pop()
        if t == "+": stack.append(a + b)
        elif t == "-": stack.append(a - b)
        else: stack.append(a * b)
    else:
        stack.append(int(t))
print(stack.pop())    # 14

Стеки монотонӣ

Баъзан дар стек элементҳоеро нигоҳ медоранд, ки ҳанӯз «ҷавоб интизоранд», ва ҳангоми пайдо шудани элементи нав онҳоеро, ки ба онҳо ҷавоб медиҳад, мегиранд. Он гоҳ ҳар элемент як бор гузошта ва гирифта мешавад, ва тамоми коркард дар n қадам мегузарад. Фикр кун, ки бо чунин стек барои ҳар адад наздиктарин хурдтари аз чап-ро чӣ тавр ёфтан мумкин аст.

Навбат

Навбат — мисли мағоза: ба охир меистем, аз аввал хизмат мерасонанд. «Аввал омад — аввал рафт» (FIFO).

Рӯйхат барои навбат бад аст: pop(0) ҳамаи элементҳоро ҷобаҷо мекунад, ва дар маълумоти калон ин хеле суст аст. Барои навбат deque аз модули collections ҳаст:

from collections import deque

q = deque()
q.append("Анис")       # ба охир истодан
q.append("Бахтиёр")
q.append("Вафо")
print(q.popleft())     # Анис — ба аввалин хизмат расонидан
print(q[0])            # Бахтиёр — навбатӣ кист
print(len(q))          # 2

deque («дек» хонда мешавад) — навбати дутарафа: он амалҳои тезро дар ҳарду охир дорад: append, appendleft, pop, popleft.

Навбат дар куҷо лозим аст

• моделсозии навбатҳо, вазифаҳо, рӯйдодҳо бо тартиби омадан;
• гузариш «ба паҳнӣ» — масалан, ҷустуҷӯи роҳи кӯтоҳтарин дар лабиринт (ин зинаи навбатӣ пас аз курси асосӣ аст);
• «k элементи охирин»: deque(maxlen=k) худаш элементҳои кӯҳнаро мепартояд.

from collections import deque
last = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    last.append(x)
print(list(last))    # [3, 4, 5]

Чӣ тавр интихоб кардан

Лозим аст	Сохтор	Амалҳо
охирин иловашударо гирифтан	стек (list)	append, pop(), [-1]
аввалин иловашударо гирифтан	навбат (deque)	append, popleft(), [0]
бо ҳарду охир кор кардан	deque	append, appendleft, pop, popleft

Хулоса

• стек: append ва pop()-и рӯйхат, «охирин омад — аввал рафт»;
• навбат: deque бо append ва popleft(), «аввал омад — аввал рафт»;
• барои навбат list.pop(0)-ро истифода набар — ин суст аст;
• пеш аз гирифтани элемент холӣ буданро санҷ;
• стек масъалаҳои дарунӣ ва «наздиктарин аз чап/рост»-ро ҳал мекунад, навбат — моделсозӣ бо тартиб.