Biography: Swing unruly, love life. Java Cultivator (wechat official ID: Java Cultivator), welcome to follow. Access to 2000G of detailed information on the 2020 interview questions

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; // private int top; public StackTest(){ arr = new long[10]; top = -1; } public StackTest(int maxsize){ arr = new long[maxsize]; top = -1; Public void push(int value){arr[++top] = value; } @return */ public long pop() {return arr[top--]; } @return */ public long peek(){return arr[top]; } public boolean isEmpty(){ return top == -1; * @return */ public Boolean isFull(){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; Private int elements; private int elements; // private int front; Private int end; public QueueTest(){ arr = new long[10]; elements = 0; front = 0; end = -1; } public QueueTest(int maxsize){ arr = new long[maxsize]; elements = 0; front = 0; end = -1; Public void insert(long value){arr[++end] = value; elements++; } /** * delete data * @return */ public long remove(){elements--; return arr[front++]; } @return */ public long peek(){return arr[front]; } @return */ public Boolean isEmpty(){return elements == 0; } public boolean isFull(){ return elements == 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; Private int elements; private int elements; // private int front; Private int end; public FirstQueueTest(){ arr = new long[10]; elements = 0; front = 0; end = -1; } public FirstQueueTest(int maxsize){ arr = new long[maxsize]; elements = 0; front = 0; end = -1; If (elements == 0){arr[++end] = value; if(elements == 0){arr[++end] = value; elements++; } else{// 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++; }} @return */ public long remove() {elements--; return arr[front++]; } @return */ public long peek(){return arr[front]; } @return */ public Boolean isEmpty(){return elements == 0; } public boolean isFull(){ return elements == 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