![]() ![]() Regardless of the type of the underlying data structure, a queue must implement the same functionality. The underlying structure for a queue could be an array, a Vector, an ArrayList, a LinkedList, or any other collection. In the standard library of classes, the data type queue is an adapter class, meaning that a queue is built on top of other data structures. ![]() ![]() In a stack we remove the item the most recently added in a queue, we remove the item the least recently added. The difference between stacks and queues is in removing. The picture demonstrates the FIFO access. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. In the queue only two operations are allowed enqueue and dequeue. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. An excellent example of a queue is a line of students in the food court of the UC. QueuesĪ queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. See ListStack.java for a complete implementation of the stack class. Linked List-based implementation provides the best (from the efficiency point of view) dynamic stack implementation. In a dynamic stack abstraction when top reaches capacity, we double up the stack size. See ArrayStack.java for a complete implementation of the stack class. In a fixed-size stack abstraction, the capacity stays unchanged, therefore when top reaches capacity, the stack object throws an exception. We say that a stack is empty when top = -1, and the stack is full when top = capacity-1. The variable top changes from -1 to capacity - 1. In an array-based implementation we maintain the following fields: an array A of a default size (≥ 1), the variable top that refers to the top element in the stack and the capacity that refers to the array size. Constant time means that there is some constant k such that an operation takes k nanoseconds of computational time regardless of the stack size. The following picture demonstrates the idea of implementation by composition.Īnother implementation requirement (in addition to the above interface) is that all stack operations must run in constant time O(1). This is achieved by providing a unique interface:public interface StackInterface Regardless of the type of the underlying data structure, a Stack must implement the same functionality. The underlying structure for a stack could be an array, a vector, an ArrayList, a linked list, or any other collection. In the standard library of classes, the data type stack is an adapter class, meaning that a stack is built on top of other data structures.
0 Comments
Leave a Reply. |