Abstract Data Types Read pages 249 and 250 and answer the qu

Abstract Data Types Read pages 249 and 250 and answer the questions. Do not use direct quotes from the text, but make it clear that you have read the text to answer the questions.

Suppose the following data is made available to the algorithm on page 250: 1 2 3 4 5. What gets written by executing the algorithm?

249 8.3 Queues Viewing eration has no constraints; the entire LIFO the removal operation. a stack from this perspective is more abstract. The insertion op- behavior is specified through n item to the stack an ite not have the number of items on the stack. We do need opera The mental image of the cafeteria plates has left an imprint on the traditional names used for the insertion and removal operations. Adding is called Push; removing an item is called Pop. We Push m onto the stack, and we Pop an item off the stack. A stack does property of length, so there is no operation that returns the tions that determine whether a stack is IsEmpty, however, because trying to Pop an item wher hether a stack is IsEmpty, however, because trying to Pop an item when the stack is empty is an error. Here is an algorithm that reads in numbers and prints them in re- verse order using a stack. We have not colored the stack operations in red because they have already been implemented by someone else; they are ours to use. Because the more data is not relevant to our discussion, we leave it unexpanded here and in the following algorithms. WHILE (more data) Read value Push(myStack, value) WHILE (NOT IsEmpty(myStack) Pop(myStack, value) Write value Desk check this algorithm to convince yourself that the values are, in- deed, written in reverse order 8.3 Queues queue is an abstract structure in which items are entered at one end and removed from the other end. Accountants call this behavior FIFO wnich stands for \"first in, first out.\" This ADT sounds like a waiting line in which standsf a bank or supermarket. In situation. Insertions are or supermarket. Indeed, queues are used to simulate this type o ertions are made at the rear of the queue, and removals are made from the front of the queue. hahway of stating the accessing behavior of a queue is to say Another way t the item em removed is the item that has been in the queue the longest

Solution

Queues are data structures which represent a sequential storage of elements which may be contiguous or non contiguous. Queues are implemented using arrays to show contiguous implementation or linked Lists to show non contiguous implementation.

It has 2 operations, insertion and removal

Insertion is done from the end of the queue and removal is done from the beginning of the queue. These two ends are called rear and front respectively.

Before every insertion, queue is checked for completeness. If we reached the array size complete and still need to insert more elements, it is not possible and displays queue is full. Similarly, for removal, the queue is checked for emptiness. If the queue is empty, then removal operastion cannot be performed.

Representation of Queue for the data 1 2 3 4 5

The algorithm has two parts – for reading and for writing

while(more data)

                Read value

                Enque(myQueue, value)

myQueue after first insertion

1

After second insertion

1

2

After third insertion

1

2

3

After fourth insertion

1

2

3

4

After fifth insertion

1

2

3

4

5

Removal Part

while(NOT isEmpty(myQueue)

                Dequeue(myQueue, value)

                Write value

After first removal

2

3

4

5

After second removal

3

4

5

After third removal

4

5

After fourth removal

5

After fifth removal

1