Day18 -- stack queue

1. queue

A queue is a special kind of linear table , What's special about this is that it's only allowed at the front of the table （front） Delete operation , And at the back end of the table （rear） Insert operation , Like the stack , A queue is a linear table with restricted operations . The end of the insertion operation is called the tail of the queue , The end of the delete operation is called the queue head .

2. The team

• Create a new node
• Connect the new node to the end of the queue
• Then the tail pointer points to the new node

public void enqueue(int paraValue) {
    
		Node tempNode = new Node(paraValue);
		tail.next = tempNode;
		tail = tempNode;
	}// of enqueue

3. Out of the stack

• First, judge whether the queue is empty
• Then the queue starts at the head of the team and leaves the team
• After leaving the team , Judge header Of next Is it empty , If it is empty , This queue is empty , take tail=header

public int dequeue() {
    
		if (header == tail) {
    
			System.out.println("No element in the queue");
			return -1;
		} 

		int resultValue = header.next.data;
		header.next = header.next.next;

		if (header.next == null) {
    
			tail = header;
		}

		return resultValue;
	}// of dequeue

4. Code implementation

package com.datastructure;

public class LinkedQueue {
    

	class Node {
    
		int data;
		Node next;

		public Node(int paraValue) {
    
			data = paraValue;
			next = null;
		}// Of the constructor
	}// of class Node

	Node header;

	Node tail;

	public LinkedQueue() {
    
		header = new Node(-1);
		tail = header;
	}// of the first constructor

	// The team , The operation of joining the team will be carried out at the end of the team 
	//1. Create a new node , Then connect the new node to the end of the team , Point the tail pointer to the new node 
	public void enqueue(int paraValue) {
    
		Node tempNode = new Node(paraValue);
		tail.next = tempNode;
		tail = tempNode;
	}// of enqueue

	// Out of the team , Head to head operation after leaving the team 
	//1. Determines if the queue is empty 
	public int dequeue() {
    
		if (header == tail) {
    
			System.out.println("No element in the queue");
			return -1;
		} 

		int resultValue = header.next.data;
		header.next = header.next.next;

		//  After leaving the team , Judge header Of next Is it empty , If it is empty , This queue is empty , take tail=header
		if (header.next == null) {
    
			tail = header;
		}

		return resultValue;
	}// of dequeue

	public String toString() {
    
		String resultString = "";

		if (header.next == null) {
    
			return "empty";
		} // Of if

		Node tempNode = header.next;
		resultString += tempNode.data;
		tempNode = tempNode.next;
		while (tempNode != null) {
    
			resultString += ", " + tempNode.data;
			tempNode = tempNode.next;
		} //of while

		return resultString;
	}//of toString

	public static void main(String args[]) {
    
		LinkedQueue tempQueue = new LinkedQueue();
		System.out.println("Initialized, the list is: " + tempQueue.toString());

		for (int i = 0; i < 5; i++) {
    
			tempQueue.enqueue(i + 1);
		} // of for i
		System.out.println("Enqueue, the queue is: " + tempQueue.toString());

		tempQueue.dequeue();
		System.out.println("Dequeue, the queue is: " + tempQueue.toString());

		int tempValue;
		for (int i = 0; i < 5; i++) {
    
			tempValue = tempQueue.dequeue();
			System.out.println("Looped delete " + tempValue + ", the new queue is: " + tempQueue.toString());
		} // of for i

		for (int i = 0; i < 3; i++) {
    
			tempQueue.enqueue(i + 10);
		} // of for i
		System.out.println("Enqueue, the queue is: " + tempQueue.toString());
	}//of main
}// of class LinkedQueue

Running results