*THIS PROGRAM SHOULD BE IN C++ AND THE LIBRARY should not be used.

Write a stack class implemented with a linked list, with the following functionality:

1. Constructor

2. Destructor

3. Push

4. Pop

5. Stack_top (wont need in this particular main program, but provide it)

6. Is_Empty

Then, write a program to simulate a mouse in a maze. Note: there are problems if the maze contains a cycle. Youll read a maze from a file, and it wont contain a cycle.

Notes:

1. Read data from a file named input.txt

2. Store the data into a two-dimensional array with 11 rows and 11 columns, completely filling one row before starting the next

3. Concerning the data:

a. 0 represents a wall, the mouse cannot step here

b. 1 represents a space where the mouse could step

4. The mouse will start at location 5, 0 (on the left edge of the maze)

5. The mouses first step will be to location 5, 1

6. The mouse succeeds when he reaches any location on the outside edge

A node will need to store the following data:

1. row number

2. column number

3. previous row number

4. previous column number

The mouse may never step back onto the space he just came from, unless he hits a dead end and backtracks following the rules below.

Each time the mouse takes a step:

1. If it is on the outside edge, he is free output final message including the path he took (without listing any backtracking need the stack for this)

2. If there is only one way he can make his next step, make the step

a. Display the location

b. Push the location onto the stack (use values 0 and 0 for previous row number and previous column number)

3. If there is more than one valid place for his next step, choose one, and:

a. Push all but chosen one onto the stack (use current location as the previous row and column numbers)

b. Make the step onto chosen location (follow rules from step 2)

4. If he hits a dead end:

a. Pop (displaying where he is stepping while backtracking) until you pop a record with a nonzero previous row or column number

b. Make the step onto the location last popped (follow rules from step 2)

There are two items of output from this program, both to the screen:

1. A list of everywhere he steps while traversing the maze (10 locations per line, spaced nicely)

2. The path he took without listing the backtracking (10 locations per line, spaced nicely)

Diagonal moves are not allowed. The mouse may only move:

North, South, East, or West

Keep in mind the following:

Name your source files stack.h, stack.cpp, and main.cpp