Lists, Stacks and Queues
This tutorial covers the programming of lists and the specialised forms of lists that are known as stacks and queues. A list is an ordered collection of data items. A stack is a LIFO (last in first out) data structure. At any instant, the only data item that can be removed from the stack is the most recent item to have been added. A queue is a data structure in which data items are added only at the rear of the list and removed only from the head. It is a FIFO (first in first out) data structure.
You can use lists, stacks and queues to contain either simple data types (such as integer, real, string and char) or records. There are several ways to implement them, and will probably find it easiest to code them in arrays. For a list, you may be content to use deletion, insertion and sorting methods that move the data items within the arrays. These methods are effective for the data sets usually processed in student projects, but they are inefficient and inappropriate when many large records need to be manipulated quickly. The alternative is to link data items with pointers (addresses), so that deletions, insertions and sorting can be effected by changing the linking pointers without moving the data. The resulting linked list is defined as a dynamic data structure used to hold a sequence. This tutorial includes some programs that use arrays and others that use pointers. Within these two general methods there is plenty of scope for code variations, and alternative possibilities will be suggested.
Follow these links to demonstration programs, and be warned that linked lists are challenging.