preface

The stack

concept

What is a stack?

** stack ** : is a special linear table that can only be operated on one end

Push: The operation of adding elements to the stack, commonly called push

The operation of removing an element from the stack, usually called pop.

Note: the term “stack” is different from the term “stack space” in memory

The structure of the stack

Compared with arrays and linked lists, stacks are linear data structures that store the same types of data, but with more limitations. For example: Only one end of the stack is open (the top of the stack), and all data operations are performed on this end. Due to this feature, there is a so-called “Last In First Out (LIFO)” feature. The other three sides are closed, so all elements In the stack are unknown except the top element. The stack also can’t do random access.

Illustrated stack structure:

Last in first out:

The design of the stack

In fact, in addition to the three sides of the stack closed, the other is the same as the linear data structure I have written before, so the internal implementation of the stack can be directly implemented by using the data structure I have learned before, such as DynamicArray DynamicArray, LinkedList. DynamicArray LinkedList DynamicArray LinkedList DynamicArray LinkedList

However, the Stack class we write is not directly inherited from these classes, because this will expose some original methods of DynamicArray, LinkedList, such as random access, random insert, delete, etc., which will make the Stack lose its characteristics. To solve this problem, use the composite pattern to draw the class diagram:

Stack interface design

1. Attributes:

private List<E> list; Implement class design stack using linear tables based on the List interface

2. Interface method:

int size();Check the number of current stack elements
boolean isEmpty();Check whether the stack is empty
public void push(E element);— Push, add elements
public E pop();Remove the tail element from the stack
public E top();Get the top element of the stack
void clear();Clear stack elements

After the design is completed, it is the specific method encoding implementation, because it is the stack of DynamicArray DynamicArray and LinkedList LinkedList. All the calls are encapsulated methods, so I won’t go into details here

coded

public class Stack<E> extends DynamicArray<E>{

   // Implement stack with dynamic array
   private List<E> list = new DynamicArray<>();

   // Use linked lists to implement stacks
   //private List<E> list = new DynamicArray<>();

   /** * check stack elements *@return* /
   public int size(a) {
      return list.size();
   }

   /** * Check whether the stack is empty *@return* /
   public boolean isEmpty(a) {
      return list.isEmpty();
   }

   /** * add element *@param element
    */
   public void push(E element){
      list.add(element);
   }

   /** * remove the tail element */
   public E pop(a){
      return list.remove(list.size() - 1);
   }

   /** * get the top element *@return* /
   public E top(a){
      return list.get(list.size() - 1);
   }


   /** * empties the stack element */
   public void clear(a) { list.clear(); }}Copy the code

summary

The application of the stack

1, double stack browser forward and backward

2. Undo and Redo functions

The queue

concept

What is a queue?

Queue: Unlike previous stacks, which can only operate on elements at the top of the stack, queues can operate on elements at both ends. Queues are also special linear tables

Queue: You can only add elements from rear, usually called enQueue

Queue out: Only elements can be removed from the front of the queue, usually called a deQueue

Queue structure

Compared with arrays, linked lists, and stacks, queues are linear data structures that store the same type of data, except that queues are less restrictive than stacks, but more restrictive than arrays and linked lists. For example: The queue can only add data at the end of the queue, and the queue head removes elements. Based on this feature, with the so-called “First In First Out principle, First In First Out, FIFO”** characteristics, the other two sides are closed In structural design, so In addition to the queue head element, other elements In the queue are unknown. Of course, the element at the end of the queue is also visible, but we usually only add elements at the end of the queue, so we don’t open this method, and the queue doesn’t do random access.

Figure out the queue structure:

Queue design

Queue and array, LinkedList and stack are all linear table structures, so there is no need to do some repetitive operations. DynamicArray and LinkedList written before can be implemented, and queue can also be implemented using stack. But here we use Both_LinkedList.

