Projects on Stacks & Queues

What should your Stacks and Queues Contain?


For each of the programming assignments that follow, you must first construct a class which has a few data elements inside of it and initialize them before putting them inside your Stacks and Queues.


If you do not want to be original, you can simply create a class

called Dog with the following structure:


public class Dog {


String name;

int age;

double weight_in_pounds;


}


To demonstrate that your program is working, you need to create several objects of this type, initialize them (i.e. make several Dogs), add them to the data structure you have built. As you add and remove Dogs (or whatever datatype you have selected) to the Stacks and Queues you build, you should periodically print the contents of the data structure to prove to your instructor that the code you have built is, indeed, working.


You should override the class' toString() method to help you print out the items.

Project #1: Stacks Using Lists


You must implement a stack (that holds the datatype you defined earlier) in java using java's built in List datatype as the underlying data structure. (If you do not understand what this means, ask your instructor).


As is true of all stacks, you must implement the following interface/functionality:


Stack<item-type> Operations


push(new-item:item-type)Adds an item onto the stack.



top():item-typeReturns the last item pushed onto the stack.



pop()Removes the most-recently-pushed item from the stack.


is-empty():BooleanTrue if no more items can be popped and there is no top item.



is-full():BooleanTrue if no more items can be pushed.



get-size():IntegerReturns the number of elements on the stack.


All operations except get-size() must be performed in  time.


But get-size() can run in at worst 

Project #2: Stacks Using Array


You must implement a stack (that holds the datatype you defined earlier) in java using a java array (not an ArrayList!)  as the underlying data structure. (If you do not understand what this means, ask your instructor).


As is true of all stacks, you must implement the following interface/functionality:


Stack<item-type> Operations


push(new-item:item-type)Adds an item onto the stack.



top():item-typeReturns the last item pushed onto the stack.



pop()Removes the most-recently-pushed item from the stack.



is-empty():BooleanTrue if no more items can be popped and there is no top item.



is-full():BooleanTrue if no more items can be pushed.



get-size():IntegerReturns the number of elements on the stack.


All operations except get-size() must be performed in  time.


But get-size() can run in at worst 

Project #3: Circular Queue Using Lists


You must implement a circular queue (that holds the datatype you defined earlier) in java using java's built in List datatype as the underlying data structure. (If you do not understand what this means, ask your instructor).


As is true of all queues, you must implement the following interface/functionality:


Queue<item-type> Operations


enqueue(new-item:item-type) Adds an item onto the end of the queue.

front():item-type Returns the item at the front of the queue.

dequeue() Removes the item from the front of the queue.

is-empty():Boolean True if no more items can be dequeued and there is no front item.

is-full():Boolean True if no more items can be enqueued.

get-size():Integer Returns the number of elements in the queue.

All operations except get-size() can be performed in  time.


get-size() runs in at worst 


Building a circular queue will require some additional thought on your part. You should research "circular queues" on the internet before proceeding with your design.

Project #4: Circular Queue Using Array


You must implement a queue(that holds the datatype you defined earlier) in java using a java array (not an ArrayList!)  as the underlying data structure. (If you do not understand what this means, ask your instructor).


As is true of all stacks, you must implement the following interface/functionality:



Queue<item-type> Operations



enqueue(new-item:item-type) Adds an item onto the end of the queue.

front():item-type Returns the item at the front of the queue.

dequeue() Removes the item from the front of the queue.

is-empty():Boolean True if no more items can be dequeued and there is no front item.

is-full():Boolean True if no more items can be enqueued.

get-size():Integer Returns the number of elements in the queue.

All operations except get-size() can be performed in  time.


get-size() runs in at worst 


Building a circular queue will require some additional thought on your part. You should research "circular queues" on the internet before proceeding with your design.

1 point
I have completed the project(s) for this lesson and have demonstrated them to my instructor.


Project #5: Non-Recursive Backtracking Using a Stack to Solve a Maze

Create a program to solve mazes as described in the Stacks and Queues Chapter.

The Tester class can be found here.