Interview(2)Stack and Queue

Interview(2)Stack and Queue

Stack
Last-in-first-out LIFO
Push  put one item into the stack,
Pop    get one item out of the stack

Some popular example will be the browser back and editor undo.

Some Popular operations
push(x)    pop()
getSize()    isEmpty()
top()

In JAVA, we have a class java.util.Stack
API - application programming interface - Interface

How to Implement Stack
#1 array S with N items, variable top
ExcpetionStackFull if data is over N items for the array.

Some core methods are as follow:
public Object pop() throws ExceptionStackEmpty {
    Object elem;
    if(isEmpty()){
        throw new ExceptionStackEmpty(“Error while pop method: Stack empty.");
    }
    elem = S[top];
    S[top - -] = null;
    return elem;
}

It is O(1) for all methods.

Java Method Stack
Java is call-by-value.

Fac(n) = n!
public static long factorial(long n) {
    if(n<=1)      return 1;
    else           return n*factorial(n-1);
}

Operand Stack

We can use stack to see if all (), {}, [], if they are all matched.
ParentMatch(X, n)
Inputs: array X with n items
Outputs: if () match in X

{
    initial stack S;
    for ( i = 0 to n -1){
        if(X[i] is ‘(‘){
            S.push(X[i]);
        }
        else if(X[i] is ‘)’){
            if(S.isEmpty()){
               return not_match;
            }
            if( S.pop() is not X[i]){
                return not_match;
            }
        }
    }

    if(S.isEmpty()){  return match; }
    else                { return not_match; }
}

HTML tag match

Queue
First-In-First-Out, FIFO

Basic method:
enqueue(x) : put item x into the queue
dequeue() : fetch the item from the queue

Other method:
getSize(), isEmpty(), front()

System can use array Q,
f - starter index of the Array
r - end index + 1 of the Array

Some import method implementation
public boolean isEmpty(){
    return (f == r);
}

public void enqueue(Object obj) throws ExceptionQueueFull{
    if(getSize() == capacity - 1){
        throw new ExceptionQueueFull(“Queue overflow");
    }
    Q[r] = obj;
    r = (r+1) % capacity;
}

public Object dequeue(){
    Object elem;
    if(isEmpty()){
        throw new ExceptionQueueEmpty(“Error dequeue: array empty");
    }
    elem = Q[f];
    Q[f] = null;
    f = (f+1) % capacity;
    return elem;
}

O(1)

Queue Application Samples
CPU, event and etc

Linked List
Singly Linked List
head - tail
element — content, next

This can save space.

Implement Stack on top of Singly Linked List
public class StackList implements Stack {
    protected Node top; //top elem
    protected int size;    //

    public StackList(){
        top = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return (top == null) ? true: false:
    }

    public void push(Object elem){
        Node v = new Node(elem, top); //create new node, next is the original top
        top = v;  //update top
        size++;  //update size
    }

    public Object pop() throws ExceptionStackEmpty{
        if(isEmpty()){
            throw new Exception
        }
        Object temp = top.getElem();
        top = top.getNext(); // update the top
        size—; //update size
        return temp;
    }
}

Implement Queue on top of Singly Linked List
public class QueueList implements Queue {
    protected Node head; //
    protected Node tail;
    protected int size;

    public QueueList(){
        head = tail = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return (0 == size) ? true: false;
    }

    public void enqueue(Object obj){
        Node node = new Node();
        node.setElem(obj);
        node.setNext(null);
        if( 0==size){
            head = node;
        }else{
            tail.setNext(node); // current node will be the tail
        }
        tail = node; //update the tail
        size++; // update the size
    }

    public Object dequeue() throws ExceptionQueueEmpty{
        if ( 0 == size){
            throw new ExceptionQueueEmpty(“dequeue Error: array is empty");
        }
        Object obj = head.getElem();
        head = head.getNext();
        size—;
        if(0 == size){
            tail = null;
        }
        return obj;
    }
}

Position
interface for position:
public interface Position{
    public Object getElem();
    public Object settled(Object e);
}

Double-ended Queue
insertFirst(x) - insertLast(x)
removeFirst() - removeLast()

first() - last()
getSize() - isEmpty()

Double Linked List
header - tailer
prev - next, element

public class DoubleEndQueue implement Deque{
    protected DLNode header;
    protected DLNode trailer;
    protected int size;

    public DoubleEndQueue(){
        header = new DLNode();
        trailer = new DLNode();
        header.setNext(trailer);
        trailer.setPrev(header);
        size = 0;
    }

    public boolean isEmpty(){
        return (0 == size) ? true: false;
    }

    public void insertFirst(Object obj){
        DLNode second = header.getNext();
        DLNode first = new DLNode(obj, header, second);
        second.setPrev(first);
        header.setNext(first);
        size++
    }

    public void insertLast(Object obj) {
        DLNode second = trailer.getPrev();
        DLNode first = new DLNode(obj, second, trailer);
        second.setNext(first);
        trailer.setPrev(first);
        size++;
    }

    public Object removeFirst() throws ExceptionQueueEmpty {
        if(isEmpty()){
            throw new ExceptionQueueEmpty(“Error: double end queue is empty");
        }
        DLNode first = header.getNext();
        DLNode second = first.getNext();
        Object obj = first.getElem();
        header.setNext(second);
        second.setPrev(header);
        size - - ;
        return obj;
    }

    public Objet removeLast() throws ExceptionQueueEmpty {
        if(isEmpty()){
            throw new ExceptionQueueEmpty(“Error: double end queue is empty");
        }
        DLNode first = trailer.getPrev();
        DLNode second = first.getPrev();
        Object obj = first.getElem();
        tailer.setPrev(second);
        second.setNext(trailer);
        size - - ;
        return obj;
    }
}

References:
https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html