Using a Word document or drawing tool of your choice, provide answers to the following questions and...

Question

Using a Word document or drawing tool of your choice, provide answers to the following questions and diagram the results of the operations in Part 1. For Part 2 and Part 3, take screenshots of the output and copy the code and screenshots into the same document used in Part 1. Part 1 Illustrate the result of each operation in the sequence PUSH(S, 4), PUSH(S, 1), PUSH(S,3), POP(S), PUSH(S, 8), and POP(S) on an initially empty stack S stored in array S[1… 6]. When you begin, the stack is empty. You will need to draw a diagram of the stack showing the result after each operation. Part 2: Implement a stack using a singly linked list L in Python or Java. • Do the operations PUSH and POP take O(1) time? • Explain why? Test your code with PUSH(10), PUSH(30), POP(), PUSH(80), and POP Part 3: Implement a queue by a singly linked list L in Python or Java. • Do the operations ENQUEUE and DEQUEUE take O(1) time? • Why? Test your code with ENQUEUE(4), ENQUEUE(1), ENQUEUE(3), DEQUEUE(), ENQUEUE(8), and DEQUEUE(). For assistance, view the animations under Stacks and Queues. Reference cathyatseneca. (2014). Data structure animations using processing.js. GitHub. http://cathyatseneca.github.io/DSAnim/web/arrayqueue.html PART 4 Write a code to implement a doubly linked list in JAVA or Python. Test your program with different sets of data and take screenshots of the output after each test. Perform an asymptotic analysis of your algorithm. Compare the doubly linked list with the single linked list in time and space complexity. · How do they differ in implementation? Copy your source code and paste the screenshots in a word document along with the asymptotic analysis and your response to the question into a Word document.

week-5-hjbapxfz.docx

Vikas · Accepted Answer

Assignment
Part 1:
Illustrate the result of each operation in the sequence
Push(S, 4)
	
	
	
	
	
	4
Push(S, 1)
	
	
	
	
	1
	4
Push(S, 3)
	
	
	
	3
	1
	4
Pop(S)
	
	
	
	
	1
	4
Push(S, 8)
	
	
	
	8
	1
	4
Pop(S)
	
	
	
	
	1
	4
Part 2:
Implement a stack using a singly linked list L in Python or Java. 
Code:
import java.util.*;
 
class Main {
    public static void main(String[] args) {
        MyStack st= new MyStack();
        st.push(10);
        st.push(30);
        st.pop();
        st.push(80);
        st.pop();
        
        st.print();
    }
}
 
class MyStack {
 
    class Node {
        int val; 
        Node next; 
    }
    
    Node top = null;
    public void push(int x) {
        Node temp = new Node();
        temp.val = x;
        temp.next = top;
        top = temp;
    }
    
    public void print() {
        if (top == null) {
            System.out.println("Underflow");
        }
        else {
            Node node = top;
            while (node != null) {
                System.out.print(node.val);
                node = node.next;
                if(node != null)
                    System.out.print(" -> ");
            }
        }
    }
 
    public int peek() {
        return top.val;
    }
 
    public void pop() {
        top = (top).next;
    }
}
Q. Do the operations PUSH and POP take O(1) time? Explain why? 
Ans: yes, PUSH and POP takes O(1) time because we are not traversing on the stack and we are only working with a pointer called top.
Q. Test your code with PUSH(10), PUSH(30), POP(), PUSH(80), and POP 
Ans: Here is the output after I ran the code on this input
Part 3:

Using a Word document or drawing tool of your choice, provide answers to the following questions and diagram the results of the operations in Part 1. For Part 2 and Part 3, take screenshots of the...

Answer To: Using a Word document or drawing tool of your choice, provide answers to the following questions and...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment