Stacks and queues (array-backed) · ⁨Ngăn xếp và hàng đợi (dựa trên mảng)⁩

English

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.

Tiếng Việt

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.

English

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 data and an index top that counts how many are in.

Tiếng Việt

Ngăn xếp遵循 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 data và chỉ số top đếm số lượng đang có.

English

Array-backed stack

With top as the count, the top item is at data[top - 1].
push: write at data[top], then top++. pop: top--, then return data[top].
(For these tasks the array is big enough; you do not need to check for "full".)

Tiếng Việt

Ngăn xếp dựa trên mảng

Với top là số lượng, mục trên cùng nằm ở vị trí data[top - 1].
push: ghi vào data[top], sau đó tăng top++. pop: giảm top--, 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").

English

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) and back (next free slot).

Tiếng Việt

Hàng đợi遵循 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).

English

Array-backed queue

enqueue: write at data[back], then back++. dequeue: read data[front], then front++, and return it.
front chases back as items come and go.
(For these tasks the array is big enough; you do not need to wrap around or check for "empty".)

Tiếng Việt

Hàng đợi dựa trên mảng

enqueue: ghi vào data[back], sau đó tăng back++. dequeue: đọc data[front], sau đó tăng front++, và trả về nó.
front chạy đuổi back khi 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").

English

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.

Tiếng Việt

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.

English

Now you try

The Stack and Queue structs are given in the starter. Use s->top, q->front, and q->back.
Do not write a main — the checker provides one.

Tiếng Việt

Bây giờ bạn thử

Các structs Stack và Queue được cung cấp trong file khởi tạo. Sử dụng s->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.

Explore · ⁨Khám phá⁩

Stacks and queues · ⁨Ngăn xếp và hàng đợi⁩

A stack is LIFO; a queue is FIFO. Step through the operations. · ⁨Ngăn xếp là LIFO; hàng đợi là FIFO. Bước qua các thao tác.⁩

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. · ⁨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.⁩

typedef struct {
    int data[64];
    int top;
} Stack;

/* push and pop so the stack is LIFO. Do not write main(). */
void push(Stack *s, int v) {
    /* store v at data[top], then top++ */
}

int pop(Stack *s) {
    return 0;   /* top--, then return data[top] */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

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. · ⁨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.⁩

typedef struct {
    int data[64];
    int top;
} Stack;

/* Return the top item without removing it. Do not write main(). */
int peek(const Stack *s) {
    return 0;   /* the top item is at data[top - 1] */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

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. · ⁨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.⁩

typedef struct {
    int data[64];
    int front;
    int back;
} Queue;

/* enqueue and dequeue so the queue is FIFO. Do not write main(). */
void enqueue(Queue *q, int v) {
    /* store v at data[back], then back++ */
}

int dequeue(Queue *q) {
    return 0;   /* read data[front], then front++ */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Stacks and queues (array-backed) · ⁨Ngăn xếp và hàng đợi (dựa trên mảng)⁩

Two ways to hold items

Hai cách lưu trữ các mục

A stack is LIFO

Ngăn xếp遵循 LIFO

Array-backed stack

Ngăn xếp dựa trên mảng

A queue is FIFO

Hàng đợi遵循 FIFO

Array-backed queue

Hàng đợi dựa trên mảng

Common mistakes

Lỗi thường gặp

Now you try

Bây giờ bạn thử

Stacks and queues · ⁨Ngăn xếp và hàng đợi⁩

Handout · ⁨Tài liệu⁩

Log in or create account · ⁨Đăng nhập hoặc tạo tài khoản⁩

Your subject · ⁨Môn học của bạn⁩

All sections · ⁨Tất cả các mục⁩

Feedback & help · ⁨Phản hồi & hỗ trợ⁩