Data Structures — Stacks and Queues (Java implementation)

What are stacks and queues?

• Stack is a special linear table structure, data in the stack, can only enter from the top of the stack, also can only be ejected from the top of the stack, with the characteristics of advanced after out.
• Queue is also a special linear table structure. In a queue, data can only be stored at the end of the queue, and data can only be removed from the front of the queue. It has the characteristics of first in, first out, last in, last out.

[Circular queue] The circular queue is a special queue. On the basis of meeting the requirements of the common queue, the circular queue solves the problem of space waste caused by the data taken out by the common queue. It maintains the index of the queue head and the index of the queue tail, so that the index can be initialized again when it crosses the boundary.

Stack implementation (Java)

/** * data stack, Java implementation ** data stack is a special linear table structure, * all data can only be inserted from the top of the stack, and can only be retrieved from the top *@authorHRP * February 14, 2020 11:33:59 am */
public class MyStack {
	private int[] arr;
	private int maxSize;
	private int top;
	
	/** * specifies the size of the stack. Initialize the stack * maxSize: indicates the maximum size of the stack * top: indicates the index of the data at the top of the stack *@param size
	 */
	public MyStack(int size) {
		this.maxSize = size;
		this.arr = new int[maxSize];
		this.top = -1;
	}
	
	/** * maintain top index * by pushing data from the top of the stack@param value
	 */
	public void push(int value) {
		arr[++top] = value;
	}
	
	/** * popup, popup the top of the stack, maintain the top index *@return* /
	public int pop(a) {
		return arr[top--];
	}
	
	/** * top==-1 *@return* /
	public boolean isEmpty(a) {
		return top == -1;
	}
	
	/** * top==(maxSize-1) *@return* /
	public boolean isFull(a) {
		return top == maxSize - 1;
	}
	
	/** * print stack, loop number is top+1 */
	public void printStack(a) {
		for(int i = 0; i <= top; i++) {
			System.out.print(arr[i]+"\t"); } System.out.println(); }}Copy the code

Implementation of circular Queues (Java)

/** * circular queue, Java implementation * queue is a special linear table structure, * it only allows delete operations at the front of the table, add operations at the back of the table *@authorHRP * February 14, 2020 10:46:57 am */
public class MyQueue {
	
	private int[] arr;
	private int maxSize;
	private int elems;
	private int font;
	private int end;
	
	/** * Specifies the size of the queue, initializes the queue *@param size
	 */
	public MyQueue(int size) {
		this.maxSize = size;
		this.arr = new int[maxSize];
		this.elems = 0;
		this.font = 0;
		this.end = -1;
	}
	
	/** * insert * and find if the queue is full. If the queue is not, then elems++ is used. If the queue is full, then font++ * is overwritten@param value
	 */
	public void insert(int value) {
		if(end == maxSize - 1) {
			end = -1;
		}
		arr[++end] = value;
		if(elems < maxSize) {
			elems++;
		}else{ font++; }}/** * select * from elems, select * from elems, select * from elems@return* /
	public int remove(a) {
		if(font == maxSize) {
			font = 0;
		}
		elems--;
		return arr[font++];
	}
	
	/** * to check whether the queue is empty, compare the queue elems attribute is 0 *@return* /
	public boolean isEmpty(a) {
		return this.elems == 0;
	}
	
	/** * If the queue is full, compare the elems attribute of the queue with the MaxSize value *@return* /
	public boolean isFull(a) {
		return this.elems == maxSize;
	}
	
	Note: You should not print the array index directly using font, * because the ++ process will destroy the correctness of the array font index */
	public void printQueue(a) {
		int index = font;
		for(int i = 0; i < elems; i++) {
			System.out.print(arr[index++]+"\t");
			if(index == maxSize) {
				index = 0; } } System.out.println(); }}Copy the code