Czy istnieje istniejąca struktura danych o ustalonym rozmiarze, która wypchnie najstarszy / ostatni element, jeśli wstawiony zostanie nowy element?

Szukam struktury danych, która wypchnie jej najstarszy / ostatni element, jeśli wstawiony zostanie nowy element. Na przykład niech Dreprezentuje strukturę. Dzawiera 3 elementy Number Dwartości domyślnych tego typu będą inicjowane do 1, 2i 3.

D = [1, 2, 3]

$D = [1, 2, 3]$

Jeśli Numberto zawiera wartość 5jest włożona D, 3zostanie wypchnięty, natomiast 1i 2są przesunięte w prawo.

D = [5, 1, 2]

$D = [5, 1, 2]$

Pierwszą rzeczą, która przychodzi na myśl, będzie tablica, ale definicja nie obejmuje zachowania polegającego na wypychaniu.

data-structures arrays queues

— Greg M.
źródło

Cóż, nie ma wbudowanej struktury danych, ale można to łatwo zaimplementować za pomocą podwójnie połączonej listy, prawda?

— Nie znaleziono użytkownika

Co z użyciem opakowania dziedziczącego z kolejki? Następnie dodajesz metodę void push_replace(T val) { pop(); push(val); }.

— Francesco Dondi

@FrancescoDondi powinien być prawdopodobnieT push_replace(T val) { T old = pop(); push(val); return old; }

— valbaca

Zdecydowanie jest teraz: po prostu nieformalnie to zdefiniowałeś; być może powinieneś zapytać, czy jest dobrze znany, ma ogólnie uzgodniony interfejs i czy są dostępne implementacje (nie to, że ostatni to świetny problem).

— PJTraill

@valbaca Myślę o C ++, w którym pop()nic nie zwraca ze względu na problemy z rozwijaniem stosu w przypadku wyjątków kopiowania złożonego obiektu, więc powinieneś użyć go front()wcześniej, jeśli potrzebujesz go przed odrzuceniem. Ale oczywiście, jeśli nie przejmujesz się wyjątkami, Twoja droga może być lepsza.

— Francesco Dondi

Kolejki o stałym rozmiarze są często implementowane przy użyciu tego, co niektórzy nazywają buforami okrągłymi . Jeśli usuniesz ochronę przed jej wypełnieniem, uzyskasz pożądane zachowanie.

Oczywiście w tablicy nie nastąpi żadne rzeczywiste wypychanie - byłoby to zbyt drogie - ale będzie to wyglądać z zewnątrz.

— Raphael
źródło

Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .

— Raphael