Below are few quotations i found from this book from the next 3 chapters (11-12-13).
1) The only object that may be accessed from a stack is the most recent object placed onto the stack. We refer to this ordering as last in, first out.
2) In the fixed stack implementation ArrayStack, an internal array field data is used to hold the objects that comprise the stack.
Example Of ArrayStack
/** A fixed stack implementation
*/
public class ArrayStack implements Stack {
// Fields
private int capacity = 101; // Default value
private Object [] data; // Holds the information in the stack
private int top =0; // Tracks last element inserted
// Constructors
public ArrayStack () {
this(101);
}
public ArrayStack (int capacity) {
this.capacity = capacity;
data = new Object[capacity + 1];
}
// Commands
public void push (Object item) {
top++;
try {
data[top] = item;
}
catch (ArrayIndexOutOfBoundsException ex) {
top--;
throw new ArrayIndexOutOfBoundsException(
''Stack capacity exceeded." );
}
}
public void pop () {
if (isEmpty())
throw new NoSuchElementException("Stack is empty." );
else {
data[top] = null;
top--;
}
}
public void makeEmpty () {
top = 0;
}
// Queries
public Object top () {
if (isEmpty())
throw new NoSuchElementException(''Stack is empty." );
else
return data[top];
}
public boolean isEmpty () {
return top == 0;
}
public int size () {
return top;
}
static public void main(String[] args) {
ArrayStack myStack = new ArrayStack(5);
myStack.push(new Integer(1));
myStack.push(new Integer(2));
myStack.push(new Integer(3));
System.out.println("myStack.size() = " + myStack.size();
myStack.pop();
System.out.println("myStack.size() = " + myStack.size
());
System.out.println ("myStack.top() = " + myStack.top());
}
}
/* Output:
myStack.size() = 3
myStack.size() = 2
myStack.top() = 2
*/
3) The LinkedStack implementation of Stack is a dynamic stack implementation. The storage associated with such a stack grows and shrinks as objects are added and removed from the stack.
The information contained in a LinkedStack is contained within a Node class. This class may be defined as a stand-alone class or as an inner class within class LinkedStack. We choose to make Node an inner class since it is dedicated exclusively to serve class LinkedStack.
Inner class Node contains two fields, item (which contains the object being stored) and next (a reference to the next Node in the stack)
A linked-list structure consists of a sequence of nodes with each node containing a reference or pointer to the next node in the sequence. If we draw such a linked-list structure from left to right, the most recent object pushed onto the stack would be the leftmost node and the oldest object to have been pushed onto the stack would be the rightmost node. Each time we add a node (command push ) to the LinkedStack this node becomes the first node in the linked-list structure. The oldest node is linked to null, which serves as a terminator of the linked list.
4) A queue is an information structure in which the first item that is inserted is the first that is available (first in, first out).This is in contrast to a stack in which the first item that is available is the last item inserted (first in, last out).
5) A stack is one of the simplest and perhaps most widely used container types. Many software applications require the logical equivalent of piling objects on top of each other.
6) The push command is used to add a new object to a stack. The pop command is used to remove the object on the top of the stack. The top query returns the object on top of the stack without removing it.
7) In the fixed stack implementation ArrayStack, an array field data is used to hold the objects that comprise the stack.
8) The LinkedStack implementation of Stack is a dynamic stack implementation. The storage associated with such a stack grows and shrinks as objects are added and removed from the stack.
9) Dynamic structures offer more flexibility since their capacity does not have to be known in advance. The price that must usually be paid for this flexibility is efficiency. Fixed structures generally perform faster than dynamic structures.
10) A queue is an information structure in which the first item that is inserted is the first that is available (first in, first out).This is in contrast to a stack, in which the first item that is available is the last item inserted (first in, last out).
11) Some lists allow items to be stored in any order whereas others require a sequential ordering of their data. The simplest list allows the addition of objects, removal of objects, and access to objects only at two ends, front and rear. An ''indexable" list extends a simple list by allowing the insertion of objects, removal of objects, and access of objects at a particular index. A "positionable" list extends a simple list by allowing the addition of objects, removal of objects, and access to objects before or after a specified object in the list. Finally, an "ordered" list extends SearchTable and requires that its elements be comparable. A strict ordering relationship is maintained among the elements of an ordered list. This is true in a search table.
12) A list is a useful and widely used container abstraction. Lists come in various flavors so we really have a family of list abstractions.
13) The simplest list allows the addition of objects, removal of objects, and access to objects only at two ends, front and rear.
14) An indexable list extends a simple list by allowing the insertion of objects, removal of objects, and access of objects at a particular index.
15) A positionable list extends a simple list by allowing the addition of objects, removal of objects, and access to objects before or after a specified object in the list.
16) An ordered list extends SearchTable and requires that its elements be comparable. A strict ordering relationship is maintained among the elements of an ordered list.
17) A Dequeue is an implementation of a simple List. Objects may be added, removed, or accessed at the front or the rear of such a list.
About the Author
Richard Wiener is Associate Professor of Computer Science at the University of Colorado at Colorado Springs and Editor-in-Chief of The Journal of Object-Oriented Programming. He is the author or co-author of twenty-one textbooks and professional books. In 1983 Richard Wiener received the Outstanding Teacher of the Year Award from the University of Colorado at Colorado Springs. His areas of research include object-oriented software development,simulated annealing and genetic algorithms, time series, and applied statistics.
Lewis J. Pinson is President of CIC and Associate Professor of Computer Science at the University of Colorado at Colorado Springs. His areas of expertise include computer software development, object-oriented problem solving,genetic algorithms, and complexity studies. He develops and presents training courses and intensive short courses and workshops on object-oriented problem solving and object-oriented languages. Dr. Pinson has authored or co-authored eight books.
No comments:
Post a Comment