Implementing Stacks and Queues

What is used to design and implement the Stack class?

An ArrayList

What is used to design and implement the Queue class?

A LinkedList

What is used to design and implement a Priority Queue?

A heap

What is a Stack?

A special type of list, where the elements are accessed, inserted, and deleted only from the end, called the top of the stack.

Why is an ArrayList used to implement a Stack rather than a LinkedList?

Since the insertion and deletion operations on a Stack are made only at the end of the Stack

In what two ways can the Stack class be designed?

Using inheritance - Define the Stack class by extending the ArrayList class

Using composition - Define an ArrayList as a data field in the Stack class

What is a Queue?

A special type of list, where the elements are inserted at the end (tail) of the queue, and are accessed and deleted from the beginning (head) of the queue.

Why is a LinkedList used to implement a Queue rather than an ArrayList?

Since deletions are made at the beginning of the List.

In what two ways can the Queue class be designed?

Using inheritance - Define the Queue class by extending the LinkedList class

Using composition - Define a LinkedList as a data field in the Queue class

Why is composition better for designing Stacks and Queues?

It enables you to define a complete new Stack class and Queue class without inheriting the unnecessary and inappropriate methods from the ArrayList and LinkedList

What is the difference between Queue and Priority Queue?

- A regular Queue is First-In-First-Out behavior

- In a Priority Queue, elements have an assigned priority. Elements with a higher priority are removed from the Queue first. Priority Queue has Largest-In, First-Out behavior.