Stack and Queue:
It is generally used as a tool for programmers to assist in conception of algorithms, with a short life cycle and is created only during runtime;
Access is restricted, and at a certain moment, only one data can be read or deleted;
It is an abstract structure, with an internal implementation mechanism that is invisible to users, such as using arrays and linked lists to implement the stack.
Simulate stack structure
At the same time, only one data is allowed to be accessed, and the time complexity of the later-in-first-out for both in-stack and out is O(1), that is, it does not depend on the number of data items in the stack. The operation is relatively fast, using an array as the storage structure of the stack
public class StackS<T> { private int max; private T[] ary; private int top; //Pointer, subscript to the top element of the stack public StackS(int size) { this.max = size; ary = (T[]) new Object[max]; top = -1; } //Stack public void push(T data) { if (!isFull()) ary[++top] = data; } //Stack public T pop() { if (isEmpty()) { return null; } return ary[top--]; } // View the top of the stack public T peek() { return ary[top]; } //Is the stack empty public boolean isEmpty() { return top == -1; } //Is the stack full public boolean isFull() { return top == max - 1; } //size public int size() { return top + 1; } public static void main(String[] args) { StackS<Integer> stack = new StackS<Integer>(3); for (int i = 0; i < 5; i++) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { Integer peek = stack.peek(); System.out.println("peek:" + peek); System.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { Integer pop = stack.pop(); System.out.println("pop:" + pop); System.out.println("size:" + stack.size()); } System.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { Integer peek = stack.peek(); System.out.println("peek:" + peek); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { Integer pop = stack.pop(); System.out.println("pop:" + pop); System.out.println("size:" + stack.size()); } } } In the example above, there is a maxSize regulation, because the array must be sized. If you want to have no limit, you can use other structures for storage, and of course you can also new an array of new length.
Example, use LinkedList storage to implement the stack
public class StackSS<T> { private LinkedList<T> datas; public StackSS() { datas = new LinkedList<T>(); } // Put the stack public void push(T data) { datas.addLast(data); } // Put the stack public T pop() { return datas.removeLast(); } // Check the top of the stack public T peek() { return datas.getLast(); } // Whether the stack is empty public boolean isEmpty() { return datas.isEmpty(); } //size public int size() { return datas.size(); } public static void main(String[] args) { StackS<Integer> stack = new StackS<Integer>(3); for (int i = 0; i < 5; i++) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { Integer peek = stack.peek(); System.out.println("peek:" + peek); System.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { Integer pop = stack.pop(); System.out.println("pop:" + pop); System.out.println("size:" + stack.size()); } System.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { stack.push(i); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { Integer peek = stack.peek(); System.out.println("peek:" + peek); System.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { Integer pop = stack.pop(); System.out.println("pop:" + pop); System.out.println("size:" + stack.size()); } } }Example, word reverse order, using the Statck structure
public class WordReverse { public static void main(String[] args) { reverse("Co., Ltd."); } static void reverse(String word) { if (word == null) return; StackSS<Character> stack = new StackSS<Character>(); char[] charArray = word.toCharArray(); int len = charArray.length; for (int i = 0; i <len; i++ ) { stack.push(charArray[i]); } StringBuilder sb = new StringBuilder(); while (!stack.isEmpty()) { sb.append(stack.pop()); } System.out.println("After inversion:" + sb.toString()); } }Print:
After the reversal: Social-style
Simulation queue (general queue, double-ended queue, priority queue)
queue:
First in first out, deal with queuing problems. First queue, first process, first row, second row, etc. The previous process is completed, and the time complexity of the insertion and removal operations is O(1). Insert from the back and remove the double-ended queue from the front:
That is, you can insert and remove at both ends of the queue: insertLeft, insertRight, removeLeft, removeRight
Functions containing stack and queues. If you remove insertLeft and removeLeft, it will be the same as the stack; if you remove insertLeft and removeRight, it will be the same as the queue. Generally, the frequency of use is low, and the time complexity O(1)
Priority Queue:
Maintain an internal sequence sorted by priority. When inserting, you need to compare and find the insertion position, time complexity O(N), delete O(1)
/* * Queue first in first out, a pointer indicates the insertion position, and a pointer indicates the position of the data item being taken out*/ public class QueueQ<T> { private int max; private T[] ary; private int front; //The head of the team indicates the position of the data item being taken out private int rear; //The tail of the team indicates the position of the data item being inserted private int nItems; //The actual number of data items public QueueQ(int size) { this.max = size; ary = (T[]) new Object[max]; front = 0; rear = -1; nItems = 0; } //Insert the tail of the queue public void insert(T t) { if (rear == max - 1) {//It has reached the end of the actual queue, start from the beginning, rear = -1; } ary[++rear] = t; nItems++; } //Remove the head of the team public T remove() { T temp = ary[front++]; if (front == max) {//The queue has reached the end, start from the beginning, start from the beginning, start from the beginning, start from the beginning, 0; } nItems--; return temp; } //View the head of the team public T peek() { return ary[front]; } public boolean isEmpty() { return nItems == 0; } public boolean isFull() { return nItems == max; } public int size() { return nItems; } public static void main(String[] args) { QueueQ<Integer> queue = new QueueQ<Integer>(3); for (int i = 0; i < 5; i++) { queue.insert(i); System.out.println("size:" + queue.size()); } for (int i = 0; i < 5; i++) { Integer peek = queue.peek(); System.out.println("peek:" + peek); System.out.println("size:" + queue.size()); } for (int i = 0; i < 5; i++) { Integer remove = queue.remove(); System.out.println("remove:" + remove); System.out.println("size:" + queue.size()); } System.out.println("----"); for (int i = 5; i > 0; i--) { queue.insert(i); System.out.println("size:" + queue.size()); } for (int i = 5; i > 0; i--) { Integer peek = queue.peek(); System.out.println("peek:" + peek); System.out.println("size:" + queue.size()); } for (int i = 5; i > 0; i--) { Integer remove = queue.remove(); System.out.println("remove:" + remove); System.out.println("size:" + queue.size()); } } } /* * Double-ended queue <span style="white-space:pre"> </span>Insert and delete at both ends*/ public class QueueQT<T> { private LinkedList<T> list; public QueueQT() { list = new LinkedList<T>(); } // Insert the queue head public void insertLeft(T t) { list.addFirst(t); } // Insert the queue tail public void insertRight(T t) { list.addLast(t); } // Remove the queue head public T removeLeft() { return list.removeFirst(); } // Remove the end of the team public T removeRight() { return list.removeLast(); } // View the head of the team public T peekLeft() { return list.getFirst(); } // View the end of the team public T peekRight() { return list.getLast(); } public boolean isEmpty() { return list.isEmpty(); } public int size() { return list.size(); } } /* * The priority queue is sorted by priority, and it is an ordered queue*/ public class QueueQP { private int max; private int[] ary; private int nItems; //The actual number of data items public QueueQP(int size) { this.max = size; ary = new int[max]; nItems = 0; } //Insert the end of the queue public void insert(int t) { int j; if (nItems == 0) { ary[nItems++] = t; } else { for (j = nItems - 1; j >= 0; j--) { if (t > ary[j]) { ary[j + 1] = ary[j]; // Assign the previous one to the next one is equivalent to using insertion sorting. The given sequence is originally ordered, so efficiency O(N) } else { break; } } ary[j + 1] = t; nItems++; } System.out.println(Arrays.toString(ary)); } //Remove the head of the team public int remove() { return ary[--nItems]; //Remove the small priority} //View the lowest priority of the team public int peekMin() { return ary[nItems - 1]; } public boolean isEmpty() { return nItems == 0; } public boolean isFull() { return nItems == max; } public int size() { return nItems; } public static void main(String[] args) { QueueQP queue = new QueueQP(3); queue.insert(1); queue.insert(2); queue.insert(3); int remove = queue.remove(); System.out.println("remove:" + remove); } }