Question

For each of the following situations, which of the following ADTs would be most appropriate, and explain (1) Queue ADT; (2) Stack ADT; (3) Ranked or Positional Sequence ADT; (4) None of these.

a. The customers at the deli counter who take numbers to mark their turn.

b. An alphabetic list of names.

c. Integers that need to be sorted.

d. Execution environments of a recursive method.

e. The items on a cash register tape.

f. A word processor that allows you to correct typing errors by using the backspace key.

g. A program that uses recursion.

h. A list of ideas in chronological order.

i. Airplanes that stack above a busy airport waiting to land.

j. People who are put on hold when the call an airline to make reservations.

k. An employer who fires the most recently hired person.

Answer 1

First of all let us understand what these three abstract data type means in general.

1)Stack ADT: This abstract data type uses the concept of LIFO,i.e Last In First Out policy and so In this data type the insertion and deletion happens from the last of the stack.

2)Queue ADT: This abstract data type uses the concept of FIFO,i.e First In First Out policy and so in this datatype the insertion of elements happens from the last of the queue and deletion happens from the front end.

3)Ranked or Positional ADT: In this abstract datatype the elements will be having an index.The first element would be having an index of 0 and adding more elements leads to more index in the array.And so if there are k elements then there would be k-1 indices.Elements can be added or deleted from anywhere from this datatype list. But when this happens the elements indices after the deleted element would be decremented by and 1 and so Or if there is an insertion happening the indices would be incremented by one.

Now looking at the questions provided:

a)The customers at the deli counter who take numbers to mark their turn:

This is an example for Queue data type. The customers who made their reservation first or took the ticket number first would be having their turn first .The customers who came last would be having their turn last.

b)An alphabetic list of names:

This is an example of Ranked or Positional Sequence ADT. Initially every names would be having indices based on their ascending sequence of alphabets in their names.But this list can change when new names have to be inserted .For example: If Abhay was the first name in this sequence having index 0, and a new student named Aarav has to be inserted in the list,now Aarav is the first element in the list having index 0 and the index of Abhay changes to 1.

c)Integers that needs to be sorted:

This is an example for Ranked or positional Sequence ADT,As the integers having values less would be having low index values and the integers having greater values large index values.

d)Execution enviroments of a recursive method:

This is an example for Stack ADT, recursive methods executes in a form of LIFO mannner which is a clear indication of Stack ADT.

e)The items on a cash register tape:

The elements are inserted to cash register tape in a manner of First come first serve. And so it is an example for Queue ADT.

f) A word processor that allows you to correct typing errors by using the backspace key.

None of the ADTS matches for this . And so answer would be None of these.

g) A program that uses recursion.

This is an example for stack ADT, recursive methods executes in a form of LIFO mannner which is a clear indication of Stack ADT.

h) A list of ideas in chronological order.:

This is an example for Stack ADT,as ideas are piled up in in a chronological manner i.e new ideas are added to the top .

i) Airplanes that stack above a busy airport waiting to land.

This is an example for Queue ADT as each aeroplanes would be given a certain time for landing and the aeroplanes having time of landing first would be landing first .

But in the case of emergency landing and all these three ADTs doesnt stand for this case .

j) People who are put on hold when the call an airline to make reservations.

This is a case of Queue ADT as the people who call first would be attended first to make reservations and others would have to wait for their chance.

k) An employer who fires the most recently hired person.

This is an example for stack ADT as the employee is fired in the basis of Last one First out manner which is a clear indication for stack ADT.

Hope this helps!!!