Show Stacks.A stack is a collection that is based on the last-in-first-out (LIFO) policy. By tradition, we name the stack insert method push() and the stack remove operation pop(). We also include a method to test whether the stack is empty, as indicated in the following API:
Array implementations of stacks.Representing stacks with arrays is a natural idea. In particular, we maintain an instance variable n that stores the number of items in the stack and an array items[] that stores the n items, with the most recently inserted item in items[n-1] and the least recently inserted item in items[0]. This policy allows us to add and remove items at the end without moving any of the other items in the stack.
Linked lists.A singly linked list comprises a sequence of nodes, with each node containing a reference (or link) to its successor. By convention, the link in the last node is null, to indicate that it terminates the list. With object-oriented programming, implementing linked lists is not difficult. We define a class for the node abstraction that is recursive in nature:A Node object has two instance variables: a String and a Node. The String is a placeholder in this example for any data that we might want to structure with a linked list (we can use any set of instance variables); the instance variable of type Node characterizes the linked nature of the data structure.
Implementing stacks with linked lists.Representing stacks with linked lists is a natural idea. In particular, we maintain an instance variable first that stores a reference to the most recently inserted item. This policy allows us to add and remove items at the beginning of the linked list without accessing the links of any other items in the linked list.
Queue.A queue supports the insert and remove operations using a first-in first-out (FIFO) discipline. By convention, we name the queue insert operation enqueue and the remove operation dequeue, as indicated in the following API:
Generics.We have developed stack implementations that allows us to build a stack of one particular type, such as String. A specific mechanism in Java known as generic types enables us to build collections of objects of a type to be specified by client code.
Autoboxing.We have designed our stacks to be generic, so that they objects of any type. The Java language features known as autoboxing and unboxing enable us to reuse generic code with primitive types as well. Java supplies built-in object types known as wrapper types, one for each of the primitive types: Boolean, Integer, Double, Character, and so forth. Java automatically converts between these reference types and the corresponding primitive types so that we can write code like the following:
Iteration.Sometimes the client needs to access all of the items of a collection, one at a time, without deleting them. To maintain encapsulation, we do not want to reveal the internal representation of the queue (array or linked list) to the client. To accommodate this design pattern, Java provides the foreach statement. You should interpret the following for statement in the following code fragment as for each string s in the collection, print s.
Implementing a collection that supports iteration in this way requires implementing Java's java.util.Iterator and java.util.Iterable interfaces. See the textbook for details. Stack and queue applications.Stacks and queues have numerous useful applications.
Exercises
Linked-List Exercises
Creative Exercises
Web Exercises
|