1. Referencing an Array implementation of a Queue; Illustrate by drawing the imp
ID: 672834 • Letter: 1
Question
1. Referencing an Array implementation of a Queue; Illustrate by drawing the implementation of what happens if the front or rear advances past the last array position (it is reset to the first array position). How would you code this event?
2. Draw a sorted queue with five elements (assume no repeats). Label the First and Last elements so they have identical element values. What is the size of the queue?
3. Write the code for a singlylinked list that supports the following: (Note which would be more efficient in an array implementation) a. accessing the element value in the current position b. insertion after the current position CSCI_2315 Data Structures Page 2 of 3 c. moving to the position immediately prior to the current position d. moving to the position immediately following the current position
4. Which statement inserts a new item x after position current? Illustrate. a. current = new ListNode(x, current); b. current = new ListNode(x, current.next); c. current.next = new ListNode(x, current); d. current.next = new ListNode(x, current.next);
5. If a header node is used, write the code that indicates (true) a list with one item and illustrate.
6. Write the condition, if true, guarantees that a doubly linked list with head and tail nodes is empty? 7. Illustrate the insertion of a node into a doubly linked list.
8. For the linked list implementation of the queue, illustrate where the enqueue and dequeues are performed? Note: a Queue is First in and First Out. Please label the first and last elements.
9. For the linked list implementation of the stack (use reference provided), state in English where are the pushes and pops performed? Note: A Stack is a First in Last Out Queue. Then write the code
Explanation / Answer
Question 1 Answer
An array can be used to implement a (bounded) stack, as follows. The first element (usually at the zero offset) is the bottom, resulting in array[0] being the first element pushed onto the stack and the last element popped off. The program must keep track of the size (length) of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted (assuming a zero-based index convention). Thus, the stack itself can be effectively implemented as a three-element structure:
The push operation adds an element and increments the top index, after checking for overflow:
Similarly, pop decrements the top index after checking for underflow, and return the item that was previously the top one:
Using a dynamic array, it is possible to implement a stack that can grow or shrink as much as needed. The size of the stack is simply the size of the dynamic array, which is a very efficient implementation of a stack since adding items to or removing items from the end of a dynamic array requires amortized O(1) time.
Question 2 Answer
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
template <typename T>
class QueuePopper
{
public:
QueuePopper(std::queue<T> &q) : q(q) {}
T operator() (const T &) { T t = q.front(); q.pop(); return t; }
private:
std::queue<T> &q;
};
int main()
{
typedef std::string T;
std::queue<T> q;
std::vector<T> v(5);
std::transform(v.begin(), v.end(), v.begin(), QueuePopper<T>(q));
}
Question 5 Answer
An inner class is a member of its enclosing class and has access to other members (inclusing private) of the outer class, And vise versa, the outer class can have a direct access to all members of the inner class. An inner class can be declared private, public, protected, or package private. There are two kind of inner classes: static and non-static. A static inner class cannot refer directly to instance variables or methods defined in its outer class: it can use them only through an object reference.
We implement the LinkedList class with two inner classes: static Node class and non-static LinkedListIterator class.
private static class Node<AnyType>
{
private AnyType data;
private Node<AnyType> next;
public Node(AnyType data, Node<AnyType> next)
{
this.data = data;
this.next = next;
}
}
head = head.next;
head.next = head.next.next;
head.next.next.next.next = head;
Question 6 Answer
#include <iostream>
#include "Student.h"
#include "Node.h"
using namespace std;
class List {
public:
List();
List(const List&);
List(); // Destructor
bool isEmpty(); int getNumNodes() {return numNodes;}
void append(Student *); // Append new Node to head or tail of List
void insert(Student *); // Inserts new Node in the
// Appropriate location in List
void deleteNode(string); //Search for and delete specific Node
void displayAscending();// Display List HEAD to TAIL
void displayDescending(); // Display List TAIL to HEAD
// input Student::data into Student pointer.
void input(Student*, string, string, string, string, string);
Node *getHead() const {return head;}
Node *getTail() const {return tail;}
private:
void printer(Node *);
Node *head;
Node *tail;
bool empty;
bool forward; // forward = head-to-tail i.e. true
int numNodes; // number of nodes in the list
};
Question 7 Answer
class Doubly
{
private:
struct node
{
string name;
node* next;
node* prev;
};
node* head;
node* last;
public:
Doubly();
~Doubly(); //dstrctr
bool empty() const { return head==NULL; }
void insert(const string& );
void remove(const string& );
void print(ostream& OutStream) const;
void sort (bool);
};
void Doubly::insert (const string& input)
{
// Insertion into an Empty List.
if(empty())
{
node* name = new node;
head = name;
last = name;
name -> prev = NULL;
name -> next = NULL;
name -> name = input;
}
else
{
node* newnode;
newnode = head;
while (input > newnode -> name && newnode -> next != last -> next)
newnode = newnode -> next;
if (newnode == head)
{
node* name = new node;
name -> name = input;
name -> prev = newnode;
name -> next = NULL;
head -> next = name;
last = name;
}
else
{
if (newnode == last && input > last -> name) {
last -> next = new node;
(last -> next) -> prev = last;
last = last -> next;
last -> next = NULL;
last -> name = input;
}
else
{
node* name = new node;
name -> name = input;
name -> next = newnode;
(newnode -> prev) -> next = name;
name -> prev = newnode -> prev;
newnode -> prev = name;
}
}
}
}
Question 8 Answer
#include<iostream.h>
class queue
{
int element;
queue* next;
public:
queue* enqueue(queue*,int);
queue* dequeue(queue*);
void queue_display(queue*);
}*head,*tail,object;
queue* queue::enqueue(queue* head,int key)
{
queue* temp;
temp=new queue;
temp->element=key;
temp->next=NULL;
if(head==NULL)
head=temp;
else
tail->next=temp;
tail=temp;
return head;
}
queue* queue::dequeue(queue* head)
{
queue* temp;
if(head==NULL)
{
cout<<" it is impossible to dequeue an element as ";
return NULL;
}
else if(head->next==NULL)
{
cout<<" the element dequeued from the queue is: "<<head->element<<endl;
return NULL;
}
else
{
cout<<" the element dequeued from the queue is "<<head->element<<endl;
temp=head->next;
head=temp;
cout<<" the elements of queue after dequeueing are ";
return head;
}
}
void queue::queue_display(queue* head)
{
if(head!=NULL)
{
while(head->next!=NULL)
{
cout<<head->element<<"->";
head=head->next;
}
cout<<head->element;
cout<<endl;
}
else
cout<<"the queue is empty ";
}
void choice()
{
int key,ch;
head=tail=NULL;
cout<<" choose the operation ";
cout<<" 1.enqueue 2.dequeue 3.exit ";
cin>>ch;
while(ch!=3)
{
switch(ch)
{
case 1:
cout<<" enter the key to be inserted ";
cin>>key;
head=object.enqueue(head,key);
cout<<" the elements of queue after inserting "<<key<<" are ";
object.queue_display(head);
break;
case 2:
head=object.dequeue(head);
object.queue_display(head);
break;
case 3:
break;
default:
cout<<" enter correct choice ";
break;
}
cout<<" —————— ";
cout<<" choose the operation ";
cout<<" 1.enqueue 2.dequeue 3.exit ";
cin>>ch;
cout<<" ———————— ";
}
}
void main()
{
choice();
}
Question 9 Answer
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int Data;
struct Node *next;
}*top;
void popStack()
{
struct Node *temp, *var=top;
if(var==top)
{
top = top->next;
free(var);
}
else
printf(" Stack Empty");
}
void push(int value)
{
struct Node *temp;
temp=(struct Node *)malloc(sizeof(struct Node));
temp->Data=value;
if (top == NULL)
{
top=temp;
top->next=NULL;
}
else
{
temp->next=top;
top=temp;
}
}
void display()
{
struct Node *var=top;
if(var!=NULL)
{
printf(" Elements are as: ");
while(var!=NULL)
{
printf(" %d ",var->Data);
var=var->next;
}
printf(" ");
}
else
printf(" Stack is Empty");
}
int main(int argc, char *argv[])
{
int i=0;
top=NULL;
printf(" 1. Push to stack");
printf(" 2. Pop from Stack");
printf(" 3. Display data of Stack");
printf(" 4. Exit ");
while(1)
{
printf(" Choose Option: ");
scanf("%d",&i);
switch(i)
{
case 1:
{
int value;
printf(" Enter a valueber to push into Stack: ");
scanf("%d",&value);
push(value);
display();
break;
}
case 2:
{
popStack();
display();
break;
}
case 3:
{
display();
break;
}
case 4:
{
struct Node *temp;
while(top!=NULL)
{
temp = top->next;
free(top);
top=temp;
}
exit(0);
}
default:
{
printf(" wrong choice for operation");
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.