Answer and please explain this question from Algorithm Design and Analysis subje
ID: 3879420 • Letter: A
Question
Answer and please explain this question from Algorithm Design and Analysis subject. Thanks and will rate.
Question 1:Consider a Stack of n integers where n> 2. Using Push (item), Pop0, and Top O functions, call the sequence of functions to remove the third from the top item of the stack. All the remaining items should remain in the stack after this (see an example below). Note that Top O returns the top item from the stack while Pop) removes the top item from the stack. Here is an example. Current Stack in 12 14 10 23 17 12 14 23 17 Question 2:Consider a singly linked list. Write a function to find the size (the number of nodes) of the linked list.Explanation / Answer
Question 1)
The algorithm to remove the 3rd element from a stack would be following(Using Push(item),Pop(), and Top() functions):
Begin
Take a stack of integers Stack1 with n elements where n>2.
Take an empty stack of integers with capacity 2 as tempStack.
Take an integer variable say item;
item <---- Top() from Stack1;
Push(item) into tempStack;
Pop() from Stack1;
item <---- Top() from Stack1;
Push(item) into tempStack;
Pop() from Stack1;
Pop() from Stack1;
item <---- Top() from tempStack;
Push(item) into Stack1;
Pop() from tempStack;
item <---- Top() from tempStack;
Push(item) into Stack1;
Pop() from tempStack;
Stop
Explanation:
The steps to remove the 3rd item from top of the stack are following(here the steps are explained with the given example):
Considering a stack of integers with n elements where n>2; name this stack as Stack1; Now we have to remove the 3rd item from the top of the stack, we would use the sequence of functions Push(item), Pop() and Top() functions to perform this task.
The given original Stack is as following
12
14
10
23
17
Step 1:
Consider an empty temporary stack of integers, let say tempStack;
Step 2:
Top() from Stack1; this will return the top most element of the Stack1; which is 12 in this case; push this item into tempStack; then Pop() from Stack1;this pop() will remove the top element of the stack;
Stack1 would look as following:
14
10
23
17
tempStack would look as following:
12
Step 3:
Top() from Stack1; this will return the current top most element of the Stack1 that is 14;(which is actually the 2nd element of original stack); push this item into tempStack; then Pop() from Stack1; this pop() will remove the top element of the stack;
Stack1 would look as following:
10
23
17
tempStack would look as following:
14
12
Step 4:
Now the top element of Stack1 is the 3rd element of the original stack so we have to remove this, hence we will Pop() from Stack1 ; this action will remove the current top most element of the stack1, which is 10 here.
Stack1 would look as following:
23
17
tempStack would look as following:
14
12
Step 5:
Now we will apply top() function upon tempStack; this would return the top element of tempStack;which is 14 here; then we will push this item into Stack1; next we will Pop() from tempStack which will remove the current top element of tempStack;
tempStack would look as following:
12
Stack1 would look as following:
14
23
17
Step 6:
Now we will again apply top() function upon tempStack; this would return the top element of tempStack; which is 12 here; then we will push this item into Stack1; next we will Pop() from tempStack which will remove the current top element of tempStack;
tempStack would now become empty:
Stack1 would look as following:
12
14
23
17
Thus finally we get Stack1 which is same as original stack where only the 3rd element has been removed.
/*NOTE: If you want this in a different way, please let me know through comments; I will surely revert back to you.*/
Question 2)
Function to find the size of a Singly Linkedlist in C/C++ is given below:
/* Returns the number of nodes in singly linked list */
/*This function takes head pointer of the singly linked list as an argument*/
int getSize(struct Node* head)
{
int count = 0; // Initialize count
struct Node* current = head; // Initialize current pointer
while (current != NULL)
{
current = current->next;
count++;
}
return count;
}
/* Assuming the Link list node definition is as follows*/
struct Node
{
int data;
struct Node* next;
};
Example:
The function should return 7 for linked list 10->37->1->12->19->21->14->NULL.
Algorithm of the above function is given below for better undestanding:
Step 1:
Initialize count variable with 0
Step 2:
Initialize a node pointer, current = headPointer of the list.
Step 3:
Perform the following tasks while current pointer is not NULL
i) current = current -> next
ii) count++;
Step 4:
Return count value which is the size of the linkedList.
/*NOTE: If you want this in a different way, please let me know through comments; I will surely revert back to you.*/
/*Hope this will help you. Thank you.*/
12
14
10
23
17
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.