Wrote in the previous – list (Java implementation) is talked about, the head of the two-way linked list node and end node is first and the last pointer to, this to queue at the team head, elements of the operation is very convenient, is, of course, using dynamic array or also can singly linked list, just behind the team head removing elements makes an array element node moves forward, In a unidirectional list, the pointer head is traversed to the tail node when the element is added to the end of the queue. Both of these add complexity, so bidirectional lists are better

Again, but we’re not going to write a Queue that inherits these classes directly, we’re going to do it as a combination, so let’s draw the class diagram

Interface design for queues

1. Attributes:

private List<E> list; Implement class design queues using linear tables based on the List interface

2. Interface method:

int size();View the number of current queue elements
boolean isEmpty();— Checks whether the queue is empty
public void enQueue(E element);Join the team and add elements
public E deQueue();— Exit the queue and delete the header element
public E front();Add the fetch header element
void clear();Clear the queue element

After the completion of the design, is the specific method encoding implementation, because it is the use of bidirectional linked list Both_LinkedList to achieve the queue, call all encapsulated methods, not detailed here

coded

Bidirectional list implementation queue:

public class Queue<E> {

   // Implement the queue using the method encapsulated in the bidirectional list
   private List<E> list = new Both_LinkedList<>();

   /** * get the number of queue elements *@return* /
   public int size(a) {
      return list.size();
   }

   /** * Check whether the current queue is empty *@return* /
   public boolean isEmpty(a) {
      return list.isEmpty();
   }

   /** * add element * from the end of the queue@param element
    */
   public void enQueue(E element) {
      list.add(element);
   }

   /** * remove element from team head *@return* /
   public E deQueue(a) {
      return list.remove(0);
   }

   /** * get the header element *@return* /
   public E front(a) {
      return list.get(0);
   }

   /** * Empties the queue element */
   public void clear(a) { list.clear(); }}Copy the code

Dual stack implementation queue:

public class QueueByStack<E> {

    // Define two stacks, inStack for the end of the queue and outStack for the end of the queue
    private Stack<E> inStack,outStack;

    // Use the constructor to initialize
    public QueueByStack(a) {
        this.inStack = new Stack<>();
        this.outStack = new Stack<>();
    }

    /** * get the number of queue elements *@return* /
    public int size(a) {
        return inStack.size() + outStack.size();
    }

    /** * Check whether the current queue is empty *@return* /
    public boolean isEmpty(a) {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    /** * add element * from the end of the queue@param element
     */
    public void enQueue(E element) {
        inStack.push(element);
    }

    /** * add element * from team head@return* /
    public E deQueue(a) {
        checkOutStack();
        return outStack.pop();
    }

    /** * get the header element *@return* /
    public E front(a) {
        checkOutStack();
        return outStack.top();
    }

    /** * empties the stack element */
    public void clear(a) {
        inStack.clear();
        outStack.clear();
    }

    /** * Check if outStack is empty, if not, wait to be queued * if it is empty, and inStack is not empty, push the inStack element off the stack, into outStack, and prepare to be queued */
    private void checkOutStack(a) {
        if (outStack.isEmpty()) {
            while(! inStack.isEmpty()) { outStack.push(inStack.pop()); }}}}Copy the code

deque

concept

Dual-end queue: a queue that can be added or deleted at both ends

Structure diagram:

design

There is no difference in the implementation relationship between a double-ended Queue Deque and Queue, which is also based on the bidirectional linked list Both_LinkedList and implemented in the combined mode

Interface design of bidirectional queue

1. Attributes:

private List<E> list; Implement class design queues using linear tables based on the List interface

2. Interface method:

int size();View the number of current queue elements
boolean isEmpty();— Checks whether the queue is empty
public void enQueueRear(E element);Join the team, from the back of the line
public E deQueueRear();Get out, get out of the back of the line
public void enQueueFront(E element);Join the team, join the team from the head
public E enQueueFront();Get out of the team, get out of the team
public E front();Add the fetch header element
public E rear();Add the fetch element to the end of the queue
void clear();Clear the queue element

