Stacks：練習問題

A programmer is choosing how to implement a Stack ADT. They decide to use a dynamic data structure rather than a static one. Which of the following is a potential disadvantage of using a dynamic data structure in this context?

Consider a stack implemented using a static array of size 5. Currently, the stack pointer points to index 4 (the last valid index). If a push operation is attempted, what condition is triggered?

When a subroutine is called, a stack frame is created. According to the AQA specification, what are the three primary types of data stored within this stack frame?

Which stack operation returns the value of the top element without removing it from the data structure?

A programmer needs to evaluate the expression \(12 + (3 \times 4)\) using a Stack. They first convert it to Reverse Polish Notation (RPN). What is the sequence of push and pop operations required to evaluate the resulting RPN: 12 3 4 * +?

A stack is used to reverse the order of characters in a string. If the string "AQA" is pushed onto the stack character by character from left to right, what will be the result of three consecutive pop operations?

During a Depth-First Search (DFS) on a graph, a stack is used to keep track of vertices. If the algorithm visits a vertex that has no unvisited neighbors, what specific stack operation is performed to continue the search?

When implementing a stack frame in memory for a recursive subroutine call, name three specific items that are stored on the stack to manage the execution state.

A stack is an Abstract Data Type (ADT) that follows the LIFO principle.

(a) Describe the difference between the push and pop operations.
(b) What is the purpose of a peek (or top) operation?
(c) Explain the condition known as stack overflow and when it occurs.

An expression tree is a specific type of binary tree. For the algebraic expression: \( (5 + 3) \times (8 - 2) \):

a. Determine the result of a Post-order traversal of the corresponding expression tree. (2 points)
b. Explain how a Stack is used to evaluate the resulting Reverse Polish Notation (RPN) from part a. (3 points)
c. Why does RPN eliminate the need for parentheses in complex calculations? (1 point)