Purpose: Adapt a doubly linked list to behave like a stack and a queue. Modify t
ID: 3856922 • Letter: P
Question
Purpose: Adapt a doubly linked list to behave like a stack and a queue.
Modify the singly linked list from lab1 into a doubly linked list. After implementing the doubly linked list, implement it to behave like a stack and a queue using inheritance. Implement the standard interface for a stack and queue. See your textbook or google for complete interface.
Create a test case to validate your doubly linked list can be adapted to behave like a queue and a stack.
Here's the code
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *next;
}*start;
/*
* Class Declaration
*/
class single_llist
{
public:
node* create_node(int);
void insert_begin();
void insert_pos();
void insert_last();
void delete_pos();
void sort();
void search();
void update();
void reverse();
void display();
single_llist()
{
start = NULL;
}
};
/*
* Main :contains menu
*/
int main()
{
int choice, nodes, element, position, i;
single_llist sl;
start = NULL;
while (1)
{
cout<<endl<<"---------------------------------"<<endl;
cout<<endl<<"Operations on singly linked list"<<endl;
cout<<endl<<"---------------------------------"<<endl;
cout<<"1.Insert Node at beginning"<<endl;
cout<<"2.Insert node at last"<<endl;
cout<<"3.Insert node at position"<<endl;
cout<<"4.Sort Link List"<<endl;
cout<<"5.Delete a Particular Node"<<endl;
cout<<"6.Update Node Value"<<endl;
cout<<"7.Search Element"<<endl;
cout<<"8.Display Linked List"<<endl;
cout<<"9.Reverse Linked List "<<endl;
cout<<"10.Exit "<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Inserting Node at Beginning: "<<endl;
sl.insert_begin();
cout<<endl;
break;
case 2:
cout<<"Inserting Node at Last: "<<endl;
sl.insert_last();
cout<<endl;
break;
case 3:
cout<<"Inserting Node at a given position:"<<endl;
sl.insert_pos();
cout<<endl;
break;
case 4:
cout<<"Sort Link List: "<<endl;
sl.sort();
cout<<endl;
break;
case 5:
cout<<"Delete a particular node: "<<endl;
sl.delete_pos();
break;
case 6:
cout<<"Update Node Value:"<<endl;
sl.update();
cout<<endl;
break;
case 7:
cout<<"Search element in Link List: "<<endl;
sl.search();
cout<<endl;
break;
case 8:
cout<<"Display elements of link list"<<endl;
sl.display();
cout<<endl;
break;
case 9:
cout<<"Reverse elements of Link List"<<endl;
sl.reverse();
cout<<endl;
break;
case 10:
cout<<"Exiting..."<<endl;
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
}
}
/*
* Creating Node
*/
node *single_llist::create_node(int value)
{
struct node *temp, *s;
temp = new(struct node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;
return 0;
}
else
{
temp->info = value;
temp->next = NULL;
return temp;
}
}
/*
* Inserting element in beginning
*/
void single_llist::insert_begin()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *p;
temp = create_node(value);
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
p = start;
start = temp;
start->next = p;
}
cout<<"Element Inserted at beginning"<<endl;
}
/*
* Inserting Node at last
*/
void single_llist::insert_last()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s;
temp = create_node(value);
s = start;
while (s->next != NULL)
{
s = s->next;
}
temp->next = NULL;
s->next = temp;
cout<<"Element Inserted at last"<<endl;
}
/*
* Insertion of node at a given position
*/
void single_llist::insert_pos()
{
int value, pos, counter = 0;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s, *ptr;
temp = create_node(value);
cout<<"Enter the postion at which node to be inserted: ";
cin>>pos;
int i;
s = start;
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos == 1)
{
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
ptr = start;
start = temp;
start->next = ptr;
}
}
else if (pos > 1 && pos <= counter)
{
s = start;
for (i = 1; i < pos; i++)
{
ptr = s;
s = s->next;
}
ptr->next = temp;
temp->next = s;
}
else
{
cout<<"Positon out of range"<<endl;
}
}
/*
* Sorting Link List
*/
void single_llist::sort()
{
struct node *ptr, *s;
int value;
if (start == NULL)
{
cout<<"The List is empty"<<endl;
return;
}
ptr = start;
while (ptr != NULL)
{
for (s = ptr->next;s !=NULL;s = s->next)
{
if (ptr->info > s->info)
{
value = ptr->info;
ptr->info = s->info;
s->info = value;
}
}
ptr = ptr->next;
}
}
/*
* Delete element at a given position
*/
void single_llist::delete_pos()
{
int pos, i, counter = 0;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the position of value to be deleted: ";
cin>>pos;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start = s->next;
}
else
{
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos > 0 && pos <= counter)
{
s = start;
for (i = 1;i < pos;i++)
{
ptr = s;
s = s->next;
}
ptr->next = s->next;
}
else
{
cout<<"Position out of range"<<endl;
}
free(s);
cout<<"Element Deleted"<<endl;
}
}
/*
* Update a given Node
*/
void single_llist::update()
{
int value, pos, i;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the node postion to be updated: ";
cin>>pos;
cout<<"Enter the new value: ";
cin>>value;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start->info = value;
}
else
{
for (i = 0;i < pos - 1;i++)
{
if (s == NULL)
{
cout<<"There are less than "<<pos<<" elements";
return;
}
s = s->next;
}
s->info = value;
}
cout<<"Node Updated"<<endl;
}
/*
* Searching an element
*/
void single_llist::search()
{
int value, pos = 0;
bool flag = false;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the value to be searched: ";
cin>>value;
struct node *s;
s = start;
while (s != NULL)
{
pos++;
if (s->info == value)
{
flag = true;
cout<<"Element "<<value<<" is found at position "<<pos<<endl;
}
s = s->next;
}
if (!flag)
cout<<"Element "<<value<<" not found in the list"<<endl;
}
/*
* Reverse Link List
*/
void single_llist::reverse()
{
struct node *ptr1, *ptr2, *ptr3;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
if (start->next == NULL)
{
return;
}
ptr1 = start;
ptr2 = ptr1->next;
ptr3 = ptr2->next;
ptr1->next = NULL;
ptr2->next = ptr1;
while (ptr3 != NULL)
{
ptr1 = ptr2;
ptr2 = ptr3;
ptr3 = ptr3->next;
ptr2->next = ptr1;
}
start = ptr2;
}
/*
* Display Elements of a link list
*/
void single_llist::display()
{
struct node *temp;
if (start == NULL)
{
cout<<"The List is Empty"<<endl;
return;
}
temp = start;
cout<<"Elements of list are: "<<endl;
while (temp != NULL)
{
cout<<temp->info<<"->";
temp = temp->next;
}
cout<<"NULL"<<endl;
}
Explanation / Answer
import java.io.*;
public class TestLinkedStack {
public static void main(String args[]) {
FileReader f = null; // to read files
BufferedReader reader = null; // reading buffer
String line = null; // read lines
LinkedStack stack = new LinkedStack(); // initialization
if (args.length < 1) {
System.err.println("Please invoke the program like this:");
System.err.println(" LinkedStack file");
}
try {
f = new FileReader(args[0]);
reader = new BufferedReader(f);
while ((line = reader.readLine()) != null)
stack.push(line);
} catch (Exception e) {
System.err.println("File not found " + args[0]);
return;
}
while ((line = (String) stack.pop()) != null) {
System.out.println(line);
}
}
}
public class LinkedQueue {
class Node {
Object elem;
Node Next;
public Node(Object o) {
elem = o;
Next = null;
}
}
Node first;
Node end;
int size;
public LinkedQueue() {
end = null;
size = 0;
}
public void enqueue(Object o) {
Node new_node = new Node(o);
if (first == null) {
first = new_node;
end = new_node;
} else {
end.Next = new_node;
end = new_node;
}
size++;
}; // inserts an object onto the queue
public Object dequeue() {
if (first == null)
return null;
;
Object o = first.elem;
first = first.Next;
size--;
return o;
} // gets the object from the queue
public boolean isEmpty() {
return (size == 0);
}
public int size() {
return size;
}
public Object first() {
if (first == null)
return null;
else
return first.elem;
}
}
import java.io.*;
public class TestLinkedQueue {
public static void main(String args[]) {
FileReader f = null; // to read files
BufferedReader reader = null; // reading buffer
String line = null; // read lines
LinkedQueue queue = new LinkedQueue(); // initialization
if (args.length < 1) {
System.err.println("Please invoke the program like this:");
System.err.println(" LinkedQueue file1 file2");
}
// opens the first file
try {
f = new FileReader(args[0]);
reader = new BufferedReader(f);
while ((line = reader.readLine()) != null)
queue.enqueue(line);
} catch (Exception e) {
System.err.println("File not found " + args[0]);
return;
}
// opens the second file
try {
f = new FileReader(args[1]);
reader = new BufferedReader(f);
while ((line = reader.readLine()) != null)
queue.enqueue(line);
} catch (Exception e) {
System.err.println("File not found " + args[1]);
return;
}
// Gets the strings from the queue and prints them
while ((line = (String) queue.dequeue()) != null) {
System.out.println(line);
}
}
}
public class List {
public class Node {
Node next;
Node previous;
Object data;
public Node(Node next, Object data) {
this.next = next;
this.data = data;
}
public Node(Object elem) {
this(null, elem);
}
}
private Node first;
private Node currentPosition;
public void forward(int numPositions) {
if (numPositions > 0 && first != null) {
int positionsForward = numPositions;
if (currentPosition == null) {
currentPosition = first;
positionsForward--;
}
while (currentPosition.next != null && positionsForward > 0) {
currentPosition = currentPosition.next;
positionsForward--;
}
}
}
public void insert(Object data) {
Node node = new Node(data);
if (currentPosition == null) {
// inserts in first node
node.next = first;
if (first != null) {
first.previous = node;
}
first = node;
} else {
// the node isn't the first.
node.next = currentPosition.next;
node.previous = currentPosition;
if (currentPosition.next != null) {
currentPosition.next.previous = node;
}
currentPosition.next = node;
}
// updates current position
currentPosition = node;
}
public Object extract() {
Object data = null;
if (currentPosition != null) {
data = currentPosition.data;
// 'delete' the node
if (first == currentPosition) {
first = currentPosition.next;
} else {
currentPosition.previous.next = currentPosition.next;
}
if (currentPosition.next != null) {
currentPosition.next.previous = currentPosition.previous;
}
// next position
currentPosition = currentPosition.next;
}
return data;
}
/** testing program */
public String toString() {
Node aux = first;
StringBuffer sb = new StringBuffer();
while (aux != null) {
sb.append(aux.data);
aux = aux.next;
}
return sb.toString();
}
/**
* Go back -numPositions-
*/
public void back(int numPositions) {
if (numPositions <= 0 || first == null || currentPosition == null)
return;
int positionsBack = numPositions;
while (currentPosition != null && positionsBack > 0) {
currentPosition = currentPosition.previous;
positionsBack--;
}
}
/** Test method */
public static void main(String[] args) {
List list = new List();
list.insert("Node1");
list.insert("Node2");
System.out.println("Initial list: " + list.toString());
System.out
.println("Data in current position: " + list.currentPosition.data);
System.out.println("Add Node: ");
list.insert("Node3");
System.out
.println("Data in current position: " + list.currentPosition.data);
System.out.println("List: " + list.toString());
list.back(1);
System.out.println("Go back one position");
System.out
.println("Data in current position: " + list.currentPosition.data);
System.out.println("List: " + list.toString());
list.insert("Node4");
System.out
.println("Data in current position: " + list.currentPosition.data);
System.out.println("List: " + list.toString());
list.extract();
System.out.println("delete... ");
System.out
.println("Data in current position: " + list.currentPosition.data);
System.out.println("List: " + list.toString());
System.out.println("Go forward 7 ");
list.forward(7);
System.out
.println("Data in current position: " + list.currentPosition.data);
System.out.println("List: " + list.toString());
list.back(1);
list.extract();
System.out
.println("Data in current position: " + list.currentPosition.data);
System.out.println("List: " + list.toString());
list.extract();
System.out.println("Current position: " + list.currentPosition);
System.out.println("List: " + list.toString());
list.forward(1);
list.extract();
System.out.println("Current position: " + list.currentPosition);
System.out.println("List: " + list.toString());
list.extract();
System.out.println("Current position: " + list.currentPosition);
System.out.println("List: " + list.toString());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.