coding

public class Deque<E> {

    // Implement the queue using the method encapsulated in the bidirectional list
    private List<E> list = new Both_LinkedList<>();

    /** * get the number of queue elements *@return* /
    public int size(a) {
        return list.size();
    }

    /** * Check whether the current queue is empty *@return* /
    public boolean isEmpty(a) {
        return list.isEmpty();
    }

    /** * from the back of the line *@param element
     */
    public void enQueueRear(E element) {
        list.add(element);
    }

    /** ** from the end of the line *@return* /
    public E deQueueRear(a) {
        return list.remove(list.size() - 1);
    }

    /** * join the team from the head *@param element
     */
    public void enQueueFront(E element) {
        list.add(0, element);
    }

    /** ** out of the team, from the head *@return* /
    public E deQueueFront(a) {
        return list.remove(0);
    }

    /** * get the header element *@return* /
    public E front(a) {
        return list.get(0);
    }

    /** * get the last element *@return* /
    public E rear(a) {
        return list.get(list.size() - 1);
    }

    /** * Empties the queue element */
    public void clear(a) { list.clear(); }}Copy the code

Circular queue

Concept:

Circular queue: An array implemented and optimized queue

Illustrated structure:

Design:

Circular queue is also called circular queue, are implemented based on Java array, using the front is the position of the pointer to a head, on the design, not after removing elements as an array, move forward elements covered, but the value empty, front, back remove elements in such a mechanism, position, after deleting when front behind pointer position is full, The new element can fill in the space just deleted, acting as a ring

Cyclic interface design

1. Attributes:

private int front; — Loop queue head pointer
private int size; — Number of queue elements
private E[] elements; Use sequential structured array storage
private static final int DEFAULT_CAPACITY = 10; — The default initialization value of the array

2. Interface method:

int size();View the number of current queue elements
boolean isEmpty();— Checks whether the queue is empty
public void enQueue(E element);Join the team, from the back of the line
public E deQueue();— Exit the queue and delete the header element
public E front();Add the fetch header element
void clear();Clear the queue element
private void ensureCapacity(int capacity)– Ensure that the capacity is sufficient. If not, expand the capacity
private int index(int index);Index mapping function that returns the real array subscript

1. Out of line operation

2. Team entry operation

3. Rejoin the team

4. Attention points:

(1) team

(2) team

(3) out of the team

(4) capacity

Code:

public class CircleQueue<E> {

    // Default initialization value for array
    private static final int DEFAULT_CAPACITY = 10;

    // loop queue head pointer
    private int front;

    // Number of queue elements
    private int size;

    // Use sequential arrays for storage
    private E[] elements;

