Exam 3 Flashcards
is one of the most commonly used data structures in computer science
A stack
The stack’s storage policy is:
Last-In, First Out , or LIFO
boolean empty()
Returns true if the stack is empty; otherwise, returns false.
E peek()
Returns the object at the top of the stack without removing it.
E pop()
Returns the object at the top of stack and removes it.
E push (E obj)
Pushes an item onto the top of the stack and returns the item pushed.
a string that reads identically in either direction , letter by letter (ignoring case )
Palindrome
When analyzing arithmetic expressions, it is important to determine whether an expression is:
balanced with respect to parentheses
The problem is further complicated if braces or brackets are used in ________ with _________.
The solution is to use:
conjunction
parentheses
Stacks
PITFALL: attempting to pop an empty stack will throw an ______________ . You can guard against this by either:
EmptyStackexception
testing for an empty stack or catching the exception
Stacks are so common in computing, that Java included a Stack class in its early versions :
import java.util.Stack;
BUT, the Java Stack class extends Vector (a deprecated class which extends AbstractList) ... THEREFORE the class provides methods \_\_\_\_\_\_\_ to Stacks Its use is:
not traditional
no longer recommended
like the stack, is a widely used data structure
The queue
A queue differs from a stack in one important way:
stack is a LIFO list Last-In, First-Out
while a queue a is FIFO list - First-In, First -Out
Operating systems use queues to:
Keep track of tasks waiting for a scarce resource
ensure that the tasks are carried out in FIFO order
Printing queue:
Printing is so much slower than the process of selecting pages to print, so a queue is used
remove() and poll() differ only on what happens when the queue is empty.
remove() removes the entry at the front and return NoSuchElementException
poll() removes the entry at the front and returns null
We use remove()
peek() and element() differ only on what happens when the queue is empty.
peek() returns entry at the front and returns null
element() returns the entry at the front and returns NoSuchElementException
We use peek()
The __________ class provides methods for inserting and removing elements at either end of a linked list, which means all _______ methods can be implemented easily
LinkedList
Queue
The Java ________ class implements the _____ interface
Linkedlist
Queue
