Stack using Linked List

Uncategorized

1. Which of the following statements are not correct with respect to Singly Linked List(SLL) and Doubly Linked List(DLL)?
A) Complexity of Insertion and Deletion at known position is O(n) in SLL and O(1) in DLL
B) SLL uses lesser memory per node than DLL
C) DLL has more searching power than SLL
D) Number of node fields in SLL is more than DLL

Answer: D
Explanation: In the worst-case scenario, inserting and deleting at known locations requires a complete traversal of the list in SLL. SLL has an item and a node field, while DLL has an item and two node fields, so SLL takes up less memory. DLL can be traversed both ways(left and right), while SLL can only traverse in one direction, so DLL has more searching power. SLL has two node fields (data and the address of the next node), while DLL has three (data, address to next node, address to previous node).

2. What is the best case time complexity of deleting a node in a Singly Linked list?
A) O (n)
B) O (n2)
C) O (nlogn)
D) O (1)

Answer: D
Explanation: The best case scenario is to delete the linked list’s head node. The head node’s successor is changed to head, and the predecessor of the newly appointed head node is deleted. This process takes O(1) time to complete.

3. What does the following function do?

public Object some_func()throws emptyStackException
{
	if(isEmpty())
		throw new emptyStackException("underflow");
	return first.getEle();
}

A) pop
B) delete the top-of-the-stack element
C) retrieve the top-of-the-stack element
D) push operation

Answer: c
Explanation: This code only retrieves the top element; note that this is not the same as a pop operation since the ‘next’ pointer is not set to the next node in the chain.

4. Given below is the Node class to perform basic list operations and a Stack class with a no arg constructor.
Select from the options the appropriate pop() operation that can be included in the Stack class. Also ‘first’ is the top-of-the-stack.

class Node
{
	protected Node next;
	protected Object ele;
	Node()
	{
		this(null,null);
	}
	Node(Object e,Node n)
	{
		ele=e;
		next=n;
	}
	public void setNext(Node n)
	{
		next=n;
	}
	public void setEle(Object e)
	{
		ele=e;
	}
	public Node getNext()
	{
		return next;
	}
	public Object getEle()
	{
		return ele;
	}
}
 
class Stack
{
	Node first;
	int size=0;
	Stack()
	{
		first=null;
	}
}

A)

public Object pop() 
{
	if(size == 0)
	System.out.println("underflow");
	else
	{
		Object o = first.getEle();
		first = first.getNext();
		size--;
		return o;
	}
}

B)advertisementhttps://0136e7135abe6e2cd467247b395e8675.safeframe.googlesyndication.com/safeframe/1-0-38/html/container.html

public Object pop() 
{
	if(size == 0)
	System.out.println("underflow");
	else
	{
		Object o = first.getEle();
		first = first.getNext().getNext();
		size--;
		return o;
	}
}

C)

public Object pop() 
{
	if(size == 0)
	System.out.println("underflow");
	else
	{
		first = first.getNext();
		Object o = first.getEle();
		size--;
		return o;
	}
}

D)

public Object pop() 
{
	if(size == 0)
	System.out.println("underflow");
	else
	{
		first = first.getNext().getNext();
		Object o = first.getEle();
		size--;
		return o;
	}
}

Answer: A
Explanation: The Object pointed to by the node ‘first' should be returned by pop(). The steps are as follows: first, use getEle() to get the element stored at node ‘first,' and then use getNext() to make the node point to the next node ().

5. What does ‘stack overflow’ refer to?
A) accessing item from an undefined stack
B) adding items to a full stack
C) removing items from an empty stack
D) index out of bounds exception

Answer: B
Explanation: Stack underflow occurs when objects are added to a complete stack.

6. What is the functionality of the following piece of code?

public void display() 
{
	if(size == 0)
		System.out.println("underflow");
	else
	{
		Node current = first;
		while(current != null)
		{
			System.out.println(current.getEle());
			current = current.getNext();
		}
	}
}

A) reverse the list
B) display the list
C) display the list excluding top-of-the-stack-element
D) reverse the list excluding top-of-the-stack-element

Answer: B
Explanation: The node ‘first’ is given an alias that traverses the list and shows the elements.

7. Consider these functions:
push() : push an element into the stack
pop() : pop the top-of-the-stack element
top() : returns the item stored in top-of-the-stack-node
What will be the output after performing these sequence of operations

push(20);
push(4);
top();
pop();
pop();
pop();
push(5);
top();

A) 20
B) 4
C) stack underflow
D) 5

Answer: D
Explanation: The two pop() statements pop the 20 and 4 that were pushed; the most recent push() is 5, so top() returns 5.

8. Given below is the Node class to perform basic list operations and a Stack class with a no arg constructor. Select from the options the appropriate push() operation that can be included in the Stack class. Also ‘first’ is the top-of-the-stack.

class Node
{
	protected Node next;
	protected Object ele;
	Node()
	{
		this(null,null);
	}
	Node(Object e,Node n)
	{
		ele=e;
		next=n;
	}
	public void setNext(Node n)
	{
		next=n;
	}
	public void setEle(Object e)
	{
		ele=e;
	}
	public Node getNext()
	{
		return next;
	}
	public Object getEle()
	{
		return ele;
	}
}
 
class Stack
{
	Node first;
	int size=0;
	Stack()
	{
		first=null;
	}
}

A)

public void push(Object item)
{
	Node temp = new Node(item,first);
	first = temp;
	size++;
}

B)

public void push(Object item)
{
	Node temp = new Node(item,first);
	first = temp.getNext();
	size++;
}

C)

public void push(Object item)
{
	Node temp = new Node();
	first = temp.getNext();
	first.setItem(item);
	size++;
}

D)

public void push(Object item)
{
	Node temp = new Node();
	first = temp.getNext.getNext();
	first.setItem(item);
	size++;
}

Answer: A
Explanation: To add a new element to the stack, create a new node with the next pointer pointing to the current top-of-the-stack node, then set this node to "first" to make it the stack's top-level node.

9. Minimum number of queues to implement stack is ___________
A) 3
B) 4
C) 1
D) 2

Answer: C
Explanation: Using one queue and one clock to count the number of things in the queue.

10. Which of the following data structures can be used for parentheses matching?
A) n-ary tree
B) queue
C) priority queue
D) stack

Answer: D
Explanation: Push each opening brace into the stack, and remove each closing brace from the stack. Take no action on behalf of any other character. If the stack is empty at the end of the method, the input has balanced parentheses.

The linked list is a simple way to execute a stack. A stack includes a top pointer in stack implementation…. the first node link has null in the link field, the second node link has the first node address in the link field, and so on, with the last node address in the “top” pointer. The memory is dynamically allocated with a connected list. However, the time complexity of all operations, such as push, pop, and peek, is the same in both scenarios. The nodes in a connected list implementation of a stack are kept in memory in a non-contiguous manner. Each node in the stack has a pointer to its immediate successor node.

Leave a Reply

Your email address will not be published. Required fields are marked *