Question
Implement the following class file using "Arrays" in C++
#ifndef _DEQUE_H_
#define _DEQUE_H_
#include <iostream>
#include <cstdlib>
template <typename T>
class deque
{
public:
typedef std::size_t size_type;
static const size_type CAPACITY = 10;
//postcondition: empty deque has been created
deque();
//precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
T& front();
// precondition: deque is not empty
// postcondition: copy of element at front of deque
// has been returned
T front() const;
// precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
T& back();
// precondition: deque is not empty
// postcondition: copy of element at back of deque
// has been returned
T back() const;
// precondition: deque is not full
// postcondition: entry has been inserted at the front
// of the deque
void push_front (const T& entry);
// precondition: deque is not full
// postcondition: entry has been inserted at the back
// of the deque
void push_back (const T& entry);
// precondition: deque is not empty
// postcondition: element at front of deque has been removed
void pop_front();
// precondition: deque is not empty
// postcondition: element at back of deque has been removed
void pop_back();
// postcondition: number of elements in deque has been returned
size_type size() const;
// postcondition: whether deque is empty has been returned
bool empty() const;
// postcondition: whether deque is full has been returned
bool full() const;
// postcondition: returned whether 2 deques are equal - equal is defined
// as the deques have the same number of elements &
// corresponding elements are equal
template <typename U>
friend bool operator == (const deque<U>& dq1, const deque<U>& dq2);
// postcondition: dq has been display from front to rear on out
template <typename U>
friend std::ostream& operator<< (std::ostream& out, const deque<U>& dq);
private:
T data[CAPACITY]; // Circular array
size_type first; // Index of item at front of the queue
size_type last; // Index of item at rear of the queue
size_type count; // Total number of items in the queue
// postcondition: returned next index in array
size_type next_index(size_type i) const;
// postcondition: returned previous index in array
size_type prev_index (size_type i) const;
};
#include "deque.template"
#endif
THANKS FOR YOUR HELP!
Explanation / Answer
public static void main(String[] args) { LinkedDequeue deque = new LinkedDequeue(); System.out.println("DEQUE TESTING"); //per Q1 deque.enqueueBack(3); deque.enqueueBack(7); deque.enqueueBack(4); deque.dequeueFront(); deque.enqueueBack(9); deque.enqueueBack(8); deque.dequeueFront(); System.out.println("The size of the deque is: " + deque.size()); System.out.println("The deque contains: " + deque.toString()); //new features System.out.println(deque.dequeueFront()); deque.enqueueFront(1); deque.enqueueFront(11); deque.enqueueFront(3); deque.enqueueFront(5); System.out.println(deque.dequeueBack()); System.out.println(deque.dequeueBack()); System.out.println(deque.last()); deque.dequeueFront(); deque.dequeueFront(); System.out.println(deque.first()); System.out.println("The size of the deque is: " + deque.size()); System.out.println("The deque contains: " + deque.toString()); } /** * LinkedDeque represents a linked implementation of a deque. * */ public static class LinkedDequeue implements DequeADT { private int count; private LinearDoubleNode head, tail; //front, back /** * Creates an empty queue. */ public LinkedDequeue() { count = 0; head = tail = null; } public void enqueueBack(T element) { LinearDoubleNode node = new LinearDoubleNode(element); if (isEmpty()) head = node; else tail.setNext(node); tail = node; count++; } public void enqueueFront(T element) { LinearDoubleNode node = new LinearDoubleNode(element); count++ ; if (head == null) { head = node; } else { node.setNext(head); head = node; } } public T dequeueFront() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("queue"); T result = head.getElement(); head = head.getNext(); count--; if (isEmpty()) head = null; return result; } public T dequeueBack() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("queue"); T result = tail.getElement(); tail = tail.getNext(); if (isEmpty()) head = null; count --; return result; } /** * Returns a reference to the element at the head of this queue. * The element is not removed from the queue. * @return a reference to the first element in this queue * @throws EmptyCollectionsException if the queue is empty */ public T first() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("stack"); T result = head.getElement(); return result; } /** * Returns a reference to the element at the tail of this queue. * The element is not removed from the queue. * @return a reference to the first element in this queue * @throws EmptyCollectionsException if the queue is empty */ public T last() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("stack"); T result = tail.getElement(); return result; } public boolean isEmpty() { if (head == null) { return true; } else { return false; } } public int size() { return count; } public String toString() { StringBuilder sb = new StringBuilder(); LinearDoubleNode tmp = head; while (tmp != null) { sb.append(tmp.getElement()).append(" "); tmp = tmp.getNext(); } return sb.toString(); } }