Queue knowledge explanation and basic implementation (data structure)

The introduction

At noon in the canteen dozen rice, is really a headache thing, pace on the way to the dining room is always in a hurry, why ah, this still use to say, go a bit later, you will know what is called the people mountain people sea, queue in the canteen, compared with students, are only a few dozen rice aunt, one in each window, unavoidably we will have to wait for, Until the front of a student finished the meal to leave, the queue behind the people can continue to go forward, until it is their turn, don’t mention how laborious, but the order and rules are we should abide by, can only complain about their late

So this fifO example is one of the basic data structures that we’re talking about, the queue.

Examples added: When using a computer, sometimes the machine will be in a suspected state of crash, the mouse point seems to have no use, double-click any shortcut is not moving, when you lose patience, ready to reset, suddenly it is like wine wake up, you just click on all the operations in accordance with the order of execution again, This is actually caused by the fact that multiple programs in the operating system implicitly need to output through a channel, but queue up in order.

Basic definition of queues

Definition: A queue is a linear table that allows only delete operations on one segment and insert operations on the other

The segment that is allowed to insert is called rear, and the segment that is allowed to delete is called front.

The data elements of a queue are also called queue elements. Inserting a queue element into a queue is called enqueueing, and deleting a queue element from a queue is called enqueueing, precisely because a queue can only be inserted at one end and deleted at the other. So this is the concept of FIFO-first in first out, as shown in our previous example

In addition, there are also queues called double-ended queues, which are linear tables that can be inserted and deleted on both sides of a table

Dual-end queue classification:

Output constrained dual-ended queues: Delete operations are restricted to one segment of the table, while inserts are allowed to be performed at both ends of the earlier table

Inserts are limited to one segment of the table, while deletes are allowed at both ends of the table

The abstract data type of the queue

#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <exception>
using namespace std;

// Used to check the validity of the scope
class outOfRange:public exception {    	
public:    
	const char* what(a)const throw(a) {	
		return "ERROR! OUT OF RANGE.\n"; }};// Check the validity of the length
class badSize:public exception {    		
public:    
	const char* what(a)const throw(a) {
		return "ERROR! BAD SIZE.\n"; }};template <class T>
class Queue {
public:
	/ / to team
	virtual bool empty(a) const = 0;
	// Clear the queue
	virtual void clear(a) = 0;
	// Find the queue length
	virtual int size(a) const = 0;
	/ / team
	virtual void enQueue(const T &x) = 0;
	/ / out of the team
	virtual T deQueue(a) = 0;
	// Read the header element
	virtual T getHead(a) const = 0;
	// Virtual destructor
	virtual ~Queue(){} 
};
#endif 
Copy the code

Circular queue

Queue as a special linear table, naturally also has two ways of sequential and chain storage, we first take a look at its sequential storage mode – circular queue

In order to store the queue, we in addition to creating array of a certain space space, also need two Pointers, pointing to the front end of the queue and the micro end respectively, the following code, we chose to team head pointer to the first element of the previous position, of the pointer to the line element (of course this is not the only way, also can turn the head pointer to the head element, The tail pointer points to the position after the tail element. The principle is basically the same.)

Why do we do that, and why do we call this kind of storage a circular queue?

Let’s break it down step by step:

Let’s start by drawing the queue elements in and out of a queue as we normally would, such as queue elements out of a queue

This idea, that is, according to the example of queuing in the canteen in front of us, but we can clearly see that when A0 out of the queue, the elements after A0 all need to move forward to fill the vacancy, but we pay attention to performance in the computer, how can improve the performance of the team?

The loop queue is designed so that if we no longer restrict the queue head to the front of the entire space, our elements do not need to move together

Problem a

At this point, we need to consider the following questions:

(1) In order to solve the problem of only one element, the head of the queue and the tail of the queue overlap.

This is where the two Pointers we mentioned earlier come in handy (the head pointer points to the position before the head element, and the tail pointer points to the tail element). When the head and tail Pointers are equal, the queue is empty

Question 2

But there was a big problem!

If there is no space in front of the header element, our header pointer will point out of the array, and the array will be out of bounds.

We can see that although our header has no any space, but the back half of the table and free space, this kind of phenomenon we call false overflow, for example, close to the class you slowly walked into the classroom, see only the front left with two places, you will not be turned away, of course, can go in the front seat, only there is no seat, to consider leaving

We can make such a feasible solution

All we need to do is connect the end of the queue. When the space behind the queue is full, we can join the queue from the space left in front of the queue. Similarly, our header pointer has found a position to point to
Date [0…maxSize] maxSize – 1

Question 3

If the table is full and the table’s head is equal to the table’s tail, then the queue is empty. (We present three possible solutions)

A: Set the flag variable flag. When front = rear and flag = 0, the flag variable is empty. When flag = 1, the flag variable is full
Count == 0; count == maxsSize; count == maxsSize
C: Reserve a storage space to distinguish whether the queue is full. In other words, a table is considered full when one cell is free

Let’s focus on the method in C

According to this method we can sum up the operation formula of several conditions

Queue full condition :(rear+1) % MaxSize == front
Queue empty condition: front == rear
Number of elements in the queue :(rear-front + maxSize) % maxSize
Join: Rear = (rear + 1) % maxSize
Front = (front + 1) % maxSize

(1) The type definition of the sequential queue

#ifndef _SEQQUEUE_H_
#define _SEQQUEUE_H_
#include "Queue.h"

