Stack
Stack Introduction
Imagine a stack of plates on a table. After the first one was put on the table, the next one was put on the first one; the third one was put on the second; and so on, until a satisfactory number was attained. To remove the plates from the table, one-by-one, the last one put on the top is removed first; then the last-but-one is removed next; then the one next from the top removed; and so on. So, the last plate to be put on the pile is the one to be removed first. In that sense, all the plates are removed in a last-in_first-out order. Last-In_First-Out order is abbreviated, LIFO.
A stack in Java is a LIFO data structure. Such a structure keeps objects of the same type. The element at the first index, is the element at the top. A stack should have at least the following three methods:
push: This adds a new element on top of the stack.
pop: This removes the element that is at the top of the stack.
peek: This reads out, without removing, the element at the top.
In Java, the stack class is in the java.util.* package, which has to be imported.
In Java, the stack has one constructor and five methods, all of which are explained below:
Java Stack Construction
The syntax for the constructor of an empty stack, is:
public Stack()
The following statement constructs an empty stack called st:
Methods of Java Stack
public E push(E item)
This adds an item onto the top of the stack. Illustration:
st.push('A'); st.push('B'); st.push('C'); st.push('D'); st.push('E');
public E pop()
This removes the item at the top of the stack and returns it. Illustration:
st.push('A'); st.push('B'); st.push('C'); st.push('D'); st.push('E');
char ch1 = st.pop(); char ch2 = st.pop(); char ch3 = st.pop();
char ch4 = st.pop(); char ch5 = st.pop();
System.out.print(ch1); System.out.print(' '); System.out.print(ch2);
System.out.print(' '); System.out.print(ch3); System.out.print(' ');
System.out.print(ch4); System.out.print(' '); System.out.print(ch5);
System.out.println();
The output is:
E D C B A
with items removed in the reverse order in which they were pushed in.
public E peek()
This copies out without removing the item at the top of the stack and returns it. Illustration:
st.push('A'); st.push('B'); st.push('C'); st.push('D'); st.push('E');
char ch1 = st.peek(); char ch2 = st.peek(); char ch3 = st.peek();
char ch4 = st.peek(); char ch5 = st.peek();
System.out.print(ch1); System.out.print(' '); System.out.print(ch2);
System.out.print(' '); System.out.print(ch3); System.out.print(' ');
System.out.print(ch4); System.out.print(' '); System.out.print(ch5);
System.out.println();
The output is:
E E E E E
which also indicates that the top element is copied and not removed by peek().
public boolean empty()
This returns true if the stack is empty, and false otherwise. Illustration:
st.push('A'); st.push('B'); st.push('C'); st.push('D'); st.push('E');
boolean bl = st.empty();
System.out.println(bl);
The output is false because the stack, st is not empty.
public int search(Object o)
This returns the index of the object searched. If the object is not found, -1 is returned. Illustration:
st.push('A'); st.push('B'); st.push('C'); st.push('D'); st.push('E');
int it1 = st.search('A'); int it2 = st.search('B'); int it3 = st.search('C');
int it4 = st.search('D'); int it5 = st.search('E'); int it6 = st.search('F');
System.out.print(it1); System.out.print(' '); System.out.print(it2);
System.out.print(' '); System.out.print(it3); System.out.print(' ');
System.out.print(it4); System.out.print(' '); System.out.print(it5);
System.out.print(' '); System.out.print(it6); System.out.print(' ');
System.out.println();
The output is:
5 4 3 2 1 -1
Stack Conclusion
The stack in Java is a last-in_first-out data structure. It has five methods which include push(), pop() and peek().
Queue
Queue Introduction
Imagine a queue of people in a line, waiting for a product or service. The first person who came is the first to be served. The second person is the second to be served. The third is the third to be served, and so on; until the queue finishes. This is a first-in_first-out scheme, abbreviated FIFO.
A queue in Java is a FIFO data structure. Such a structure keeps objects of the same type. The element at the first index is the element at the top. A queue should have at least the following three methods:
enqueue: This adds a new element at the back of the queue.
dequeue: This removes the element at the front of the queue.
peek: This reads out, without removing, the first element.
In Java, the queue has no constructor and six methods, three of which are explained below:
Java Queue Implementation/Instantiation
The Queue in Java is an interface. Java Stack class instantiates a stack object while Java Queue Interface implements a class. An object is still to be instantiated from the class. Fortunately, Java has already implemented many classes from the Queue Interface. The programmer should choose the one most appropriate to him among the lot. The one chosen for this article is LinkedList. LinkedList has two constructors, but only one will be explained below. The LinkedList class has many methods, but only three will be explained below.
In Java, the LinkedList class is in the java.util.* package which has to be imported.
A syntax to construct a queue from the LinkedList class, is:
public LinkedList()
The following statement constructs an empty queue called, qu:
Some Methods of LinkedList Queue
public boolean add(E e)
This adds an item at the back of the queue. Illustration:
qu.add('A'); qu.add('B'); qu.add('C'); qu.add('D'); qu.add('E');
public E remove()
This removes the item in front of the queue, and returns it. Illustration:
qu.add('A'); qu.add('B'); qu.add('C'); qu.add('D'); qu.add('E');
char ch1 = qu.remove(); char ch2 = qu.remove(); char ch3 = qu.remove();
char ch4 = qu.remove(); char ch5 = qu.remove();
System.out.print(ch1); System.out.print(' '); System.out.print(ch2);
System.out.print(' '); System.out.print(ch3); System.out.print(' ');
System.out.print(ch4); System.out.print(' '); System.out.print(ch5);
System.out.println();
The output is:
A B C D E
confirming that this is a FIFO data structure.
public E peek()
This copies out without removing the item at the front of the queue and returns it. Illustration:
qu.add('A'); qu.add('B'); qu.add('C'); qu.add('D'); qu.add('E');
char ch1 = qu.peek(); char ch2 = qu.peek(); char ch3 = qu.peek();
char ch4 = qu.peek(); char ch5 = qu.peek();
System.out.print(ch1); System.out.print(' '); System.out.print(ch2);
System.out.print(' '); System.out.print(ch3); System.out.print(' ');
System.out.print(ch4); System.out.print(' '); System.out.print(ch5);
System.out.println();
The output is:
A A A A A
which also indicates that the front element is copied and not removed by peek().
Queue Conclusion
The queue in Java is a first-in_first-out data structure. It has many methods which include add(), remove() and peek().
General Conclusion
The stack and queue are data structures. The stack in Java is a last-in_first-out data structure. It has five methods which include push(), pop() and peek(). The queue in Java is a first-in_first-out data structure. It has many methods which include add(), remove() and peek().
