Generalized queue. Implement a class that supports the following API, which generalizes bo...

Generalized queue. Implement a class that supports the following API, which generalizes both a queue and a stack by supporting removal of the ith most recently inserted item:

First, develop an implementation that uses a resizing array, and then develop one that uses a linked list. (See Exercise 4.4.57 for a more efficient implementation that uses a binary search tree.)

EXERCISE 4.4.57

Generalized queue. Implement a class that supports the following API, which generalizes both a queue and a stack by supporting removal of the i th least recently inserted item:

Use a BST that associates the kth item inserted into the data structure with the key k and maintains in each node the total number of nodes in the subtree rooted at that node. To find the i th least recently inserted item, search for the i th smallest key in the BST.