CS1102C Miniature 5

What are lists, stacks and queues?

A list is a generic term which simply means an ordered collection of items. Here, items can include integers, floating point numbers, strings, objects and so on. There are various kinds of lists, including linked lists, tailed linked lists, vectors, and so on. Often, an array is also considered as a kind of list. Do know the differences between the different kinds of lists.

For stacks, imagine a stack of plates in a restaurant. You always place a plate on the top of the stack, and you always remove the plate from the top of the stack. People normally don't try to put a plate at the bottom of the stack, for example. So one observes that the first plate that is put into the stack of plates is also the last stack to be taken out. Hence, stacks have a first-in-last-out, or FILO property. A synonym of FILO is last-in-first-out, or LIFO. For historical reasons, the insertion of an item into a stack is known as push, and the removal of an item into a stack is known as pop.

For queues, think of people queueing at the canteen or at a cashier. People will join a queue at the back of the queue, and people at the front of the queue gets served first. To make things explicit, people who joined in the queue first will get to be served first. Hence, a queue is a first-in-first-out structure, abbreviated as FIFO. Items are always added to the back end of the queue, and removed from the front end of the queue.

For both stacks and queues, their main operations are insertion and removal of items, but it would be very useful if there is some way to tell whether they are empty, and what is the next item to be removed. Hence the inclusion of the other operations.

Often, stacks and queues are implemented using some variant of lists. Normally, a simple linked list suffices for the implementation of a stack, while a tailed linked list is suitable for the implementation of a queue.

Back to Index