Stacks October 25 2018
On “Implementing a Stack with a Singly Linked List”
In designing such an implementation, we need to decide if the top of the stack is at the front or back of the list. There is clearly a best choice here, however, since we can insert and delete elements in constant time only at the front. With the top of the stack stored at the front of the list, all methods execute in constant time.
The Adapter Pattern
One general way to apply the adapter pattern is to define a new class in such a way that it contains an instance of the existing class as a hidden field, and then to implement each method of the new class using methods of this hidden instance variable. By applying the adapter pattern in this way, we have created a new class that performs some of the same functions as an existing class, but repackaged in a more convenient way.
a stack can be used as:
- a general tool to reverse a data sequence (due to how last in first out works and all)
- mathing delimiters in an expressions
- matching tags in a markup language
- navigation (browsers, ui, back/forward)
important task when processing arithmetic expressions is to make sure their delimiting symbols match up correctly. We can use a stack to perform this task with a single left-to-right scan of the original string.
If the length of the original expression is n, the algorithm will make at most n calls to push and n calls to pop.
Eh, why not queues too then
Another fundamental data structure is the queue. It is a close “cousin” of the stack, but a queue is a collection of objects that are inserted and removed according to the first-in, first-out (FIFO) principle. That is, elements can be inserted at any time, but only the element that has been in the queue the longest can be next removed.
There are many other applications of queues
Stores, theaters, reservation centers, and other similar services typically process customer requests according to the FIFO principle. A queue would therefore be a logical choice for a data structure to handle calls to a customer service center, or a wait-list at a restaurant.
a queue can be used
- by like your reservation systems
- like on limited resources (resource allocation… a… reservation system)
- web servers serving requests
- a network printer with a printer queue
queue abstract data type defines a collection that keeps objects in a sequence, where element access and deletion are restricted to the first element in the queue, and element insertion is restricted to the back of the sequence
Never noticed the sequence word in the definition of a queue before — even if intuitively used it. See how important definitions and terminology is?
The queue ADT also includes the following accessor methods (with first being analogous to the stack’s top method)
See how natural the transition from a stack to a queue is when you connect things?
See you next time