Question
1. What is the time complexity for the following operations in queue:
a. Time complexity of enqueue in (circular) array-based queue.
b. Time complexity of dequeue in (circular) array-based queue.
c. Time complexity of enqueue in (noncircular) array-based queue.
d. Time complexity of dequeue in (noncircular) array-based queue.
e. Time complexity of enqueue in link-based queue.
f. Time complexity of dequeue in link-based queue.
g. What is the time complexity of size() in a link-based queue with a count variable?
h. What is the time complexity of size() in a link-based queue without a count variable? (See part 2 of this assignment.)
2. For the queue implementations, the code discussed in class uses a count variable to keep track of the number of elements in the queue. Rewrite the link-based implementation without a count variable.
3. Implement the following function: obtain user input as a String, then output whether the input is a Palindrome. Complete this task by storing the characters of the string in a queue, as well as in a stack. Remove characters from both and compare. If they always match, it’s a palindrome.
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.
package adtqueue;class QueueNode{
char value;
QueueNode next;
public QueueNode(char value){
this.value = value;
next = null;
}
public char getValue(){
return value;
}
public QueueNode getNext() {
return next;
}
public void setNext(QueueNode next) {
this.next = next;
}
}
class ADTQueue{
private QueueNode front, rear;
public ADTQueue(){
front = null;
rear = null;
}
public void enqueue(char value){
QueueNode node = new QueueNode(value);
if(rear == null){
rear = node;
if(front == null){
front = node;
}
}else {
rear.setNext(node);
rear = node;
}
}
public char dequeue(){
if(!isEmpty()){
QueueNode d = front;
if(front == rear){
front = null;
rear = null;
}else {
front = d.getNext();
}
return d.getValue();
}else {
return ' ';
}
}...
By purchasing this solution you'll be able to access the following files:
Solution.zip.