c++

Web browsers commonly allow you to navigate through a "history" of web pages which have previously been visited. The mechanism is somewhat like a stack, in that the most recently visited pages are at the top of the history and revisited when the "back" button is pressed.

However, the history does not really have infinite capacity. In reality, there may exist a fixed limit on the size of the history. The issue arises as to what should happen when the capacity is exhausted and a new item is pushed onto the stack. One possibility is to throw an exception. But this is not how a Web browser behaves. If it only has room to save 50 pages in its history and yet you visit more pages, it will make room in the history for a new page by throwing away the page which is on the very bottom of the history (i.e., the least recently visited page). The formal Stack interface does not help, as it gives us no way to directly access or remove the object on the bottom of the stack.

In this assignment, we define a new ADT which we call a BoundedStack. The interface for a BoundedStack is very similar to the interface given for a Stack. However in the case when the capacity is exhausted, a call to push will result in the placement of the new page at the expense of the loss of the least recently accessed page.

For this assignment, you will be required to give two different classes, as described below.

BoundedStackA

Use a linked list of a fixed size of 50 nodes. The node can be implemented as a struct or class and can be embedded or independent of the BoundedStackA class. The push function should add new items to one end of the list, and the pop function should remove items from the same end of the list, which will be the top of the stack. However, when adding a node with the push function, if the list is full, remove the oldest node to make room for the new node. This means that you will need to remove a node from the other end of the list, which will be the bottom of the stack.

BoundedStackB

A second way to implement a BoundedStack is to use an array viewed in a circular manner. You can mark the "top" of the circular stack with an extra integer variable which is an index into your array. By also keeping explicit count of the current size of the stack, you can effectively identify the "bottom" of the stack as well, when needed. With a bit of care, you can more efficiently handle pushes, even those involving overflow.

Grading Criteria:

You have some flexibility in the way you design your code for this lab. I have a few requirements for the structure of your program, but your program may do more than what is required below to meet the functional requirements. Your program should meet the functional requirements and include a minimum of the following:

Use the input file weblog_unique.url as input data.

Create two stack classes: BoundedStackA and BoundedStackB as described above. Note: Do not use an STL container class for this lab.

Create functions for your implementations that includes at a minimum the following functions.

A push function for adding an item to the top of the stack.

A pop function for removing an item from the top of the stack.

A peek function for displaying the item at the top of the stack.

A client program that adds items from the input file to the BoundedStackA and BoundedStackB and properly handles overflow for each. The client program should display and pop the entire contents of the stack to demonstrate its contents after adding the above listed input file (note: this will empty the stack completely).

BoundedStackA and BoundedStackB can be template classes (optional).