Data structure - dynamic array

It refers to that both ends of a linear table are used as the bottom of the stack to enter and exit the stack respectively. It mainly uses the characteristic of "the bottom position of the stack remains unchanged, while the top position of the stack changes dynamically".

1.1.2 arraydoubleendstack class

package P2.linear structure;
import java.util.Iterator;
//Double ended stack
public class ArrayDoubleEndStack<E> implements Iterable<E> {
    //Top of left stack
    private int ltop;
    //Top of right stack
    private int rtop;
    //Container for storing elements
    private E[] data;
    //Default capacity of array container
    private static int DEFAULT_CAPACITY = 10;

    public ArrayDoubleEndStack() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        ltop = -1;
        rtop = data.length;
    }

    public void pushLeft(E element) {
        if (ltop + 1 == rtop) {
            resize(data.length * 2);
        }
        data[++ltop] = element;
    }

    public void pushRight(E element) {
        if (ltop + 1 == rtop) {
            resize(data.length * 2);
        }
        data[--rtop] = element;
    }

    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        //Copy the elements of the left stack
        for (int i = 0; i <= ltop; i++) {
            newData[i] = data[i];
        }
        //Copy the elements of the right stack
        int index = rtop;
        for (int i = newLen - sizeRight(); i < newLen; i++) {
            newData[i] = data[index++];
        }
        rtop = newLen - sizeRight();
        data = newData;
    }

    public E popLeft() {
        if (isLeftEmpty()) {
            throw new IllegalArgumentException("left stack is null");
        }
        E ret = data[ltop--];
        if (sizeLeft() + sizeRight() <= data.length / 4 && data.length > DEFAULT_CAPACITY) {
            resize(data.length / 2);
        }
        return ret;
    }

    public E popRight() {
        if (isRightEmpty()) {
            throw new IllegalArgumentException("right stack is null");
        }
        E ret = data[rtop++];
        if (sizeLeft() + sizeRight() <= data.length / 4 && data.length > DEFAULT_CAPACITY) {
            resize(data.length / 2);
        }
        return ret;
    }

    public E peekLeft() {
        if (isLeftEmpty()) {
            throw new IllegalArgumentException("left stack is null");
        }
        return data[ltop];
    }

    public E peekRight() {
        if (isRightEmpty()) {
            throw new IllegalArgumentException("right stack is null");
        }
        return data[rtop];
    }

    public boolean isLeftEmpty() {
        return ltop == -1;
    }

    public boolean isRightEmpty() {
        return rtop == data.length;
    }

    public int sizeLeft() {
        return ltop + 1;
    }

    public int sizeRight() {
        return data.length - rtop;
    }

    @Override
    public String toString() {
        // 1 2 3       7 8 9
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isLeftEmpty() && isRightEmpty()) {
            sb.append(']');
            return sb.toString();
        }
        //Start on the left
        for (int i = 0; i <= ltop; i++) {
            sb.append(data[i]);
            if (i == ltop && isRightEmpty()) {
                sb.append(']');
                return sb.toString();
            } else {
                sb.append(',');
            }
        }
        //Back right
        for (int i = rtop; i < data.length; i++) {
            sb.append(data[i]);
            if (i == data.length - 1) {
                sb.append(']');
            } else {
                sb.append(',');
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayDoubleEndStackIterator();
    }

    class ArrayDoubleEndStackIterator implements Iterator<E> {
        private ArrayList<E> list;
        private Iterator<E> it;

        public ArrayDoubleEndStackIterator() {
            list = new ArrayList<>();
            for (int i = 0; i <= ltop; i++) {
                list.add(data[i]);
            }
            for (int i = rtop; i < data.length; i++) {
                list.add(data[i]);
            }
            it = list.iterator();
        }

        @Override
        public boolean hasNext() {
            return it.hasNext();
        }

        @Override
        public E next() {
            return it.next();
        }
    }
}

1.2 queue

1.2.1 definition of queue

A queue is a linear table that only allows insertion at one end and deletion at the other. We call the end that allows deletion as the front and the end that is inserted as the rear. A queue without any data elements is called an empty queue. A queue is a First In Last Out linear table, referred to as FIFO. The queue itself is a linear table, Its data elements have a linear relationship, but it is a special linear table. The insertion operation of the queue is called the deletion operation of the queue, which is called the make queue

1.2.2 definition of queue interface

package P1. Interface;

    public interface Queue<E> extends Iterable<E> {
        public void offer(E element);   // Join the team
        public E poll();    // Out of the team
        public E peek();    // View team leader element
        public boolean isEmpty();
        public void clear();
        public int size();
    }

1.2.3} ArrayQueue class

package P2.linear structure;

import P1.Interface.Queue;

import java.util.Iterator;

public class ArrayQueue<E> implements Queue<E> {
    private ArrayList<E> list;
    public ArrayQueue() {
        list = new ArrayList<>();
    }

    @Override
    public void offer(E element) {
        list.add(list.size(), element);
    }

    @Override
    public E poll() {
        return list.remove(0);
    }

    @Override
    public E peek() {
        return list.get(0);
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public String toString() {
        return list.toString();
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayQueue) {
            ArrayQueue other = (ArrayQueue) o;
            return list.equals(other.list);
        }
        return false;
    }
}

1.3 queue implementation stack

1.3.1 quetostack class

