public class Stack { public int size; public int top; public int[] array; public
ID: 3586473 • Letter: P
Question
public class Stack {
public int size;
public int top;
public int[] array;
public Stack () {
size = 0;
top = -1;
array = null;
}
public Stack (int _size) {
size = _size;
top = -1;
array = new int[size];
}
/*
* Implement the Stack-Empty(S) function
*/
public boolean empty () {
}
/*
* Implement the Push(S, x) function
*/
public void push (int x) {
}
/*
* Implement the Pop(S) function
* Return -1 if the stack is empty
*/
public int pop () {
}
/*
* Convert stack to string in the format of #size, [#elements]
*/
public String toString () {
String str;
str = size + ", [";
for (int i = 0; i <= top; i++)
str += array[i] + ", ";
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack s;
s = new Stack(10);
for (int i = 0; i < 5; i++)
s.push(i);
System.out.println(s.toString());
for (int i = 0; i < 2; i++)
s.pop();
System.out.println(s.toString());
}
}
package ds;
public class Queue {
public int size;
public int[] array;
public int head;
public int tail;
public Queue () {
size = 0;
array = null;
head = -1;
tail = 0;
}
public Queue (int _size) {
size = _size;
array = new int[size];
head = -1;
tail = 0;
}
/*
* Implement the ENQUEUE(Q, x) function
*/
public void enqueue (int x) {
}
/*
* Implement the DEQUEUE(Q) function
*/
public int dequeue () {
}
/*
* Convert queue to string in the format of #size, head, tail,
[#elements]
*/
public String toString () {
String str;
str = size + ", " + head + ", " + tail + ", [";
for (int i = head; i%size < tail; i++)
str += array[i] + ",";
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue q;
q = new Queue(10);
for (int i = 0; i < 5; i++)
q.enqueue(i);
System.out.println(q.toString());
for (int i = 0; i < 2; i++)
q.dequeue();
System.out.println(q.toString());
}
}
package ds;
public class LinkedList {
public ListNode head;
public LinkedList () {
head = null;
}
/*
* Implement the LIST-SEARCH(L, k) function
*/
public ListNode search (int k) {
}
/*
* Implement the LIST-INSERT(L, x) function
* Note that x is a integer value, not a ListNode
*/
public void insert (int x) {
}
/*
* Implement the LIST-DELETE(L, x) function
*/
public void delete (ListNode x) {
}
/*
* Convert a LinkedList to a string in the format of [#elements]
*/
public String toString () {
String str;
ListNode n;
str = "[";
n = this.head;
while (n != null) {
str += n.key + ",";
n = n.next;
}
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList l;
l = new LinkedList();
for (int i = 0; i < 5; i++)
l.insert(i);
System.out.println(l.toString());
for (int i = 0; i < 2; i++)
l.delete(l.head.next);
System.out.println(l.toString());
}
}
package ds;
public class ListNode {
public int key;
public ListNode prev;
public ListNode next;
public ListNode () {
prev = next = null;
}
public ListNode (int _key) {
key = _key;
prev = next = null;
}
}
. Task 1 (30 pts). Implement the empty), push(int z), and pop) function . Task 2 (30 pts). Implement the enqueue(int x), dequeue() function for . Task 3 (40 pts). Implement the search(int k), insert(int z), delete() func- » Task 4 (10 pts Extra Credit). In the push(int x) function of Stack.java, by for Stack in Stack.java as discussed in Lecture 5 Queue in Queue.java as discussed in Lecture 5. tion in LinkedList.java as discussed in Lecture 6. default, we never check if the stack is already fi into a full stack, we should get an error. Implement the capacity check feature for push(int x). (Hint: Use System.err.println() to print the error messagee if the stack is already full. If we insert an element Task 5 (10 pts Extra Credit). In the enqueue(int x) function of Queue.java, we do not check if the queue is already full. Implement the capacity check feature for enqueue(int x). (Hint: Use System.err.println() to print the error message.) . Task 6 (10 pts Extra Credit). In the dequeue() function of Queue.java, we do not check if the queue is empty. If we dequeue an empty queue, we should also get an error. Implement the empty check feature for en- queue(int x). (Hint: Use System.err.println() to print the error message.)Explanation / Answer
//Queue.java
package com.test;
public class Queue {
public int size;
public int[] array;
public int head;
public int tail;
public Queue () {
size = 0;
array = null;
head = -1;
tail = 0;
}
public Queue (int _size) {
size = _size;
array = new int[size];
head = -1;
tail = 0;
}
/*
* Implement the ENQUEUE(Q, x) function
*/
public void enqueue (int x) {
if(tail == size)
System.err.println("Queue is full");
else
array[tail++] = x;
}
/*
* Implement the DEQUEUE(Q) function
*/
public int dequeue () {
if(head+1 == tail)
System.err.println("Queue is empty");
else {
int item = array[head++];
return item;
}
return -1;
}
/*
* Convert queue to string in the format of #size, head, tail,
[#elements]
*/
public String toString () {
String str;
str = size + ", " + head + ", " + tail + ", [";
for (int i = head; i%size < tail; i++)
str += array[i] + ",";
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue q;
q = new Queue(10);
for (int i = 0; i < 5; i++)
q.enqueue(i);
System.out.println(q.toString());
for (int i = 0; i < 2; i++)
q.dequeue();
System.out.println(q.toString());
}
}
//LinkedList.java
package com.test;
public class LinkedList {
public ListNode head;
public LinkedList () {
head = null;
}
/*
* Implement the LIST-SEARCH(L, k) function
*/
public ListNode search (int k) {
ListNode temp = head;
while(temp != null)
{
if(temp.key == k)
return temp;
temp = temp.next;
}
return null;
}
/*
* Implement the LIST-INSERT(L, x) function
* Note that x is a integer value, not a ListNode
*/
public void insert (int x) {
ListNode temp = head;
while(temp.next != null)
{
temp = temp.next;
}
ListNode n = new ListNode(x);
temp.next = n;
}
/*
* Implement the LIST-DELETE(L, x) function
*/
public void delete (ListNode x) {
ListNode temp = head;
ListNode prev = null;
while(temp.next != null && temp != x)
{
prev = temp;
temp = temp.next;
}
if(prev == null && temp == x)
{
head = head.next;
}
else if(temp == x)
{
prev.next = temp.next;
temp.next = null;
}
}
/*
* Convert a LinkedList to a string in the format of [#elements]
*/
public String toString () {
String str;
ListNode n;
str = "[";
n = this.head;
while (n != null) {
str += n.key + ",";
n = n.next;
}
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList l;
l = new LinkedList();
for (int i = 0; i < 5; i++)
l.insert(i);
System.out.println(l.toString());
for (int i = 0; i < 2; i++)
l.delete(l.head.next);
System.out.println(l.toString());
}
}
//ListNode.java
package com.test;
public class ListNode {
public int key;
public ListNode prev;
public ListNode next;
public ListNode () {
prev = next = null;
}
public ListNode (int _key) {
key = _key;
prev = next = null;
}
}
//Stack.java
package com.test;
public class Stack {
public int size;
public int top;
public int[] array;
public Stack () {
size = 0;
top = -1;
array = null;
}
public Stack (int _size) {
size = _size;
top = -1;
array = new int[size];
}
/*
* Implement the Stack-Empty(S) function
*/
public boolean empty () {
return (top == -1);
}
/*
* Implement the Push(S, x) function
*/
public void push (int x) {
if(top == size)
System.err.println("Stack is full");
else {
array[++top] = x;
}
}
/*
* Implement the Pop(S) function
* Return -1 if the stack is empty
*/
public int pop () {
if(!empty()) {
int item = array[top];
top--;
size--;
return item;
}
return -1;
}
/*
* Convert stack to string in the format of #size, [#elements]
*/
public String toString () {
String str;
str = size + ", [";
for (int i = 0; i <= top; i++)
str += array[i] + ", ";
str += "]";
return str;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack s;
s = new Stack(10);
for (int i = 0; i < 5; i++)
s.push(i);
System.out.println(s.toString());
for (int i = 0; i < 2; i++)
s.pop();
System.out.println(s.toString());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.