21
$\begingroup$

I'm looking for a data structure that will push its oldest/last element out if a new element is inserted. For example, let D represent the structure. D contains 3 elements of the type Number D's default values will be initialized to 1, 2 and 3.

$$D = [1, 2, 3]$$

If a Number that contains the value 5 is inserted into D, 3 will be pushed out, while 1 and 2 are shifted right.

$$D = [5, 1, 2]$$

The first thing that comes to mind would be an array, but the definition does not include the pushing behavior.

Improve this question
$\endgroup$
5
  • $\begingroup$ Well there is no in-built data structure but it is simple to implement using a Doubly linked list linked list right? $\endgroup$
    – User Not Found
    Jul 12, 2017 at 4:53
  • 1
    $\begingroup$ What about using a wrapper inheriting from a queue? Then you add the method void push_replace(T val) { pop(); push(val); }. $\endgroup$
    – Francesco Dondi
    Jul 12, 2017 at 12:05
  • $\begingroup$ @FrancescoDondi should probably be T push_replace(T val) { T old = pop(); push(val); return old; } $\endgroup$
    – valbaca
    Jul 12, 2017 at 18:52
  • 1
    $\begingroup$ There definitely is now: you just informally defined it; perhaps you should ask if it is well-known, has a generally agreed interface and whether implementations are available (not that the last is a great issue). $\endgroup$
    – PJTraill
    Jul 12, 2017 at 21:41
  • $\begingroup$ @valbaca I'm thinking of C++ where pop() returns nothing due to problems with stack unwinding in case of exceptions copying out a complex object, so you're supposed to use front() before if you need it before discarding. But sure, if you don't care about exceptions your way can be better. $\endgroup$
    – Francesco Dondi
    Jul 13, 2017 at 8:06

1 Answer 1

Reset to default
44
$\begingroup$

Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour.

Of course, no actual pushing will happen in the array -- that would be too expensive -- but it will look like it from the outside.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Raphael ♦
    Jul 12, 2017 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.