Stacks and queues (array-backed) · Стеки и очереди (на базе массивов)
Two ways to hold items
- A stack and a queue both hold a line of items, but they differ in which item comes out next.
- A stack is LIFO: Last In, First Out — like a pile of plates.
- A queue is FIFO: First In, First Out — like a line of people.
Два способа хранения элементов
- Стек и очередь оба хранят последовательность элементов, но они различаются тем, какой элемент выйдет следующим.
- Стек работает по принципу LIFO: Last In, First Out (последним пришёл — первым вышел) — как стопка тарелок.
- Очередь работает по принципу FIFO: First In, First Out (первым пришёл — первым вышел) — как очередь людей.
A stack is LIFO
- push adds an item on top. pop removes and returns the top item. peek looks at the top without removing it.
- The last item you pushed is the first one you pop.
- We store the items in an array
dataand an indextopthat counts how many are in.
Стек работает по принципу LIFO
- push добавляет элемент сверху. pop удаляет и возвращает верхний элемент. peek смотрит на верхний элемент, не удаляя его.
- Последний элемент, который вы положили в стек, будет первым, который вы из него достанете.
- Мы храним элементы в массиве
dataи индексеtop, который считает, сколько их находится внутри.
Array-backed stack
- With
topas the count, the top item is atdata[top - 1]. - push: write at
data[top], thentop++. pop:top--, then returndata[top]. - (For these tasks the array is big enough; you do not need to check for "full".)
Стек на основе массива
- При
topкак счетчик, верхний элемент находится по индексуdata[top - 1]. - push: запишите в
data[top], затем увеличьтеtop++. pop: уменьшитеtop--, затем вернитеdata[top]. - (Для этих задач массив достаточно велик; вам не нужно проверять условие «полный».)
A queue is FIFO
- enqueue adds an item at the back. dequeue removes and returns the item at the front.
- The first item you enqueue is the first one you dequeue.
- We keep two indexes:
front(next to leave) andback(next free slot).
Очередь работает по принципу FIFO
- enqueue добавляет элемент в конец. dequeue удаляет и возвращает элемент в начале.
- Первый элемент, который вы поместили в очередь, будет первым, который вы из неё достанете.
- Мы храним два индекса:
front(следующий для удаления) иback(следующая свободная ячейка).
Array-backed queue
- enqueue: write at
data[back], thenback++. dequeue: readdata[front], thenfront++, and return it. frontchasesbackas items come and go.- (For these tasks the array is big enough; you do not need to wrap around or check for "empty".)
Очередь на основе массива
- enqueue: запишите в
data[back], затем увеличьтеback++. dequeue: прочитайте изdata[front], затем увеличьтеfront++и верните значение. frontотслеживает positionbackпо мере поступления и удаления элементов.- (Для этих задач массив достаточно велик; вам не нужно делать цикл (wrap around) или проверять условие «пусто».)
Common mistakes
- A stack is last-in-first-out; a queue is first-in-first-out.
- Check the structure is not empty before you pop or dequeue.
Распространенные ошибки
- Стек работает по принципу last-in-first-out; очередь — first-in-first-out.
- Проверяйте, что структура не пуста, перед тем как вызывать pop или dequeue.
Now you try
- The
StackandQueuestructs are given in the starter. Uses->top,q->front, andq->back. - Do not write a
main— the checker provides one.
Теперь попробуйте сами
- Структуры
StackиQueueпредоставлены в шаблоне. Используйтеs->top,q->frontиq->back. - Не пишите
main— проверяющая система предоставит его.
Stacks and queues · Стеки и очереди
A stack is LIFO; a queue is FIFO. Step through the operations. · Стек работает по принципу LIFO; очередь — FIFO. Разберите последовательность операций.
The Stack struct (with data and a count top) is given. Complete void push(Stack *s, int v) and int pop(Stack *s) so the stack is LIFO. Do not write a main. · Структура ⟨Stack⟩ (с ⟨data⟩ и счетчиком ⟨top⟩) задана. Заполните ⟨void push(Stack *s, int v)⟩ и ⟨int pop(Stack *s)⟩, чтобы стек работал по принципу LIFO. Не пишите ни main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
The Stack struct is given. Complete int peek(const Stack *s) so it returns the top item without removing it. Assume the stack is not empty. Do not write a main. · Структура Stack задана. Завершите int peek(const Stack *s) так, чтобы она возвращала верхний элемент без его удаления. Предположите, что стек не пуст. Не пишите код для main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
The Queue struct (with data, front, and back) is given. Complete void enqueue(Queue *q, int v) and int dequeue(Queue *q) so the queue is FIFO. Do not write a main. · Структура Queue (с полями data, front и back) задана. Завершите void enqueue(Queue *q, int v) и int dequeue(Queue *q) так, чтобы очередь работала по принципу FIFO. Не пишите код для main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.