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:后进先出 —— 就像一摞盘子。
- 队列是 FIFO:先进先出 —— 就像排队的人。
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 看一眼顶部但不移除。
- 你最后 push 的那个,就是你最先 pop 的那个。
- 我们把元素存在数组
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 移除并返回前端的元素。
- 你最先 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在后面追着back。 - (这些任务里数组足够大;你不需要环绕,也不需要检查“空了”。)
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.
常见错误
- 栈是后进先出,队列是先进先出。
- pop 或出队前先检查结构不是空的。
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. · 栈是后进先出;队列是先进先出。逐步查看操作。
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. · 点击“运行”查看此处输出。