Stacks are different from queues and arrays, linked lists, and trees. Stacks and queues are used primarily as tools for programmers, primarily as AIDS in thinking up algorithms, rather than as full data storage tools.

They have a much shorter life cycle than arrays and are created during program execution and destroyed as soon as the task is completed.

A stack

A stack is a data structure in which data can be inserted and deleted only at one end, known as the top of the stack. Its characteristic is to tell simply after advanced. The main mechanism of the stack can be implemented using arrays, and of course, linked lists.

Use arrays to implement stacks, and complete common operations — out of the stack, on the stack, look at elements (only look at the top of the stack), determine whether the stack is empty and so on.

public class StackTest {
	
    private long[] arr;
    / / stack
    private int top;

    public StackTest(a){
        arr = new long[10];
        top = -1;
    }
    public StackTest(int maxsize){
        arr = new long[maxsize];
        top = -1;
    }

    /** * Add data *@param value
     */
    public void push(int value){
        arr[++top] = value;
    }

    /** * Remove data *@return* /
    public long pop(a) {
        return arr[top--];
    }

    /** * view data *@return* /
    public long peek(a){
        return arr[top];
    }
    public boolean isEmpty(a){
        return top == -1;
    }

    /*** * Check whether the file is full@return* /
    public boolean isFull(a){
        return top == arr.length-1; }}Copy the code

All operations on the stack are O(1) complexity, stack operations do not depend on the size of the stack element, stack does not need to move and compare operations.

The second queue

Queues are characterized by first in, first out. Queues are also implemented using arrays.

Arrays are used to implement queues and perform common operations — queue out, queue in, view elements, determine whether the queue is empty, and so on.

public class QueueTest {

    private long[] arr;
    // The size of the valid data
    private int elements;
    / / team head
    private int front;
    / / of the
    private int end;

    public QueueTest(a){
        arr = new long[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    public QueueTest(int maxsize){
        arr = new long[maxsize];
        elements = 0;
        front = 0;
        end = -1;
    }

    /** * Insert data *@param value
     */
    public void insert(long value){
        arr[++end] = value;
        elements++;
    }

    /** * delete data *@return* /
    public long remove(a){
        elements--;
        return arr[front++];
    }

    /** * view data from the head *@return* /
    public long peek(a){
        return arr[front];
    }

    /** * check whether the value is null *@return* /
    public boolean isEmpty(a){
        return elements == 0;
    }

    public boolean isFull(a){
        returnelements == arr.length; }}Copy the code

The complexity of queue insertion and deletion is O(1).

Three priority queues

A priority queue is the same as a normal queue. It is also a queue head and a queue tail. The elements are removed from the queue head. Thus, the complexity of priority queue insertion is O(N) and the complexity of deleting and viewing elements is O(1).

Use arrays to implement priority queues and perform common operations — queue out, queue in, view elements, determine whether the queue is empty and so on.

public class FirstQueueTest {

    private long[] arr;
    // The size of the valid data
    private int elements;
    / / team head
    private int front;
    / / of the
    private int end;

    public FirstQueueTest(a){
        arr = new long[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    public FirstQueueTest(int maxsize){
        arr = new long[maxsize];
        elements = 0;
        front = 0;
        end = -1;
    }

    /** * Insert data *@param value
     */
    public void inser(long value){
        if(elements == 0){
            arr[++end] = value;
            elements++;
        }else{
            // Compare by a certain rule, here using the value of the size comparison, in order from the smallest to the largest
            for(int i = elements-1; i>=0; i--){if(value<arr[i]){
                    arr[i+1] = arr[i];
                    arr[i] = value;
                }else{
                    arr[i+1] = value;
                    break; } } elements++; end++; }}/** * delete data *@return* /
    public long remove(a){
        elements--;
        return arr[front++];
    }

    /** * view data from the head *@return* /
    public long peek(a){
        return arr[front];
    }

    /** * check whether the value is null *@return* /
    public boolean isEmpty(a){
        return elements == 0;
    }

    public boolean isFull(a){
        returnelements == arr.length; }}Copy the code

Four summarizes

  1. The stack is characterized by first in, last out, and the stack can only view one element at the top of the stack
  2. Queues are first in, first out, and only one element of the queue head can be viewed
  3. To insert an element in a priority queue, on average, 2/N elements need to be moved, so the insertion complexity is O(N).
  4. Stacks and queues can be implemented using arrays or other data structures
  5. Stacks and queues are data structures that are manually constructed to do some work

Focus, don’t get lost

If you think the article is good, please pay attention to it, like it, and save it. Your support is the motivation for my creation. Thank you all.

If there is a problem with the article, please don’t be stingy, welcome to point out the message, I will check and modify in time.

If you want to know more about me, you can follow me by searching “Java Journey” on wechat. Reply “1024” to get the learning video and beautiful ebook. Push technical articles at 7:30 every day on time, so that your way to work is not lonely, and there are monthly book activities to help you improve your hard power!