template <class T>
class seqQueue:public Queue<T> {
private:
	// Point to an array of elements
	T &data;
	// Queue size
	int maxSize;
	// Define the team head and tail Pointers
	int front, rear;
	// Expand the queue space
	void resize(a);
public: 
	seqQueue(int initSize = 100);
	~seqQueue() {delete[]data; }// Clear the queue
	void clear(a) {front = rear = - 1; }/ / found empty
	bool empty(a) const {returnfront == rear; }/ / to full
	bool full(a) const {return (rear + 1) % maxSize == front; }// Queue length
	int size(a) const {(rear- front + maxSize) % maxSize; }/ / team
	void enQueue(const T &x);
	/ / out of the team
	T deQueue(a);
	// take the first element of the queue
	T getHead(a) const; 
}; 

#endif 
Copy the code

Initialize an empty queue

template <class T>
seqQueue<T>::seqQueue(int initSize) {
	if (initSize <= 0) throw badSize();
	data = new T[initSize];
	maxSize = initSize;
	front = rear = - 1; 
}
Copy the code

(3) join the team

template <class T>
void seqQueue<T>::enQueue(const T &x) {
	// If the team is full, expand the capacity
	if ((rear + 1) % maxSize == front) resize();
	// Move the queue pointer
	rear = (rear + 1) % maxSize;
	/ / x team
	data[rear] = x;
}
Copy the code

(4) out of line

template <class T>
T seqQueue<T>::deQueue() {
	// If the queue is empty, an exception is thrown
	if (empty()) throw outOfRange();
	// Move the queue pointer
	front = (front + 1) % maxSize;
	/ / x team
	return data[front];
}
Copy the code

(5) take the first element of the team

template <class T>
T seqQueue<T>::getHead() const {
	if (empty()) throw outOfRange();
	// return the head element without moving the head pointer
	return data[(front + 1) % maxSize];
}
Copy the code

(6) Expand the queue space

template <class T>
void seqQueue<T>::resize() {
	T *p = data;
	data = new T[2 *maxSize];
	for(int i = 1; i < size(); ++i)
		// Copy the element
		data[i] = p[(front + i) % maxSize];
	// Set the first and last team Pointers
	front = 0; rear = size();
	maxSize *= 2;
	delete p;
}
Copy the code

Chain queue

If you use a chain storage structure to represent a queue we call it a chain queue, and you use a single linked list with no heads, where the head of the table is the head of the queue, and the tail of the table is the tail of the queue, you need two Pointers to the head element and the tail element, and one of the nice things about this storage structure is that the queue is not full

(1) The type definition of the sequential queue

#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
#include <iostream>
#include "Queue.h"

template <class T>
class linkQueue:public Queue<T> {
private:
	struct node {
		T data;
		node *next;
		node (const T &x, node *N = NULL) {
			data = x;
			next = N;
		}
		node ():next(NULL){}
		~node () {} 
	};
	node *front, *rear;
public: 
	linkQueue(){front = rear = NULL; }; ~linkQueue() {clear(); }// Clear the queue
	void clear(a);
	/ / found empty
	bool empty(a) const {return front == NULL; }// Queue length
	int size(a) const;
	/ / team
	void enQueue(const T &x);
	/ / out of the team
	T deQueue(a);
	// take the first element of the queue
	T getHead(a) const; 
};

#endif 
Copy the code

(2) Clear the queue

template <class T>
void linkQueue<T>::clear() {
	node *p;
	// Release all nodes in the queue
	while(front ! =NULL) {
		p = front;
		front = front -> next;
		delete p;
	}
	// Modify the tail pointer
	rear = NULL;
} 
Copy the code

(3) find the length of the queue

template <class T>
int linkQueue<T>::size() const {
	node *p = front;
	int count = 0;
	while(p) {
		count++;
		p = p -> next;
	} 
	return count;
}
Copy the code

(4) join the team

template <class T>
void linkQueue<T>::enQueue(const T &x) {
	if(rear == NULL) 
		front = rear = new node(x);
	else {
		rear -> next = newnode(x); rear = rear -> next; }}Copy the code

(5) out of line

template <class T>
T linkQueue<T>::deQueue() {
	// If the queue is empty, an exception is thrown
	if (empty()) throw outOfRange();
	node *p = front;
	// Save the team head element
	T value = front -> data;
	front = front -> next;
	if (front == NULL)
		rear = NULL;
	delete p;
	return value;
}
Copy the code

(6) take the first element of the team

template <class T>
T linkQueue<T>::getHead() const {
	if (empty()) throw outOfRange();
	return front -> data; 
}
Copy the code

The end:

If there are any deficiencies or mistakes in the article, please leave a comment and share your thoughts. Thank you for your support!

If it helps you, follow me! If you prefer the way of reading articles on wechat, you can follow my official account

We don’t know each other here, but we are working hard for our dreams

A adhere to push original development of technical articles of the public number: ideal more than two days

Queue knowledge explanation and basic implementation (data structure)

The introduction

Basic definition of queues

The abstract data type of the queue

Circular queue

Problem a

Question 2

Question 3

(1) The type definition of the sequential queue

Initialize an empty queue

(3) join the team

(4) out of line

(5) take the first element of the team

(6) Expand the queue space

Chain queue

(1) The type definition of the sequential queue

(2) Clear the queue

(3) find the length of the queue

(4) join the team

(5) out of line

(6) take the first element of the team

The end:

Related Posts

HttpSevletRequest Body information is read multiple times to fill the pit record – Java

Clean up the LeetCode series of circular lists with Java brush questions

The pit of postman