Question

Implement the instance method flip declared as follows (this is a Queue): /** * Reverses ("flips") {@code this}. * * @updates this * @ensures this = rev(#this) */ public void flip(); Rewrite flip, including the contract, so that it is a static method. http://web.cse.ohio-state.edu/software/common/doc/

Answer 1

Queue can be reversed with the help of another queue.

a.

Required method:

Program:

Sample output:

Code to copy:

import java.util.Iterator;

import components.queue.Queue;

import components.queue.Queue2;

public class QueueWithNewFlip<T> {

    /**

     * Representation of {@code this}.

     */

    private Queue<T> rep;

    QueueWithNewFlip() {

        this.createNewRep();

    }

    private void createNewRep() {

        this.rep = new Queue2<T>();

    }

    public void enqueue(T x) {

        assert x != null : "Violation of: x is not null";

        this.rep.enqueue(x);

    }

    public T dequeue() {

        assert this.rep.length() > 0 : "Violation of: this /= <>";

        return this.rep.dequeue();

    }

    /**

     * Reverses ("flips") {@code this}.

     *

     * @updates this

     * @ensures this = rev(#this)

     */

    public void flip() {

        // Create another queue

        Queue<T> tempq = new Queue2<T>();

        // Repeat until this queue have no elements

        while (this.rep.length() > 0) {

            // remove all elements from this queue one by one, except last

            // element and enqueue into this queue

            for (int i = 0; i < this.rep.length() - 1; i++) {

                this.rep.enqueue(this.rep.dequeue());

            }

            // enqueue the last element into temporary queue

            tempq.enqueue(this.rep.dequeue());

        }

        // again insert all the elements of temporary queue into this queue

        while (tempq.length() > 0) {

            this.rep.enqueue(tempq.dequeue());

        }

        // clear the temporary queue

        tempq.clear();

    }

    public static void main(String args[]) {

        QueueWithNewFlip<Integer> que = new QueueWithNewFlip<Integer>();

        que.enqueue(123);

        que.enqueue(234);

        que.enqueue(345);

        que.enqueue(456);

        // Print the queue before flip

        System.out.println("Before flip: ");

        Iterator<Integer> itrq1 = que.rep.iterator();

        while (itrq1.hasNext()) {

            System.out.println(itrq1.next());

        }

        // Call flip to reverse the queue

        que.flip();

        // Print the queue before flip

        System.out.println("After flip: ");

        Iterator<Integer> itrq2 = que.rep.iterator();

        while (itrq2.hasNext()) {

            System.out.println(itrq2.next());

        }

    }

}

b.

Required modified method:

Program:

Sample output:

Code to copy:

import java.util.Iterator;

import components.queue.Queue;

import components.queue.Queue2;

public class QueueWithNewFlip<T> {

    /**

     * Representation of {@code this}.

     */

    private Queue<T> rep;

    QueueWithNewFlip() {

        this.createNewRep();

    }

    private void createNewRep() {

        this.rep = new Queue2<T>();

    }

    public void enqueue(T x) {

        assert x != null : "Violation of: x is not null";

        this.rep.enqueue(x);

    }

    public T dequeue() {

        assert this.rep.length() > 0 : "Violation of: this /= <>";

        return this.rep.dequeue();

    }

    /**

     * Reverses ("flips") {@code this}.

     *

     * @updates this

     * @ensures this = rev(#this)

     */

    public static <T> void flip(QueueWithNewFlip thiss) {

        // Create another queue

        Queue<T> tempq = new Queue2<T>();

        // Repeat until this queue have no elements

        while (thiss.rep.length() > 0) {

            // remove all elements from this queue one by one, except last

            // element and enqueue into this queue

            for (int i = 0; i < thiss.rep.length() - 1; i++) {

                thiss.rep.enqueue(thiss.rep.dequeue());

            }

            // enqueue the last element into temporary queue

            tempq.enqueue((T) thiss.rep.dequeue());

        }

        // again insert all the elements of temporary queue into this queue

        while (tempq.length() > 0) {

            thiss.rep.enqueue(tempq.dequeue());

        }

        // clear the temporary queue

        tempq.clear();

    }

    public int length() {

        return this.rep.length();

    }

    public static void main(String args[]) {

        QueueWithNewFlip<Integer> que = new QueueWithNewFlip<Integer>();

        que.enqueue(123);

        que.enqueue(234);

        que.enqueue(345);

        que.enqueue(456);

        // Print the queue before flip

        System.out.println("Before flip: ");

        Iterator<Integer> itrq1 = que.rep.iterator();

        while (itrq1.hasNext()) {

            System.out.println(itrq1.next());

        }

        // Call flip to reverse the queue

        que.flip(que);

        // Print the queue before flip

        System.out.println("After flip: ");

        Iterator<Integer> itrq2 = que.rep.iterator();

        while (itrq2.hasNext()) {

            System.out.println(itrq2.next());

        }

    }

}