Ngăn xếp và hàng đợi (dựa trên mảng)
Hai cách lưu trữ các mục
- Một ngăn xếp (stack) và một hàng đợi (queue) đều chứa một dòng các mục, nhưng chúng khác nhau ở mục nào sẽ ra trước.
- Ngăn xếp là LIFO: Vào sau, Ra trước — giống như đống đĩa.
- Hàng đợi là FIFO: Vào trước, Ra trước — giống như hàng người.
Một ngăn xếp tuân theo nguyên tắc LIFO
- push thêm một mục lên trên. pop lấy và trả về mục trên cùng. peek xem mục trên cùng mà không lấy nó ra.
- Mục cuối cùng bạn push chính là mục đầu tiên bạn pop.
- Chúng ta lưu các mục trong mảng
datavà chỉ sốtopđếm số lượng đang có.
Ngăn xếp dựa trên mảng
- Với
toplà số lượng, mục trên cùng nằm ở vị trídata[top - 1]. - push: ghi vào
data[top], sau đó tăngtop++. pop: giảmtop--, sau đó trả vềdata[top]. - (Đối với các bài tập này, mảng đủ lớn; bạn không cần kiểm tra "đầy").
Một hàng đợi tuân theo nguyên tắc FIFO
- enqueue thêm một mục vào cuối. dequeue lấy và trả về mục ở đầu.
- Mục đầu tiên bạn enqueue chính là mục đầu tiên bạn dequeue.
- Chúng tôi giữ hai chỉ số:
front(tiếp theo sẽ rời đi) vàback(ngăn trống tiếp theo).
Hàng đợi dựa trên mảng
- enqueue: ghi vào
data[back], sau đó tăngback++. dequeue: đọcdata[front], sau đó tăngfront++, và trả về nó. frontchạy đuổibackkhi các mục ra vào.- (Đối với các bài tập này, mảng đủ lớn; bạn không cần vòng lại hoặc kiểm tra "rỗng").
Lỗi thường gặp
- Ngăn xếp là vào sau ra trước; hàng đợi là vào trước ra trước.
- Kiểm tra cấu trúc không rỗng trước khi thực hiện pop hoặc dequeue.
Bây giờ bạn thử
- Các structs
StackvàQueueđược cung cấp trong file khởi tạo. Sử dụngs->top,q->front, vàq->back. - Không viết một
main— trình kiểm tra sẽ cung cấp cho bạn một cái.
Ngăn xếp và hàng đợi
Ngăn xếp là LIFO; hàng đợi là FIFO. Bước qua các thao tác.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
The Stack struct (with data and a count top) is given. Hoàn thành void push(Stack *s, int v) và int pop(Stack *s) để ngăn xếp hoạt động theo LIFO. Không viết một main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
The Stack struct is given. Hoàn thành int peek(const Stack *s) để trả về phần tử trên cùng mà không xóa nó. Giả sử ngăn xếp không rỗng. Không viết một main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
The Queue struct (with data, front, and back) is given. Hoàn thành void enqueue(Queue *q, int v) và int dequeue(Queue *q) để hàng đợi hoạt động theo FIFO. Không viết một main.
Nhấn Chạy để xem kết quả ở đây.