CS 121 Lecture 80: Linear Data Structures, Queues, & Stacks
5 Jul 2018
School
Department
Course
Professor
Linear Data Structures:
In addition to lists, some data structures have become classic in that they
represent important generic situations that commonly occur in computing.
Like lists, a queue & a stack are linear data structures.
oThe data they represent is organized in a linear fashion.
Queue: is similar to a list except that it has restrictions on the way you put
items in & take items out.
oFirst-In, First-Out (FIFO) Processing: first item put in the list is the first
item that comes out of the list.
EX: Any waiting line is a queue. Think about a line of people waiting
for a teller at a bank. A customer enters the queue at the back & moves
forward as earlier customers are serviced. Eventually, each customer
comes to the front of the queue to be processed.
The processing of a queue is conceptual.
We may speak in terms of ppl moving forward until they reach the
front of the queue.
Reality might be that the front of the queue moves as elements
come off.
We’re not concerned at this point w/ whether queue of
customers moves toward the teller, or remains stationary as
teller moves when customers are serviced.
A queue data structure typically has the following operations:
Enqueue: adds an item to the rear of the queue.
Dequeue: removes an item from the front of the queue.
Empty: returns true if the queue is empty.
Stacks: elements go on & come off at the same end.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
In addition to lists, some data structures have become classic in that they represent important generic situations that commonly occur in computing. Like lists, a queue & a stack are linear data structures: the data they represent is organized in a linear fashion. Ex: any waiting line is a queue. Think about a line of people waiting for a teller at a bank. A customer enters the queue at the back & moves forward as earlier customers are serviced. Eventually, each customer comes to the front of the queue to be processed. The processing of a queue is conceptual. We may speak in terms of ppl moving forward until they reach the front of the queue. Reality might be that the front of the queue moves as elements come off. We"re not concerned at this point w/ whether queue of customers moves toward the teller, or remains stationary as teller moves when customers are serviced.
