Tại sao lớp Stack (không chung) được triển khai như một bộ đệm tròn? (và điều đó có nghĩa là chính xác)?

Question

Trạng thái lớp không phổ biến Stack "Ngăn xếp được triển khai dưới dạng bộ đệm tròn".

Tôi không hiểu việc áp dụng bộ đệm tròn vào trường hợp sử dụng Ngăn xếp. Tôi cũng không hiểu cách ngăn xếp có thể được triển khai như bộ đệm tròn.

Wikipedia nói điều này:

Thuộc tính hữu ích của một bộ đệm tròn là nó không cần phải có yếu tố của nó xáo trộn xung quanh khi một được tiêu thụ. (Nếu một bộ đệm không tròn được sử dụng thì nó sẽ là cần thiết để thay đổi tất cả các yếu tố khi một được tiêu thụ.) Nói cách khác, bộ đệm tròn rất thích hợp như một bộ đệm FIFO trong khi một bộ đệm tiêu chuẩn, không tròn rất phù hợp như một bộ đệm LIFO.

Đệm tròn làm cho chiến lược triển khai tốt cho hàng đợi có kích thước tối đa cố định.

Vậy ... ngăn xếp được triển khai như bộ đệm tròn và tại sao?

Answer 1

Tôi nghi ngờ đó là lỗi sao chép/dán/chỉnh sửa trong tài liệu; nhìn vào phản xạ, nó là không được triển khai dưới dạng bộ đệm tròn; ví dụ push là (sau khi mã thay đổi kích thước) về cơ bản:

this._array[this._size++] = obj; 

ú là:

return this._array[this._size - 1]; 

và pop là:

object value = this._array[--this._size]; 
this._array[this._size] = null; 
return value; 

Lưu ý nó không sử dụng bất kỳ loại bù đắp/wrap-around - vì vậy nó là không thực sự sử dụng bộ đệm tròn. Bản năng của bạn có vẻ đúng, nhưng tài liệu có vẻ sai.