Transcript Stacks(Continued) and Queues

Stacks (Continued) and Queues
• Array Stack Implementation
• Linked Stack Implementation
• The java.util.Stack class
• Queue Abstract Data Type (ADT)
• Queue ADT Interface
• Queue Design Considerations
• The java.util.Queue interface
Reading L&C 3rd : 4.4, 4.6, 5.1 2nd: 7.1-7.8
1
Array Stack Implementation
• We can use an array of elements as a stack
• The top is the index of the next available
element in the array
top
Object of type T
T [ ] stack
Object of type T Object of type T
null
2
Array Stack Implementation
• push – O(n)
public void push (T element)
{
if (size() == stack.length)
expandCapacity();
stack [top++] = element;
}
• worst case: O(n)
• How about the average case: almost
constant time.
3
Array Stack Implementation
• pop() – O(1)
public T pop() throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException();
T result = stack[--top];
stack[top] = null; // removes “stale” reference
return result;
}
• The “stale” reference stored in stack[top]
would prevent garbage collection on the
object when the caller sets the returned
4
reference value to null – ties up resources
Linked Stack Implementation
• We can use the same LinearNode class
that we used for LinkedSet implementation
• We change the attribute name to “top” to
have a meaning consistent with a stack
count
Object of type T
top
LinearNode next;
T element;
LinearNode next;
T element;
Object of type T
Object of type T
null
5
Linked Stack Implementation
• push – O(1)
public void push (T element)
{
LinearNode<T> temp = new LinearNode<T>(element);
temp.setNext(top);
top = temp;
count++;
}
• Note the difference between the stack push
method and the LinkedSet add method
– There is no check for already present or not
6
Linked Stack Implementation
• pop – O(1)
public T pop () throws EmptyStackException
{
if (isEmpty()) throw new EmptyStackException();
T result = top.getElement();
top = top.getNext();
count--;
return result;
}
• Note the difference between the stack pop
method and the LinkedSet remove method
– There is no specified target as a parameter
7
The java.util.Stack Class
• The java.util.Stack class is part of the Java
collections API.
• It is a subclass of the java.util.Vector class
which is a subclass of java.util.AbstractList
• java.util.Stack inherits some methods from
its superclasses that are inappropriate for
a stack collection – a bad design decision!
• A good programmer will avoid using those
methods on a Stack object
8
The java.util.Stack Class
• java.util.Stack has a search method that
returns the distance from the top of the
stack to the first occurrence of that object
on the stack, e.g. search returns 1 for the
top element of the stack
• If the object is not found, search returns -1
• The search method is O(n)
• Does this method violate the principles of
a stack as a data structure?
9
Queue Abstract Data Type
• A queue is a linear collection where the
elements are added to one end and
removed from the other end
• The processing is first in, first out (FIFO)
• The first element put on the queue is the
first element removed from the queue
• Think of a line of people waiting to be
served at RMV.
10
A Conceptual View of a Queue
Rear of Queue
(or Tail)
Adding an Element
Front of Queue
(or Head)
Removing an Element
11
Queue Terminology
• We enqueue an element on a queue to add one
• We dequeue an element off a queue to remove one
• We can also examine the first element without
removing it
• We can determine if a queue is empty or not and
how many elements it contains (its size)
• The L&C QueueADT interface supports the above
operations and some typical class operations such
as toString()
12
Queue ADT Interface
<<interface>>
QueueADT<T>
+
+
+
+
+
+
enqueue(element : T) : void
dequeue () : T
first() : T
isEmpty () : bool
size() : int
toString() : String
13
Queue Design Considerations
• Although a queue can be empty, there is no
concept for it being full. An implementation
must be designed to manage storage space
• For first and dequeue operation on an
empty queue, this implementation will throw
an exception
• Other implementations could return a value
null that is equivalent to “nothing to return”
14
Queue Design Considerations
• No iterator method is provided
• That would be inconsistent with restricting
access to the first element of the queue
• If we need an iterator or other mechanism
to access the elements in the middle or at
the end of the collection, then a queue is
not the appropriate data structure to use
15
The java.util.Queue Interface
• The java.util.Queue interface is in the Java
Collections API (extends Collection)
• However, it is only an interface and you
must use an implementing class
• LinkedList is the most commonly used
implementing class
• For a queue of type objects:
Queue<type> myQueue = new LinkedList<type>();
16
The java.util.Queue Interface
• The names of the methods are different
• Enqueue is done using:
boolean offer(T element) // returns false if full
• Dequeue is done using either:
T poll()
T remove()
// returns null value if empty
// throws an exception if empty
• Peek is done using either:
T peek()
// returns null value if empty
T element() // throws an exception if empty
17