package P2.linear structure;
import P1.Interface.Stack;
import java.util.Iterator;
public class QueueToStack {
    public static void main(String[] args) {
        StackImplByQueue<Integer> stack = new StackImplByQueue<>();
        System.out.println(stack);
        for (int i = 1; i <= 5; i++) {
            stack.push(i); //Queue A
        }
        System.out.println(stack.toString());
        System.out.println(stack.pop());
        System.out.println(stack);  //Queue B

    }
}
class StackImplByQueue<E> implements Stack<E> {
    private ArrayQueue<E> queueA;
    private ArrayQueue<E> queueB;

    public StackImplByQueue() {
        queueA = new ArrayQueue<>();
        queueB = new ArrayQueue<>();
    }

    @Override
    public int size() {
        if (queueA.isEmpty() && queueB.isEmpty()) {
            return 0;
        } else if (!queueA.isEmpty()) {
            return queueA.size();
        } else {
            return queueB.size();
        }
    }

    @Override
    public boolean isEmpty() {
        return queueA.isEmpty() && queueB.isEmpty();
    }

    @Override
    public void push(E element) {
        if (queueA.isEmpty() && queueB.isEmpty()) {
            queueA.offer(element);
        } else if (!queueA.isEmpty()) {
            queueA.offer(element);
        } else {
            queueB.offer(element);
        }
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }
        E ret = null;
        if (!queueA.isEmpty()) {
            while (queueA.size() != 1) {
                queueB.offer(queueA.poll());
            }
            ret = queueA.poll();
        } else {
            while (queueB.size() != 1) {
                queueA.offer(queueB.poll());
            }
            ret = queueB.poll();
        }
        return ret;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E ret = null;
        if (!queueA.isEmpty()) {
            while (queueA.size() != 1) {
                queueB.offer(queueA.poll());
            }
            ret = queueA.poll();
            queueB.offer(ret);
        } else {
            while (queueB.size() != 1) {
                queueA.offer(queueB.poll());
            }
            ret = queueB.poll();
            queueA.offer(ret);
        }
        return ret;
    }

    @Override
    public void clear() {
        queueA.clear();
        queueB.clear();
    }

    @Override
    public Iterator<E> iterator() {
        if (isEmpty()) {
            return queueA.iterator();
        } else if (!queueA.isEmpty()) {
            return queueA.iterator();
        } else {
            return queueB.iterator();
        }
    }
    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        } else if (!queueA.isEmpty()) {
            return queueA.toString();
        } else {
            return queueB.toString();
        }
    }

}

1.4 circular queue ArrayLoopQueue

1.4.1 definition of circular queue ArrayLoopQueue

The implementation idea of the circular queue is also a dynamic array, but due to the particularity of the operation elements, it cannot be directly implemented by ArrayList or ArrayQueue, so ArrayLoopQueue is defined from scratch

1.4.2 arrayloopqueue class

package P2.linear structure;

import P1.Interface.Queue;
import java.util.Iterator;
//Circular queue
public class ArrayLoopQueue<E> implements Queue<E> {
    private E[] data;   //Container for storing data
    private int front;  //Queue head pointer (actually the index angle in the array)
    private int rear;   //Tail pointer
    private int size;   //Number of elements (f < R R-F; R < f r + L-F)
    private static int DEFAULT_CAPACITY = 10;   //Default capacity
    public ArrayLoopQueue() {
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }
    @Override
    public void offer(E element) {
        //Is it full
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }
    @Override
    public E poll() {
        //Empty
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    @Override
    public E peek() {
        return null;
    }

    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        int index = 0;
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            newData[index++] = data[i];
        }
        data = newData;
        front = 0;
        rear = index;
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
        front = 0;
        rear = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
            return sb.toString();
        }
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if ((i + 1) % data.length == rear) {
                sb.append(']');
            } else {
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayLoopQueue) {
            ArrayLoopQueue<E> other = (ArrayLoopQueue<E>) o;
            if (size != other.size) {
                return false;
            }
            int i = front;
            int j = other.front;
            while (i != rear) {
                if (!data[i].equals(other.data[j])) {
                    return false;
                }
                i = (i + 1) % data.length;
                j = (j + 1) % other.data.length;
            }
            return true;
        }
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayLoopQueueIterator();
    }

    class ArrayLoopQueueIterator implements Iterator<E> {
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}

1.5 double ended queue

1.5.1 definition of double ended queue

double ended queue (deque) is a linear table that restricts the insertion and deletion operations at both ends of the table. It is a data structure with the properties of queue and stack

1.5.2 arraydeque class

package p2.linear structure;
import p1.Interface.Queue;
import java.util.Iterator;

public class ArrayQueue<E> implements Queue<E> {
    private ArrayList<E> list;
    public ArrayQueue() {
        list = new ArrayList<>();
    }

    @Override
    public void offer(E element) {
        list.add(list.size(), element);
    }

    @Override
    public E poll() {
        return list.remove(0);
    }

    @Override
    public E element() {
        return list.get(0);
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public String toString() {
        return list.toString();
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayQueue) {
            ArrayQueue other = (ArrayQueue) o;
            return list.equals(other.list);
        }
        return false;
    }
}

Keywords: data structure linked list

Added by sheen.andola on Fri, 14 Jan 2022 18:01:33 +0200

Programming VIP