The purpose of this assignment is to help reinforce linear data structure implem

Question

The purpose of this assignment is to help reinforce linear data structure implementations in C++. Specifically, the assignment is to construct a C++ implementation of a static deque class. The header file that we will use is deque.h.

#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 the back 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 displayed from front to rear
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

Explanation / Answer

#include #include struct node { int info; struct node *ptr; }*front,*rear,*temp,*front1; int frontelement(); void enq(int data); void deq(); void empty(); void display(); void create(); void queuesize(); int count = 0; void main() { int no, ch, e; printf(" 1 - Enque"); printf(" 2 - Deque"); printf(" 3 - Front element"); printf(" 4 - Empty"); printf(" 5 - Exit"); printf(" 6 - Display"); printf(" 7 - Queue size"); create(); while (1) { printf(" Enter choice : "); scanf("%d", &ch); switch (ch) { case 1: printf("Enter data : "); scanf("%d", &no); enq(no); break; case 2: deq(); break; case 3: e = frontelement(); if (e != 0) printf("Front element : %d", e); else printf(" No front element in Queue as queue is empty"); break; case 4: empty(); break; case 5: exit(0); case 6: display(); break; case 7: queuesize(); break; default: printf("Wrong choice, Please enter correct choice "); break; } } } /* Create an empty queue */ void create() { front = rear = NULL; } /* Returns queue size */ void queuesize() { printf(" Queue size : %d", count); } /* Enqueing the queue */ void enq(int data) { if (rear == NULL) { rear = (struct node *)malloc(1*sizeof(struct node)); rear->ptr = NULL; rear->info = data; front = rear; } else { temp=(struct node *)malloc(1*sizeof(struct node)); rear->ptr = temp; temp->info = data; temp->ptr = NULL; rear = temp; } count++; } /* Displaying the queue elements */ void display() { front1 = front; if ((front1 == NULL) && (rear == NULL)) { printf("Queue is empty"); return; } while (front1 != rear) { printf("%d ", front1->info); front1 = front1->ptr; } if (front1 == rear) printf("%d", front1->info); } /* Dequeing the queue */ void deq() { front1 = front; if (front1 == NULL) { printf(" Error: Trying to display elements from empty queue"); return; } else if (front1->ptr != NULL) { front1 = front1->ptr; printf(" Dequed value : %d", front->info); free(front); front = front1; } else { printf(" Dequed value : %d", front->info); free(front); front = NULL; rear = NULL; } count--; } /* Returns the front element of queue */ int frontelement() { if ((front != NULL) && (rear != NULL)) return(front->info); else return 0; } /* Display if queue is empty or not */ void empty() { if ((front == NULL) && (rear == NULL)) printf(" Queue empty"); else printf("Queue not empty"); }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.