# Stack and Queue

## Appendix

### Stack

Stack is an application of linear data structure, items in the stack follow the “First In First Out” pattern.

#### 1. Array implementation

• Constructor
• `node()`: object composes stack;
• `stack()`: FIFO lined list;
• method
• `push(item A)`: add item A on stack;
• `pop()`: return the item on the top of stack
• `isEmpty()`: return true if N = 0;
``````public class Stack<item extends Comparable<? super item>>{

private class node<item extends Comparable<? super item>>{
public node() {};
public item item;
public node next;
}

private node first;
private int N;

public Stack(){
this.first = null;
this.N =0;
}

public boolean isEmpty(){
return N == 0;
}

public void push(item A){
node oldfirst = first;
first = new node();
first.item = A;
first.next = oldfirst;
N++;
}

public item pop(){
item out = first.item;
first = first.next;
N--;
return out;
}

}
``````

### Queue

Queue is an application of linear data structure, items in the Queue follow the “First In Last Out” pattern.

#### 1. Single-way Queue(Array)

Create a fixed sized array as a container of Queue and following the FILO pattern.

``````public class Queue<item>{
private int N;
private item[] Q;
private int front = rear = -1;

public Queue(int size){
Q = new item[size];
}

public int capacity(){
return Q.length;
}

public boolean isEmpty(){
return front == rear == -1;
}

public boolean isFull(){
return (rear == size-1 && front == 0) ||(front == rear+1);
}

public void enqueue(item a){
if(isFull()) throw new IndexOutOfRange("Queue is Full !!");
if(rear == size-1 && front != 0){
rear = -1;
}
Q[++rear] = a;
if(front == -1){
front = 0;
}
}

public item dequeue(){
if(isEmpty()) throw new IndexOutOfRange("Queue is empty !!");
item out = Q[front];
if(front == size){
front = 0;
}
if(front-1 == rear){
front = rear = -1;
}
}
}

``````

• Constructor
• `node()`: object composes stack;
• `queue()`: FIFO lined list;
• method
• `enqueue(item A)`: put item in line;
• `dequeue()`: return the LAST item in queue;
• `isEmpty()`: return true if N = 0;
``````public class queue<item extends Comparable<? super item>>{
private class node<item extends Comparable<? super item>>{
public node() {};
public item item;
public node next;
}

private node first;
private node last;
private int N;

public queue(){
this.N =0;
}

public boolean isEmpty(){
return N == 0;
}

public void enqueue(item A){
Node oldlast = last;
last = new node();
last.item = A;
last.next = null;
//very important !!!!!! it will give the value to the first node//
if(isEmpty()) {first = last;}
else          {oldlast.next = last;}
N++;
}

public item dequeue(){
item out = first.item;
first = first.next;
if(isEmpty()){last = null;}
N--;
return out;
}
}
``````