CP164 Study Guide - Final Guide: Array Data Type, Array Data Structure, Data Element
Notes - The Array-Based Stack
Implementation
There are a number of different approaches to implementing ADTs. These implementations
vary depending on the programming language used, and the capabilities of these languages.
We will use two different implementation styles: array-based and linked. We will begin
with an array-based stack and work with linked structures later in the course.
Many programming languages have built-in array data types. An array is an area of
memory that holds a series of consecutive data elements, with each data element accessible
through an index value. Arrays are of fixed length. Python does not have a array data type
built-in to its basic language set. A Python list is closest thing available, but such lists are
not of fixed length, nor do they require that all their elements be of the same type.
However, we will treat Python lists as though they are arrays for two reasons: the array
concept is extremely important in other languages; and it is easier to call a list data
structure written in Python an array-based list as opposed to a list-based list.
Thus our first implementation of the Stack ADT uses a Python list as the underlying means
of storing the Stack's data. We will wrap the Python list code with our own in order to meet
our ADT standards.
The top of the stack is the right-most inhabited element in the stack's array. As data is
pushed onto the top of the stack, the index of the right-most inhabited element increases;
as elements are removed, the index of the right-most inhabited element decreases. The size
of the stack at any given time is simply the number of array elements that contain values, or
right-most element index + 1. No array elements with an index smaller than that of the
right-most element can be left empty. A stack is empty if the array element with index 0 is
empty.
Document Summary
There are a number of different approaches to implementing adts. These implementations vary depending on the programming language used, and the capabilities of these languages. We will use two different implementation styles: array-based and linked. We will begin with an array-based stack and work with linked structures later in the course. Many programming languages have built-in array data types. An array is an area of memory that holds a series of consecutive data elements, with each data element accessible through an index value. Python does not have a array data type built-in to its basic language set. A python list is closest thing available, but such lists are not of fixed length, nor do they require that all their elements be of the same type. Thus our first implementation of the stack adt uses a python list as the underlying means of storing the stack"s data.
