Page 16 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 1: Data Structures

Stacks are also called last-in first-out (LIFO) lists. Other names used for stacks are “piles” and Notes
“push-down” lists. Stack has many important applications in computer science.

1.3.3 Queues

A queue, also called a first-in-first-out (FIFO) system, is a linear list in which deletions can take
place only at one end of the list, the “front” of the list, and insertions can take place only at the
other end of the list, the “rear” of the list. The features of a Queue are similar to the features of
any queue of customers at a counter, at a bus stop, at railway reservation counter, etc. A queue
can be implemented using arrays or linked lists. A queue can be represented as a circular queue.
This representation saves space when compared to the linear queue. Finally, there are special
cases of queues called Dequeues which allow insertion and deletion of elements at both the end.

Figure 1.2: A Queue of People Waiting at a Bus Stop

BUS
STOP

Source: http://www.csbdu.in/econtent/DataStructures/Unit1-DS.pdf

Task Analyze various applications of queues.

1.3.4 Linked List

A linked list, or one-way list, is a linear collection of data elements, called nodes, where the
linear order is given by means of pointers. That is, each node is divided into two parts: the first
part contains the information of the element, and the second part, called the link field or next
pointer field, contains the address of the next node in the list.

Figure 1.3 is a schematic diagram of a linked list with 6 nodes. Each node is pictured with two
parts.
Figure 1.3: Linked List with 6 Nodes

Source: http://www.csbdu.in/econtent/DataStructures/Unit1-DS.pdf

LOVELY PROFESSIONAL UNIVERSITY 9