Stacks and Queues

Our study of data types in computation so far has involved:

• primitive types, such as char, int, and double,
• compound types as provided by structs in C, and
• linear structures such as arrays and linked lists.

The pair of readings for today introduce two additional linear structures that further restrict the operations available. This notion of restriction is often useful for two orthogonal reasons:

1. We can ask questions about what kinds of problems can be solved (efficiently) with a restricted set of operations, which are often representative of actual physical substrates.
2. We can optimize our implementations to cater to the specific set of operations.

Our two readings for today are substantial, but we will return to them over the next several days as we concentrate on implications and implementations:

• Stacks
• Queues