Java simulation stack and queue data structure of the basic example
- 2020-05-09 18:35:40
- OfStack
Stack and queue:
1 is generally used as a programmer's tool, used to assist in conceiving algorithms, the life cycle is short, runtime is created;
Access is restricted, only 1 data can be read or deleted at a particular time;
Is an abstract structure, internal implementation mechanism, invisible to the user, such as using array, linked list to implement stack.
Mock stack structure
At the same time, only 1 data is allowed to be accessed, lifo
For both push and pull, the time complexity is O(1), that is, it does not depend on the number of data items in the stack, so the operation is faster
For example, an array is used as the storage structure of a stack
public class StackS<T> {
private int max;
private T[] ary;
private int top; // Pointer to the subscript of the element at the top of the stack
public StackS(int size) {
this.max = size;
ary = (T[]) new Object[max];
top = -1;
}
// Into the stack
public void push(T data) {
if (!isFull())
ary[++top] = data;
}
// Out of the stack
public T pop() {
if (isEmpty()) {
return null;
}
return ary[top--];
}
// Look at the top
public T peek() {
return ary[top];
}
// Whether the stack is empty
public boolean isEmpty() {
return top == -1;
}
// The stack is 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 above example, there is an maxSize rule, because arrays are of specified size, you can use other structures for storage if you want to be unlimited, or you can new a new length array.
For example, the stack is implemented using LinkedList storage
public class StackSS<T> {
private LinkedList<T> datas;
public StackSS() {
datas = new LinkedList<T>();
}
// Into the stack
public void push(T data) {
datas.addLast(data);
}
// Out of the stack
public T pop() {
return datas.removeLast();
}
// Look at the top
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--) {
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());
}
}
}
For example, the word is in reverse order, using the Statck structure
public class WordReverse {
public static void main(String[] args) {
reverse(" FUJITSU CONNECTED TECHNOLOGIES LIMITED ");
}
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 the reverse: " + sb.toString());
}
}
Print:
After the reversal: social strains
Simulated queue (1-type queue, double-end queue, priority queue)
Queue:
First in first out, deal with the similar queuing problem, first in the queue, first in the queue, first in the back row, etc
The time complexity for both insert and remove operations is O(1), insert from the back and remove from the front
Double-ended queue:
That is, insert and remove are available at both ends of the queue: insertLeft, insertRight, removeLeft, removeRight
Contains stack and queue functions, such as insertLeft, removeLeft, that is like stack 1; If insertLeft and removeRight are removed, it will be like queue 1
1 general low frequency of use, time complexity O(1)
Priority queue:
Internal maintenance of a prioritized sequence. When inserting, it is necessary to compare and find the inserted location. The time complexity is O(N), and O(1) is deleted.
/*
* The queue First in first out, 1 Two Pointers indicate the insertion position, 1 Two Pointers indicate the location where the data item is fetched
*/
public class QueueQ<T> {
private int max;
private T[] ary;
private int front; // Team head pointer Indicates the location where the data item is fetched
private int rear; // Pointer to a party Indicates the insertion position
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 line
public void insert(T t) {
if (rear == max - 1) {// We're at the end of the line, starting from scratch
rear = -1;
}
ary[++rear] = t;
nItems++;
}
// Remove the team head
public T remove() {
T temp = ary[front++];
if (front == max) {// Line up to the end. Start from the beginning
front = 0;
}
nItems--;
return temp;
}
// Check the team first
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());
}
}
}
/*
* deque <span style="white-space:pre"> </span> Insert and delete both ends
*/
public class QueueQT<T> {
private LinkedList<T> list;
public QueueQT() {
list = new LinkedList<T>();
}
// Insert the team head
public void insertLeft(T t) {
list.addFirst(t);
}
// Insert the line
public void insertRight(T t) {
list.addLast(t);
}
// Remove the team head
public T removeLeft() {
return list.removeFirst();
}
// Removal of the
public T removeRight() {
return list.removeLast();
}
// Check the team first
public T peekLeft() {
return list.getFirst();
}
// Look at the line
public T peekRight() {
return list.getLast();
}
public boolean isEmpty() {
return list.isEmpty();
}
public int size() {
return list.size();
}
}
/*
* Priority queue In the queue, sorted by priority, yes 1 Two ordered queues
*/
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 line
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]; // before 1 After one is assigned to 1 a Small in the It's like insertion sort, because a given sequence is already ordered, so it's efficient O(N)
} else {
break;
}
}
ary[j + 1] = t;
nItems++;
}
System.out.println(Arrays.toString(ary));
}
// Remove the team head
public int remove() {
return ary[--nItems]; // Remove low priority ones
}
// Look at the line Lowest priority
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);
}
}