Lecture Preview: Arrays and Implementing ADTs

(Suggested book reading: Programming Abstractions in C++, 11.2 - 11.3, 12.1, 12.3, 14.1, 14.4)

We have used several collections so far from the Stanford libraries, such as Vector, Stack, Queue, Set, Map, and so on. Today we will explore how collection classes are implemented. We will implement a stack of integers using an array internally, which we will call ArrayStack.

Inside a stack is an array storing the elements you have added. Typically the array is larger than the data added so far, so that it has some extra slots in which to put new elements later. We call this an unfilled array.

If you execute the following code: 

ArrayStack stack;
stack.push(42);
stack.push(-5);
stack.push(17);

The state inside the array looks like this:

index 0 1 2 3 4 5 6 7 8 9
value 42 -5 17 0 0 0 0 0 0 0
size 3 capacity 10

To write our own implementation of a stack, we must learn about how to use arrays in C++. C++ arrays are a bit cumbersome to use and require unusual syntax, which is why we have avoided them thus far. Here is a brief example of constructing an array and storing data in some of its elements: 

int* a = new int[10];
a[0] = 42;
a[1] = 17;
a[9] = 90210;

The unusual use of a * character above is related to how C++ manages memory using a feature called pointers. We will learn about this feature in detail later.

This document and its content are copyright © Marty Stepp and Julie Zelenski, 2019. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.