Page 1 of 2
- The Associative Array
- The String Object
- The Array object
- A Time Interval Object*
- Collection Object
- Stacks, Queue & Deque
- The Linked List
- A Lisp-like list
- The Binary Tree
- Bit manipulation
- Typed Arrays I
- Typed Arrays II*
* First Draft
The LIFO stack
It is always difficult to know which stack is the most basic but the LIFO or Last In First Out stack is perhaps the most commonly used.
A simple array object already has the two basic methods needed to create a LIFO stack push and pop.
The push method will add any object to the top of the stack and the pop method will remove it. To treat an array as a LIFO stack you simply create an instance and use push and pop.
var stack=new Array();
If you try this out you will see the alerts display "C", "B" and "A". This is the key property of a LIFO stack - it reverses the order of the data you store on it. You pushed A, B and then C byt you got back C, B and then A.
You can use any Array object as a LIFO stack and it is sometimes useful to treat an array as a stack for a while and then go back to working with it as an array. If you really want to create a stack object that can only be used as a stack then you have to encapsulate an Array and expose only the push and pop methods.
If you make the stac Array object private using a closure say then the only operations allowed on Stack are push and pop.
var stack=new Stack();
and again you will see the data retrieved in the order "C", "B", "A".
Notice that while we refer to the "top of the stack" push adds the object to the "end" of the array and pop removes the final element.
That is if the array has three items already stored i.e. array, array and array then push() stores its object in array.
Also notice that if you try to pop a value that doesn't exist i.e. pop an empty stack the result is undefined. You could test for this error in the Stack object and throw an exception or some other error if the user attempts to pop an empty stack.
A typical stack will often allow you to manipulate the stack pointer say or peek at the value on the top of the stack i.e. retrieve it without removing it but these "non-stack" operations are generally not necessary.
Also notice that as you can push and pop any object onto the stack you can use it in very sophisticated ways. For example, if you need to store an object on the stack long with the time it was created you don't need to create a more complex Stack object because you can simply push a composite object:
Also notice that there is no need to worry about problems of enumeration - because you don't naturally ever need to enumerate a stack structure.
The FIFO stack or Queue
The close relative of the LIFO stack is the FIFO - First In First Out stack - also known as the Queue because it mimics the behaviour of a queue in the real world. That is you store an item on the back of the queue and retrieve it from the front.
Once again the Array object provides methods that enable us to create a Queue directly. The unshift method adds an item to the front of the Array. To create a queue we have to remove items from the end of the Array and this we can do using the pop method again.
That is to treat an Array as a queue all we have to do is
var Q=new Array();
If you try this out you will see the data retrieved in the order "A", "B" and "C". That is a queue or a FIFO stack doesn't change the order of the data the items are retrieved in the order that they were stored.
A queue is useful when ever you have data to deal with and not enough time to deal with it all. You simply add the data you can't deal with to the queue and deal when it when you can. The queue ensures that it is dealt with in the order it arrived. Another name for a queue is a buffer.
If you want to create a queue object you can follow the basic idea used for the LIFO stack:
var Q=new Queue();
The methods enqueue and dequeue aren't standard names but they are often used. Another controversy is over whether you join the head or start of the queue ot the tail or end of the queue. It all depends on how you think about it and as long as you get the basic FIFO action it all works.
As in the case of a stack trying to remove something from an empty queue returns undefined. You can also queue complex objects and augment the queue with additional methods to return the number of items in the queue and even the nth item in the queue.
There are more complex types of queue that you can implement but these are less commonly encountered.
For example, the priority queue works int he same way but when you enqueue an item you can also specify its priority. When items are dequeued they are returned in priority order rather than the order that they arrived in. You can implement a priority queue either by keeping the array sorted in priority order or simply search for the value to be returned in an unsorted list.
You can also use more complex data structures to implement a priority queue such as the heap - see a future article for details.