Stacks and queues (array-backed) · Stacks และ queues (ใช้ 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.
วิธีสองอย่างในการจัดเก็บรายการ
- stack และ queue ทั้งคู่จัดเก็บลำดับรายการ, แต่ต่างกันที่ รายการไหนจะถูกนำออกก่อน
- Stack เป็น LIFO: Last In, First Out — เหมือนกองจาน
- Queue เป็น FIFO: First In, First Out —<input排队คน
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.
Stack เป็น LIFO
- push เพิ่มรายการบนสุด pop ลบและคืนค่ารายการ top peek มองเห็น topโดยไม่ลบออก
- รายการสุดท้ายที่คุณ push คือรายการแรกที่คุณ pop
- เราจัดเก็บรายการใน array
dataและ indextopนับจำนวนที่มีอยู่
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 ที่ใช้ array รองรับ
- ด้วย
topเป็นจำนวน, รายการ top อยู่ที่data[top - 1] - push: เขียนที่
data[top], แล้วtop++. pop:top--, แล้วคืนค่าdata[top] - (สำหรับงานเหล่านี้ array มีขนาดใหญ่พอ; คุณไม่จำเป็นต้องตรวจสอบ "เต็ม")
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).
Queue เป็น FIFO
- enqueue เพิ่มรายการที่ ท้าย dequeue ลบและคืนค่ารายการที่ หน้า
- รายการแรกที่คุณ enqueue คือรายการแรกที่คุณ dequeue
- เรารักษา two indexes:
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".)
Queue ที่ใช้ array รองรับ
- enqueue: เขียนที่
data[back], แล้วback++. dequeue: อ่านdata[front], แล้วfront++, และคืนค่ามัน frontไล่ตามbackเมื่อรายการเข้ามาและออกไป- (สำหรับงานเหล่านี้ array มีขนาดใหญ่พอ; คุณไม่จำเป็นต้อง 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.
ข้อผิดพลาดที่พบบ่อย
- Stack เป็น last-in-first-out; Queue เป็น first-in-first-out
- ตรวจสอบโครงสร้างว่าไม่ใช่ empty ก่อนที่จะ 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.
ลองดูเลย
- structs
StackและQueueถูกกำหนดไว้ใน starter ใช้s->top,q->front, และq->back - อย่า เขียน
main— ตัวตรวจสอบจะจัดเตรียมให้
Stacks and queues · Stacks และ queues
A stack is LIFO; a queue is FIFO. Step through the operations. · Stack เป็น LIFO; Queue เป็น 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. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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. · struct Stack ให้มา เติม int peek(const Stack *s) เพื่อส่งค่าบนสุด โดยไม่ ลบออก สมมติว่า Stack ไม่ว่าง ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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. · คลิก Run เพื่อดูผลลัพธ์ที่นี่