The code for this part of the lecture can be found here.
So far, we have used data structures such as Lists and ArrayLists
that don't define the order in which data is added and removed form the structure
On the other hand, stacks and queues precisely determine the order in which elements are added and removed.
An easy way to understand the nature of a stack is to think of a bounce of coins, one on top of the other. We can only add a new coin on top of the others and we can only remove the coin on the top. So a stack is a data structure in which all insertions and deletions are made at one end, called the top. This is last-in-first-out(LIFO) access policy. The first element to be removed is the last added one.
On the contrary, a queue looks more like a line of customers in front of a cashier. New customers are added at the end of the line and the customer in the front row is the first to be served and leave the line. So a queue is a data structure in which all insertions take place at one end, the rear, while all deletions take place at the other end, the front. This is first-in-first-out(FIFO) access policy. The first element to be removed is the one that was added first.
The difference between the two structures can be made clearer using an example: The restrictions on a stack imply that if the elements A,B,C,D,E are added to the stack, in that order, then the first element to be removed is E. While in a queue, if elements were added in the same order as before, the first to be removed would be A.
Queues and stacks are defined as a way to access a set of datum. Their definitions don't specify how the structures are implemented. The definitions really are an interface rather than a complete description of how to build the structures. The implementation is something that the programmer is free to decide, as long as he/she respects the constraints imposed.
Let's see how we can build stacks and queues inJava.
A first approach would be to use Lists:
class Stack1< T > {
AList alist;
Stack1(){
this.alist=new MtList< T >();}
void add(T t){
this.alist= new ConsList< T >(t,alist);
}
T remove(){
T temp=((ConsList< T >)this.alist).first;
this.alist =((ConsList< T >)this.alist).rest;
return temp;
}
}
The most important part is how we define the add and remove methods. Since Lists offer a single access point
to their contents, the first, we can use that as our top. We always add at the beginning of the list and remove the first element.
Thus we respect the LIFO policy.
Another approach would be to use ArrayLists:
class Stack2< T >{
ArrayList< T > arlist;
Stack2(){
this.arlist=new ArrayList< T >();
}
void add(T t){
this.arlist.add(t);
}
T remove(){
return this.arlist.remove(this.arlist.size()-1);
}
}
The most important part again is how we define the add and remove methods.
ArryLists offer a random access point
to their contents, the one pointed by the index. We can choose as our top the element of index 0.
We always add at the beginning of the ArrayList and remove the first element. Thus we respect the LIFO policy.
A first approach to implement queues would be to use ArrayLists:
class Queue1< T >{
ArrayList< T > arlist;
Queue1(){
this.arlist=new ArrayList< T >();
}
void add(T t){
this.arlist.add(t);
}
T remove(){
return this.arlist.remove(0);
}
}
ArryLists offer a random access point
to their contents, the one pointed by the index. We can choose as our front the element of index 0 and as our rear the element of index n-1,
where n the size of the ArrayList. We always add at the end of the ArrayList and remove the first element.
Thus we respect the FIFO policy.
Another approach would be to use Lists. Unfortunately Lists are not powreful enough to implement a queue. A List
offers only one access point to its contents and serial access to the rest of the elements in it. To implement a queue, we need two access points:
the front and the rear.
Instead of using a List we can use a variant called doubly-linked List:
/*
+----------+
| DList |<--------------------+
+----------+ |
+----------+ |
| |
/ \ |
--- |
| |
--------------------------- |
| | |
+-------------+ +-------------------+ |
| DMTList | | DConsList | |
+-------------+ +-------------------+ |
+-------------+ +---| DList previous | |
| | T Data | |
+---| DList next | |
| +-------------------+ |
+--------------------------+
*/
The main difference between a List and a doubly-linked List is that an element of a doubly-linked List
contains a link not only to the elements that are after
it in the structure, but also to the previous elements. So we can traverse the structure both ways by simply following the links.
This is very convenient because, if the programmer keeps track of the first and the last element of the structure, it is easy to
remove and add elements to any side of the structure .
To add an element at the end of the DList, we just need to set the new element as the next
of the last element and the last element as the previous of the new element.
The newly added element becomes, off course, the new last element.
To remove an element form the beginning of the DList, we just need to set
the next element of the first of the DList as the new first element of our DList.
The previous of the new first element of the DList will be the empty DList.
If we choose as our front the first element of our DList and as our rear the last element of the DList,
we can always add at the end of the DList and remove the first element. Thus we respect the FIFO policy.
List.
class Queue2< T > {
DList< T > dlist;
DList< T > last;
Queue2(){
this.dlist=new DMtList< T >();
this.last=this.dlist;
}
boolean isEmpty(){
return this.dlist instanceof DMtList;
}
void add(T t){
if (this.isEmpty())
{
this.last=new DConsList< T >(t,new DMtList< T >(),new DMtList< T >());
this.dlist=this.last;
}
else
{
DList node=new DConsList< T >(t,this.last,new DMtList< T >());
((DConsList< T >)this.last).next=node;
this.last=node;
}
}
T remove(){
T temp=((DConsList< T >)this.dlist).data;
this.dlist = ((DConsList< T >>)this.dlist).next;
if (!this.isEmpty())
{
((DConsList< T >)this.dlist).previous = new DMtList< T >();
}
return temp;
}
}