Assignment1: Lists-Stacks-Queues

A queue is an abstract data type where elements are stored in order of insertion and removed in the same order. Because the first element that is inserted is the first to be removed, it is often referred to as First-in First-out collection.

TwoStackQueue

You have seen in class, that a queue could be implemented using the java.util.LinkedList class or the MyLinkedList class. In this assignment, you will implement the queue using two stacks. One stack is used to enqueue elements, while the other is used to dequeue elements. That is, when an element is added to the queue it is pushed on the in stack. When an element is removed from the queue it is popped off the out stack. If the out stack is empty, the contents of the in stack is transferred to the out stack.

What to do?

-First, you need to implement the MyQueueI> interface as described below.

-Then you create the class TwoStackQueue that implements the interface myQueue.

-Your class should include two constructors:

1. A default constructor TwoStackQueue() to create an empty Queue by creating two empty stacks. Make use of the java.util.Stack class or MyStack class implemented in class.

2. TwoStackQueue(List L) to create a Queue from a List (linkedList or ArrayList) by creating an empty out-stack and an in-stack filled with the List elements.

-Implement the methods of the TwoStackQueue class by implementing all the abstract methods declared in the MyQueueI interface (dequeue(), enqueue(E), isEmpty(), peek()).

-You can use the push() and pop() methods from the Stack class (or MyStack).

-In a main method, test your class thoroughly.

public interface MyQueueI

Interface to specify operations for a simple unbounded first-in-first-out (FIFO) queue.

Method Summary
public E	dequeue() Removes and returns the element at the front of this queue.
public void	enqueue(E element) Adds the specified element to the back of this queue.
public boolean	isEmpty() Returns true if this queue contains no elements.
public E	peek() Returns, but does not remove, the element at the front of this queue.

Coding: (Copy and Paste Source Code here)

public class UseTwoStackQueue {

public static void main(String[] args) {

List listString = new ArrayList();

listString.add("One");

listString.add("Two ");

listString.add("Three");

List linkedString = new LinkedList(listString);

linkedString.add("end of linked list");

TwoStackQueue Q1 = new TwoStackQueue();

TwoStackQueue Q2= new TwoStackQueue(listString);

TwoStackQueue Q3 = new TwoStackQueue(linkedString);

TwoStackQueueQ4 = new TwoStackQueue();

Q1.enqueue("First"); Q1.enqueue("Second"); Q1.enqueue("Third");

Q2.enqueue("Four");

System.out.println(" The element at the front of Q3" + Q3.peek());

Q4.enqueue(new Integer(200));Q4.enqueue(new Integer(100));

Q4.enqueue(new Integer(500)); Q4.enqueue(50);

System.out.println(" ******** Dequeue the Stack Q1");

while (!Q1.isEmpty()) System.out.print(" "+ Q1.dequeue());

System.out.println(" ******** The first element to dequeue in Q2");

System.out.print(" "+Q2.dequeue());

System.out.println(" ******** Dequeue the Stack Q3");

while (!Q3.isEmpty()) System.out.print(" "+ Q3.dequeue());

System.out.println(" ******** Dequeue the Stack Q4");

while (!Q4.isEmpty()) System.out.print(" "+ Q4.dequeue());

}

}

interface MyQueueI ..

// Complete and implement your interface here

class TwoStackQueue ..

// complete and implement your class here

queue dequeue0 enqueue front back