Topic 3 - Stack ADT

Question 1

Give examples of where LIFO is useful.

Answer 1

1) Backtracking in puzzles and games.
2) Browsers - to keep track of pages visited in a browser tab
3) Parenthesis - first closed parenthesis closes the previous open parenthesis
4) Undo operations - keeps track of most recent operations
5) Markup Languages - HMTL, XML, have formatting information (tags) as well as raw text - checks for matching tags
6) Stack calculators - to convert an infix expression to postfix, to make evaluation easier
7) Compilers - convert infix expressions to postfix, to make translation of high-level language such as Java or C to a lower level language easier
8) Call Stack (Runtime Stack) - stores information about the active subroutines of a computer program, used by runtime system when methods are invoked, for a method call / return processing

Question 2

Every collection has a ___?

Answer 2

A set of operations that define how we interact with it, for example:

• add elements
• remove elements
• determine if the collection is empty
• determine the collection’s size

Question 3

Define all the Stack Operations

Answer 3

Push: add an element at the top of the stack
Pop: remove the element at the top of the stack
Peek: examine the element at the top of the stack
isEmpty: determines whether the stack is empty
size: determines the number of elements in the stack
toString: returns a string representation of the stack

Question 4

Define: Stack Abstract Data Type (Stack ADT)

Answer 4

it is a collection of data, together with the operations on that data - we just discussed the operations in previous slides

Question 5

Java has a programming construct called an Interface that___?

Answer 5

that we use to formally define what the operations on a collection are in Java

Question 6

Define Java Interface:

Answer 6

• A list of abstract methods and constant
• must be public
• constants must be declared as final static

Question 7

Define Abstract Method

Answer 7

A method that does not have an implementation ie. it just consists of the header of the method. ex:
return type method name (parameter list)

Question 8

Define: Infix Notation

Answer 8

Operators are between operands: 3+4*2

Parantheses force precedence: (3+4)*2

Question 9

Define: postfix epxression

Answer 9

The operator comes after its two operands

Question 10

Does an application program need to know how the Stack collection is implemented?

Answer 10

No - we are using the Stack collection for its functionality (what); how it is implemented is not relevant

Question 11

The class ArrayStack implements______?

Answer 11

the StackADT interface:
public class ArrayStack implements StackADT

Question 12

constructors are not specified in the Java interface for the StackADT (why not?)

Answer 12

BecauseThe elements of the stack array are of generic type T

Question 13

pop() does what?

Answer 13

Returns value of and deletes top element

Question 14

Can we instantiate anything of a generic type? Ie. create a constructor that creates an instance of a generic type? If, yes, explain. If no, then what do we do instead.

Answer 14

No.

We need to instantiate an element of type Object and cast it into the type T

Question 15

In a Java interface, can we have attributes? Constants? How do you declare each if yes.

Answer 15

No. Yes. Constants must be declared as final static