    The /** * constructor initializes the array */
    public CircleQueue(a) {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    /** * gets the number of queue elements *@return* /
    public int size(a){
        return size;
    }

    /** * Check whether the queue is empty *@return* /
    public boolean isEmpty(a){
        return size == 0;
    }

    /** * add element * from the end of the queue@param element
     */
    public void enQueue(E element) {
        ensureCapacity(size + 1);
        //elements[(front + size) % elements.length] = element;

        // Call the wrapper function
        elements[index(size)] = element;
        size++;
    }

    /** * remove element from team head *@return* /
    public E deQueue(a) {
        E element = elements[front];
        elements[front] = null;
        //front = (front + 1) % elements.length;
        // Call the wrapper function
        front = index(1);
        size--;
        return element;
    }


    /** * get the header element *@return* /
    public E front(a){
        return elements[front];
    }

    /** * Empties the queue element */
    public void clear(a) {
        for (int i = 0; i < size; i++) {
            //elements[(i + front) % elements.length] = null;

            // Call the wrapper function
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    /** * Ensure that the capacity of capacity is sufficient@param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;

        // The new capacity is 1.5 times the old capacity
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            //newElements[i] = elements[(i + front) % elements.length];

            // Call the wrapper function
            newElements[i] = elements[index(i)];
        }
        elements = newElements;

        / / reset the front
        front = 0;
    }

    /** * index mapping function that returns the real array subscript *@param index
     * @return* /
    private int index(int index){
        return (front + index) % elements.length;
    }

    @Override
    public String toString(a) {
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
                .append(" size=").append(size)
                .append(" front=").append(front)
                .append("[");
        for (int i = 0; i < elements.length; i++) {
            if(i ! =0) {
                string.append(",");
            }

            string.append(elements[i]);
        }
        string.append("]");
        returnstring.toString(); }}Copy the code

Loop double – ended queue

Concept:

Loop queue: a loop queue that can be added or deleted at both ends

Illustrated structure:

Last = (font + size-1) % array.length); last = (font + size-1) % array.length)

Cyclic interface design

1. Attributes:

private int front; — Loop queue head pointer
private int size; — Number of queue elements
private E[] elements; Use sequential structured array storage
private static final int DEFAULT_CAPACITY = 10; — The default initialization value of the array

2. Interface method:

int size();View the number of current queue elements
boolean isEmpty();— Checks whether the queue is empty
public void enQueueRear(E element);Join the team, from the back of the line
public E deQueueRear();Get out, get out of the back of the line
public void enQueueFront(E element);Join the team, join the team from the head
public E enQueueFront();Get out of the team, get out of the team
public E front();Add the fetch header element
public E rear();Add the fetch element to the end of the queue
void clear();Clear the queue element
private void ensureCapacity(int capacity)– Ensure that the capacity is sufficient. If not, expand the capacity
private int index(int index);Index mapping function that returns the real array subscript

coded

As mentioned above, the structure is the same as the loop queue, so most of the methods are the same, but the functionality has been enhanced and some of the method logic has been adjusted

Method changes:

Public void enQueueFront(E element); Join the team, join the team from the head

/** * join the team from the head *@param element
 */
public void enQueueFront(E element) {

    //front points to the position in front of the current node
    front = index(-1);
    // If front is 0, add to -1 when adding elements to queue header
    elements[front] = element;
    size++;
}
Copy the code

Public E deQueueRear(); Get out, get out of the back of the line

/** ** from the end of the line *@return* /
public E deQueueRear(a) {
    // Find the real index of the tail element
    int last = index(size - 1);
    E element = elements[last];
    elements[last] = null;
    size--;
    return element;
}
Copy the code

(3) add public E rear(); Add the fetch element to the end of the queue

/** * get the last element *@return* /
public E rear(a) {
    return elements[index(size - 1)];
}
Copy the code

(4) change private int index(int index); Index mapping function that returns the real array subscript

/** * index mapping function that returns the real array subscript *@param index
 * @return* /
private int index(int index){
    index += front;

    // If the real index is 0, add an element to the queue header and pass -1, which is less than 0
    if (index < 0){
        index += elements.length;
    }
    return index % elements.length;
}
Copy the code

The statement

Personal ability is limited, have incorrect place, also please correct

The article is original, welcome to reprint, just indicate the source

The code for this article has been uploadedgithub, welcomestar

GitHubaddress

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

(Super detailed) Hands-on writing – stack, queue (Java implementation)

preface

The stack

concept

The design of the stack

coded

summary

The queue

concept

Queue design

coded

deque

concept

design

coding

Circular queue

Circular queue

Loop double – ended queue

The statement

(Super detailed) Hands-on writing – stack, queue (Java implementation)

preface

The stack

concept

The design of the stack

coded

summary

The queue

concept

Queue design

coded

deque

concept

design

coding

Circular queue

Circular queue

Loop double – ended queue

The statement

Related Posts

Redis for Nosql database

I have something to say about the Http Status Code

Elasticsearch Analysis analyzer