Data structure – an implementation of queues (arrays)

Unidirectional queue (array implementation)

package main

import (
	"errors"
	"fmt"
	"os"
)

// Queue is an important data structure, which is relatively widely used. There are two main ways to implement queue: array and linked list
// Let's start with a simple one-way queue using arrays
// The queue information includes the size of the queue, the storage form of the queue (array), the head of the queue (not pointing to the first element), and the tail of the queue (pointing to the last element)
// Column operations include adding an element to the queue, fetching an element from the queue, and displaying elements in the queue
// Define a structure to hold the queue information
type signalQueue struct {
	maxSize int
	array [5]int // simulate the queue
	head int
	tail int
}

// Define a method to add elements to the queue
func (q *signalQueue) Push(val int) error{
	// Check whether the queue is full
	if q.tail == q.maxSize - 1 { //tail contains the last element
		return errors.New("Queue full")
	}
	q.tail++ // Move the tail back
	q.array[q.tail] = val
	return nil
}

// Define a method to get elements from the queue
func (q *signalQueue) Pop(a) (val int, err error) {
	// Check whether the queue is empty
	if q.tail == q.head {
		return - 1, errors.New("Queue empty")
	}
	q.head++ // Since the head points in front of the first element, it moves backwards first
	val = q.array[q.head]
	return val, nil
}

// Define a method to display queue elements
func (q *signalQueue) List(a) error {
	// Find the head of the queue (excluding the first element) and walk to the end of the queue
	for i := q.head + 1; i <= q.tail; i++{
		fmt.Printf("array[%d]=%d\t", i, q.array[i])
	}
	fmt.Println()
	return nil
}

func main (a){
	queue := &signalQueue{
		maxSize: 5,
		array:   [5]int{},
		head:    - 1,
		tail:    - 1,}var key string
	var val int
	// Add data
	for {
		fmt.Println("1. Add add data to queue")
		fmt.Println("2. Get gets data from the queue")
		fmt.Println("3.show display queue")
		fmt.Println("4. Exit the queue")

		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("Enter the data you want to queue.")
			fmt.Scanln(&val)
			err := queue.Push(val)
			iferr ! =nil {
				fmt.Println(err)
			} else {
				fmt.Println("Made the team.")}case "get":
			val, err := queue.Pop()
			iferr ! =nil {
				fmt.Println(err)
			} else {
				fmt.Println("The number of queue exits is:", val)
			}
		case "show":
			queue.List()
		case "exit":
			os.Exit(0)}}}/ / summary:
// One of the biggest problems with the unidirectional queue implemented above is that:
// If there is no valid space for using data, the queue will be displayed as full when adding data, but the queue will be displayed as empty when fetching data
// The solution to this problem is to join the end and head of the array together to create a circular queue
Copy the code

Ring queue (array implementation)

package main

import (
	"errors"
	"fmt"
	"os"
)

// Head refers to the first element in the queue, and tail refers to the next element in the queue.
// Define a structure to manage the ring queue
type circelQueue struct {
	maxSize int
	array [5]int
	head int
	tail int
}

// Define an enqueue method
func (q *circelQueue) Push(val int) error {
	// Check to see if it is full
	if q.IsFull(){
		return errors.New("Queue full")
	}
	q.array[q.tail] = val
	q.tail = (q.tail + 1) % q.maxSize //tail points to the last position of the tail
	return nil
}

// Define an outqueue method
func (q *circelQueue) Pop(a) (val int, err error) {
	// Check whether the queue is empty
	if q.IsEmpty(){
		return - 1, errors.New("Queue empty")
	}
	val = q.array[q.head]
	q.head = (q.head + 1) % q.maxSize //head points to the next element (next team leader)
	return val, nil
}

// Define a method to determine if the ring queue is full
func (q *circelQueue) IsFull (a) bool {
	return (q.tail + 1) % q.maxSize == q.head
}

// Define a method to determine whether the ring queue is empty
func (q *circelQueue) IsEmpty(a) bool {
	return q.tail == q.head
}

// Get the number of elements in the ring queue
func (q *circelQueue) Size(a) int {
	return (q.tail + q.maxSize - q.head) % q.maxSize
}

// Define a method to display ring queue elements
func (q *circelQueue) List(a){
	// Check whether the queue is empty
	if q.Size() == 0 {
		fmt.Println("Queue empty")}// Define an auxiliary variable to point to head, temporary head
	tempHead := q.head
	for i := 0; i < q.Size(); i++ {
		fmt.Printf("arr[%d]=%d\t", tempHead, q.array[tempHead])
		tempHead = (tempHead + 1) % q.maxSize
	}
	fmt.Println()
}

func main(a){
	queue := &circelQueue{
		maxSize: 5,
		array:   [5]int{},
		head:    0,
		tail:    0,}var key string
	var val int
	// Add data
	for {
		fmt.Println("1. Add add data to queue")
		fmt.Println("2. Get gets data from the queue")
		fmt.Println("3.show display queue")
		fmt.Println("4. Exit the queue")

		fmt.Scanln(&key)
		switch key {
		case "add":
			fmt.Println("Enter the data you want to queue.")
			fmt.Scanln(&val)
			err := queue.Push(val)
			iferr ! =nil {
				fmt.Println(err)
			} else {
				fmt.Println("Made the team.")}case "get":
			val, err := queue.Pop()
			iferr ! =nil {
				fmt.Println(err)
			} else {
				fmt.Println("The number of queue exits is:", val)
			}
		case "show":
			queue.List()
		case "exit":
			os.Exit(0)}}}/ / summary:
// Ring queue can solve the problem that one-way queue does not effectively utilize the effective space of array
// The implementation of the ring queue also fits most application scenarios
Copy the code