Page 85 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 3.7 Review Questions

1. Write an algorithm to reverse an input string of characters using a stack.

2. Explain how function calls may be implemented using stacks for return values.
3. What are the advantages of implementing a stack using dynamic memory allocation
method?

4. Trace the execution of infi x-to-postfix algorithm on the following expression.
3 + (23 * 9 / 3 - 67 - (2 * 7) /9)
5. One way to determine if a string of characters is a palindrome is to use one stack and one
queue and to apply the following algorithm strategy:

(a) Put the input string on the stack and the queue simultaneously.
(b) Thus, popping the string from the stack is equivalent to reading it backwards while
deleting the string from the queue is reading it forwards.

6. Write a C program to implement a stack of characters.
7. Explain why we cannot use the following implementation for the method push in our
linked Stack.

Error_code Stack :: push(Stack_entry item)
{
Node new_top(item, top_node);
top_node = new_top;
return success;
}
8. What is wrong with the following attempt to use the copy constructor to implement the
overloaded assignment operator for a linked Stack?
void Stack :: operator = (const Stack &original)
{
Stack new_copy(original);
top_node = new_copy.top_node;
}
How can we modify this code to give a correct implementation?
Answers: Self Assessment

1. (c) 2. (a)
3. (b) 4. (e)
5. (b) 6. (b)
7. LIFO (Last In First Out) 8. Array
9. Dynamic 10. Polish Notation

80 LOVELY PROFESSIONAL UNIVERSITY