Lists Stacks and Queues Flashcards
1
Q
Running time of insert of array
A
O(N)
2
Q
Running time of delete of array
A
O(N)
3
Q
Running time of insert/delete at end of array
A
O(1)
4
Q
Running time of trimToSize() for array
A
O(N)
5
Q
What are the 4 applications for Stacks
A
- Balancing symbols
- Postfix expressions
- Infix to Postfix conversion
- Method calls
6
Q
What is the logic to reading a postfix expression using a stack
A
Push numbers until you see an operator, then pop 2 numbers, use the operator against them, and then push the result onto the stack
7
Q
What is the logic to converting postfix to infix using a stack
A
- Always push numbers onto output
- Only push operators onto the stack, and pop higher priority operators into the output (except open brackets) before pushing onto the stack
- For closing brackets, pop all operators until the opening bracket is encountered, and do not push the brackets to the output
8
Q
What kind of queue can go from end to front
A
Circular Queue
