Stacks and queues (array-backed) · Pilhas e filas (backed por array)
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.
Duas formas de segurar itens
- Uma stack e uma queue ambas seguram uma fila de itens, mas diferem em qual item sai primeiro.
- Uma stack é LIFO: Last In, First Out — como uma pilha de pratos.
- Uma queue é FIFO: First In, First Out — como uma fila de pessoas.
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.
Uma stack é LIFO
- push adiciona um item no topo. pop remove e retorna o item do topo. peek olha para o topo sem removê-lo.
- O último item que você empilhou é o primeiro que você retira.
- Guardamos os itens em um array
datae um índicetopque conta quantos estão lá.
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".)
Stack baseado em array
- Com
topcomo a contagem, o item do topo está emdata[top - 1]. - push: escreva em
data[top], depoistop++. pop:top--, depois retornedata[top]. - (Para estas tarefas o array é grande o suficiente; não precisa verificar se está "cheio".)
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).
Uma queue é FIFO
- enqueue adiciona um item na parte traseira. dequeue remove e retorna o item na parte frontal.
- O primeiro item que você enfileira é o primeiro que você retira.
- Mantemos dois índices:
front(próximo a sair) eback(próximo slot livre).
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".)
Queue baseado em array
- enqueue: escreva em
data[back], depoisback++. dequeue: leiadata[front], depoisfront++, e retorne-o. frontperseguebackconforme os itens chegam e saem.- (Para estas tarefas o array é grande o suficiente; não precisa dar volta ou verificar se está "vazio".)
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.
Erros comuns
- Uma stack é last-in-first-out; uma queue é first-in-first-out.
- Verifique se a estrutura não está vazia antes de pop ou 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.
Agora você tenta
- As structs
StackeQueuesão dadas no starter. Uses->top,q->fronteq->back. - Não escreva um
main— o verificador fornece um.
Stacks and queues · Pilhas e filas
A stack is LIFO; a queue is FIFO. Step through the operations. · Uma pilha é LIFO; uma fila é FIFO. Passe pelas operações.
The · A Stack struct (with data and a count top) is given. Complete void push(Stack *s, int v) and · e int pop(Stack *s) so the stack is LIFO. Do not · não write a main. · A estrutura Stack (com data e uma contagem top) é fornecida. Complete void push(Stack *s, int v) e int pop(Stack *s) para que a pilha seja LIFO. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
The · A 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 · não write a main. · A estrutura Stack é fornecida. Complete int peek(const Stack *s) para retornar o item superior sem removê-lo. Suponha que a pilha não esteja vazia. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
The · A Queue struct (with data, front, and back) is given. Complete void enqueue(Queue *q, int v) and · e int dequeue(Queue *q) so the queue is FIFO. Do not · não write a main. · A estrutura Queue (com data, front e back) é fornecida. Complete void enqueue(Queue *q, int v) e int dequeue(Queue *q) para que a fila seja FIFO. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.