In this post I will discuss two basic data storage
structure: the Stack and the Queue.
These data structure are used mainly to carry out some task
rather than actually storing data in system. These are programmer’s tool.
Stack and Queues are more abstract entities
than array and many other data storage structures. They are defined primarily
by their interface. Some set of operations are exposed via the interface, which
can be carried out on them.
Stacks
A Stack allows access to last item only. Stack is analogous
to disc cake box. You can only take disc which is on the top. In Stack, last item inserted is the first item to be removed (LIFO)
Following operations can be carried out on Stack :-
- Push – (This insert the data. Data is inserted at the top of the Stack)
- Pop – (This deletes the data from the Stack and return the value.)
- Peek – (This just sneak and return the value at the top of the Stack)
- Size – (Returns the current size of the Stack)
The underlying implementation of Stack is either array or
link list. We will discuss linklist in separate post.
Java implementation of Stack and its interface operations.
class StackImpl
{
private int maxSize; // size of stack array
private long[] stackArray;
private int top; // pointer to the top item
public StackImpl(int s)
{
maxSize = s;
stackArray = new long[maxSize];
top = -1;
}
public void push(long item)
{
stackArray[++top] = item;
}
public long pop()
{
return stackArray[top--];
}
public long peek()
{
return stackArray[top];
}
}
Queue
In Queue,
item first inserted is the first item to be removed (FIFO). This is analogous to line
in front of movie ticket counter. There
are various queue doing their job in our system, like print request queue. In
Queue, items are removed from front and inserted at rear.
Following
functionalities are supported by Queue:-
- Insert - (To insert an item at the rear)
- Remove - (To get an item from front and then delete it from Queue)
- Peek - (To sneek and get the value at front)
- Size - (Returns the size of the Queue)
The
underlying implementation of Queue is also either array or linked list.
Java
implementation of Queue
class QueueImpl
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
public QueueImpl(int s)
{
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
public void insert(long j)
{
if(nItems != maxSize)
{
queArray[++rear] = j;
nItems++;
}
}
public long remove()
{
long temp = -99999;
if(nItems != 0)
{
long temp = queArray[front++];
nItems--;
}
return temp;
}
public long peek()
{
return queArray[front];
}
public int size()
{
return nItems;
}
}
Other
variations of Queue are Circular Queue, Deques and Priority Queue.
Circular
Queue
To avoid
the problem of not being able to insert data in Queue even when it is not full,
the front and rear wraps around to the beginning of array. This special
implementation of Queue is Circular Queue.
Deque
A Deque
is a Double ended queue. Items can be inserted and deleted at either end. A Deque
provides a more versatile data structure than Stack and Queue. It can be used
as Stack and Queue depending upon requirement.
Priority
Queue
Priority
Queue is more specialized data structure than Stack and Queue. Items are
ordered by key in Priority Queue as opposed to Queue in which items are not
ordered. Items are inserted in proper
position in Priority Queue. All other functionality remains same as it is in
Queue.
No comments:
Post a Comment