Page 324 - Introduction to Microcontrollers Architecture, Programming, and Interfacing of The Motorola 68HC12

10.3 Sequential Data Structures 301

Figure 10.5. Deque Data Structure

bottom elements can be accessed. Pushing an element onto the top (or bottom) makes
the old top (or bottom) the next-to-top (or next-to-bottom) element and the element
pushed becomes the new top (or bottom) element. Popping or pulling an element reads
the top (or bottom) element, removes it from the deque, and makes the former next-to-
top (or next-to-bottom) element the new top (or bottom) element (see Figure 10.5). You
start at some point in memory and allow bytes to be pushed or pulled from the bottom
as well as the top.
In C, two pointers can be used, as a pointer was used in the string data structure, or
else indexes can be used to read or write on the top or bottom of a deque, and a counter is
used to detect overflow or underflow. We use indexes in this example and invite the
reader to use pointers in an exercise at the end of the chapter.
The deque buffer is implemented as a 50-element global vector deque, and the
indexes as global unsigned chars top and hot initialized to the first element of the
deque, as in the C declaration
unsigned char deque [50], size,error, top, bot;

Figure 10.6. Buffer for a Deque Wrapped on a Drum