Universidad Carlos III de Madrid

The Java execution stack stores the invocations to the methods that are being executed and allows, especially when an exception is launched, to make a follow-up of the calls made till that moment, including the line number where the error appears. To obtain this stack, a call to the printStackTrace() method over the Exception object must be made. The following printouts represent a possible execution stack trace produced when certain file is not found.

java.io.FileNotFoundException: fred.txt
   at java.io.FileInputStream.
              <init>(FileInputStream.java)
   at java.io.FileInputStream.
              <init>(FileInputStream.java)
   at ExTest.readMyFile(ExTest.java:19)
   at ExTest.main(ExTest.java:7)						

One of the options of the Java machine is the -Xss option, which allows to establish the stack size for every execution thread. Java has two stacks; one for Java code and one for C code. This option establishes the maximum stack size that can be used for the Java code in the execution of a program thread. The default size of this stack is 512 kilobytes (-Xss512k).

The Java API provides a Stack class. The Stack methods are push, pop, peek, empty and search. However, the Stack class extends Vector and is slower than it needs to be; like Vector, its use is no longer in vogue and can be replaced with array classes or with classes which implement the java.util.List interface.

int [] arr = new int[10];
					

Suppose that we really need 12 items instead of 10. We can expand the array this way:

int[] temporal = arr;//Save reference to arr
arr = new int[12];   //Have arr reference more memory
for(int i=0;i<10;i++)//Copy the old data over
  arr[i] = temporal[i]; 
temporal = null;     //Unreference the temporal array
					

At a first glance, this is an expensive operation. If, for instance, this array expansion is in response to reading input, it would be inefficient to reexpand every time we read a few elements. Thus, when array expansion technique is implemented, we always make it some multiplicative constant times as large. For instance, we might expand it to be twice as large; the array from N items might be converted into an array of 2N items.

This class is the ArrayList class, which you should use instead of Vector when you want to implement dynamic arrays. The basic idea is that an ArrayList maintains not only a size, but also a capacity; the capacity is the amount of memory that it has reserved. The capacity of the ArrayList is really an internal detail (not something you need to worry about). The add method adds a new item into the array at the appropriate position. This is a trivial operation if capacity has not been reached. If it has, the capacity is automatically expanded ,using the dynamic expansion technique. Because indexing via [] is reserved only for basic arrays; we have to use the method get to access the ArrayList items.

The ArrayList is appropriate if insertions are performed only at the high end of the array (using add). This is because the ArrayList doubles the internal array capacity if an insertion at the high end would exceed the internal capacity. Although this gives good Big-Oh performance, especially if we add a constructor that allows the caller to suggest initial capacity for the internal array, the ArrayList is a poor choice if insertions are not made at the end, because then we must move items out of the way.

In a linked list, we store items noncontiguosly rather than in the usual contiguous array. To do this, we store each object in a node that contains the object and a reference to the next node in the list. In this scenario, we maintain references to both the first and last node in the list. These lists are then more efficient to avoid large amounts of data movement.

Access methods of a queue (get and set) are always executed in its ends; elements are extracted from the head and elements are added at the tail. The next element that is extracted is located at the head. To access to an arbitrary element in the queue, the front elements must have been extracted in order first. The java.util package offers the following interface to work with queues, public interface Queue extends Collection, with the following methods to operate with:

Operation      With Exception    Without Exception
--------------------------------------------------------
add            add()              offer()
remove         remove()           poll()
look up        element()          peek(
					

The use of an auxiliary stack allows to invert the elements of a queue in an efficient way, taking advance of the LIFO structure of the stack (Last In - First Out). To do so, we push in the stack all the elements that are dequeued from the queue and, afterwards, we add to the queue the elements of the stack. The code to do this is:

void invert(Queue queue) {
 Stack stack = new Stack();
  while (!queue.empty())
   stack.push(queue.dequeue());
  while (!stack.vacia())
   queue.enqueue(stack.pop())
} 
					

Indeed, the complexity is constant, that is, O(1), because it does not matter the number of elements existing in these structures; the access to them is always at any of both ends, so you don't need to process the rest of the elements. Because of this, if you implement any of these methods with a non-constant complexity, the implementation will be less efficient and it is not recommended.

Every graphic application in Java stores the user interactions (mouse events, keystrokes events, etc.) in an event queue (AWT Event Queue) while they are produced. Meanwhile, a task extracts continuously (in an infinite loop) the queue events, processing them consecutively. This task is called "Event Dispatch Thread" (EVT) and processes the events depending on their types. For example, if the event is a mouse event over a component, the task will invoke the corresponding handler of a mouse event over the component. The event process of the EVT can be explicitly invoked with the SwingUtilities.invokeLater() method or SwingUtilities.invokeAndWait() method.

A double-ended queue allows access (add or remove) at both ends (either head or tail). An stack can be considered as an specialization of a deque and can be implemented by means of extending it. Equivalence between the methods of both structures are shown in the next table:

Stack      Deque
--------------------------
size()     size()
isEmpty()  isEmpty()
top()      last()
push(e)    insertLast(e)
pop()      removeLast()
					

A double-ended queue allows access (add or remove) at both ends (either head or tail). A queue can be considered as an specialization of a deque an can be implemented by means of extending it. Equivalence between the methods of both structures are shown in the next table:

Queue       Deque
--------------------------
size()      size()
isEmpty()   isEmpty()
front()     first()
enqueue(e)  insertLast(e)
dequeue()   removeFirst()
					

A linked list keeps just a reference to the initial node of the list (head) for the implementation. Given a queue implemented with a linked list, adding an element (enqueue()) at the tail has a complexity proportional to the number of elements in the list, that is, O(n). This is the reason why another reference is strongly recommended, at the end of the list (tail) to make the complexity constant, independent of the list size (O(1)).

The use of a circular array in a array-based queue implementation (ArrayQueue) avoids to make a shift of elements when inserting or deleting data, since both ends of the array are joined and, therefore, both operations are of constant complexity O(1). In the case of an array-based stack implementation (ArrayStack), it is not necessary to have a circular array for the insertion or deletion of data; there is no shift of elements in both operations because they are made at the same end of the array and that's why they are also of constant complexity O(1).

In Java, an Iterator offers a mechanism to traverse the elements of a collection, and substitutes the deprecated enumerations (Enumeration). However, both stacks and queues are data structures that "hide" intermediate inner elements and just offer access methods at both ends of them; this is way there is no sense in having an iterator object for them.