RootishArrayStack: A Space-Efficient Array Stack

Discover the need of RootishArrayStack.

The data structures that store their data in one or two arrays and they avoid resizing these arrays too often, the arrays frequently are not very full. For example, immediately after a resize() operation on an ArrayStack, the backing array is only half full. Even worse, there are times when only one-third of it contains data.

Visual demonstration

A sequence of add(i, x) and remove(i) operations on a RootishArrayStack is illustrated below. Arrows denote elements being copied.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy