Important Short Questions and Answers: Linear Data Structures - Stacks, Queues

1. Write down the algorithm for solving Towers of Hanoi problem?

Push parameters and return address on stack.

If the stopping value has been reached then pop the stack to return to previous level else move all except the final disc from starting to intermediate needle.

Move final discs from start to destination needle.

Move remaining discs from intermediate to destination needle.

Return to previous level by popping stack.

2. What is a Stack ?

A stack is a non-primitive linear data structure and is an ordered collection of homogeneous data elements.The other name of stack is Last-in -First-out list.

One of the most useful concepts and frequently used data structure of variable size for problem solving is the stack.

3. What are the two operations of Stack?

PUSH

POP

4. What is a Queue ?

A Queue is an ordered collection of items from which items may be deleted at one end called the front of the queue and into which tems may be inserted at the other end called rear of the queue.Queue is called as First –in-First-Out(FIFO).

5. What is a Priority Queue?

Priority queue is a data structure in which the intrinsic ordering of the elements does determine the results of its basic operations. Ascending and Descending priority queue are the two types of Priority queue.

6. What are the different ways to implement list?

Simple array implementation of list

Linked list implementation of list

cursor implementation of list

7. What are the postfix and prefix forms of the expression?

A+B*(C-D)/(P-R)

Postfix form: ABCD-*PR-/+

Prefix form: +A/*B-CD-PR

8. Explain the usage of stack in recursive algorithm implementation?

In recursive algorithms, stack data structures is used to store the return address when a recursive call is encountered and also to store the values of all the parameters essential to the current state of the procedure.

9. Write down the operations that can be done with queue data structure?

Queue is a first - in -first out list. The operations that can be done with queue are insert and remove.

10. What is a circular queue?

The queue, which wraps around upon reaching the end of the array is called as circular

queue.

11.Give few examples for data structures?

Stacks

Queue

Linked list

Trees

Graphs

12.     List out Applications of queue

  Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.

Computer systems must often provide a “h processes, two programs, or even two systems. This holding area is usually called a “buffer”       and   is   often   implemented as a queue.

13. How do you test for an empty queue?

To test for an empty queue, we have to check whether READ=HEAD where REAR is a pointer pointing to the last node in a queue and HEAD is a pointer that pointer to the dummy header.

In the case of array implementation of queue, the condition to be checked for an empty queue is READ<FRONT.

14.What are applications of stack?

Conversion of expression

  Evaluation of expression

  Parentheses matching

  Recursion

14.            Define recursion?

It is a technique and it can be defined as any function that calls itself is called recursion. There are some applications which are suitable for only recursion such as, tower of Hanoi, binary tree traversals etc, can be implementing very easily and efficiently.

16.What are types of Queues?

Simple queue (ordinary queue)

  Circular queue

  Double ended queue

  Priority queue