Linear list, linked list and queue are the most common data structures in coding. In daily programming, we will consciously or unconsciously make choices.

1. The linear table

In essence, a linear table is a sequential storage structure, and all the contents that need to be stored can be indexed. Speaking of which, arrays are often used in programming. Linear table data structure representation:

class LinearList 
{
    private:
        int MaxSize;      // The maximum size of a linear table
        int length;     // The actual length of the linear table
        int *element;     // Store an array of linear tables
                  // We usually use templates instead of int definitions. We use int for convenience
    publicConstructor for linear tables, default maximum size is 10LinearList(int MaxSize = 10);
        ~LinearList() { delete[] element;  }

        bool IsEmpty()const { return length == 0; }
        bool IsFull()const { return length == MaxSize; }

        int Length()const { return length; }

        // The access function of a linear table, where k represents the index number and item represents the data value accessed
        bool Find(int k, int &item)const;
        int Search(const int &item)const;
        void Delete(int k, int &item)const;
        void Insert(int k, const int &item);
}Copy the code

It is not hard to see, the advantages of the linear table of random access of high efficiency and fast speed (because can index), and relatively simple to implement, but due to the maximum length of leading table fixed, so want to increase the length of the linear table will not be easy, if you need to change the length of the linear table, can create a new linear table, Copy the contents of the original linear table to the new linear table and delete the original linear table.

2. Linked list structure

class Node
{
    private:
        int data;   // Data fields, typically template classes
        Node *next; // point to the next node
    public:
        Node(Node *nextNode = NULL) { next = nextNode; }
        Node(const int& item, Node *nextNode = NULL)
            { data = item;  next = nextNode; }
        void setData(int data);
        int Data() { returndata; }}; class LinkedList {private:
        Node *head;  / / the head pointer
    public:
        LinkedList() { head = new Node(); }
        LinkedList(int &item);
        ~LinkedList();

        bool IsEmpty()const { return head->next == NULL; }
        int Length()const; // Return the length of the list

        // There are many different implementations here, and the following functions are one of them
        // Find the KTH element by iterating through the list and assign that element to item
        bool Find(int k, int &item)const;
        int Search(int k, int &item)const;
        void Delete(int k, int &item)const;
        void Insert(int k, const int &item);
}Copy the code

3. The stack

The concept of a stack should be separate, a heap is a heap, a stack is a stack, two different things. The basic components of the stack are pointer to the top of the stack, push the stack, pop the stack action, and can only read and write the top element of the stack,. The logical structure is that the elements that are first on the stack are read out later, and the elements that are last in are read out first, which we can call the later-come-behind principle (LIFO). The stack is just a concept, and its implementation is done by other basic data structures.

We’re talking about the stack, not the heap.

3.1 the order of stack

class AStack
{
    private:
        int size;     // The length of the linear table
        int *stackArray;    // An array of top elements
        int top;    // Top of stack pointer
    public:
        AStack(int MaxStackSize = 10)
        {
            size = MaxStackSize;
            stackArray = new int[MaxStackSize];
            top = -1;
        }
        ~AStack()
        { delete[] stackArray; }

        bool Push(const int &item);   / / pressure stack
        bool Pop(int &item);     / / flare stack
        bool Peek(int &item)const;      // Read the top element of the stack
        int IsEmpty()const { return top == -1; }
        int IsFull()const { return top == size - 1; }
        void clear() { top = -1; }Copy the code

3.2 the chain stack

As the name suggests, this stack is implemented as a linked list storage structure.

class LStack
{
    private:
        Node *top;   // pointer to the top of the stack
    public:
        LStack() { top = NULL; }
        ~LStack() { clear(); }
        void clear();   / / empty stack

        bool Push(const int &item);
        bool Pop(int &item);
        bool Peek(int &item);
        int IsEmpty()const { returntop == NULL; }}Copy the code

The advantages and disadvantages of the chain stack can be similar to the linked list structure.

4. The queue

4.1 Sequential Queue

The main idea is to create a linear table and add two Pointers, named as the first pointer to the queue, pointing to the beginning of the queue, and the element out of the queue, the last pointer to the queue, pointing to the current position of the queue, and can only be inserted backwards.

A pointer could be added to the queue to iterate over the elements in the queue, but doing so would destroy the principle of queue operation and reduce the queue to a simple linear table.

class AQueue
{
    private:
        int front;     / / team first
        int rear;     / / of the
        int count;    // Number of queue elements
        int *QArray;   // Queue array
        int size;    // Queue size
    public:
        AQueue(int MaxQueueSize = 10);
        ~AQueue() { delete[] QArray; }

        bool QInsert(const int &item);    // Insert elements to the end of the queue
        bool QDelete(int &item);     // Delete the header element

        void QClear() { front = rear = count = 0; }
        int QFront()const;    // Read the first element
        bool IsEmpty()const { return count == 0; }
        bool IsFull()const { returncount == size; }}Copy the code

4.2 Chain queue

class LQueue
{
    private:
        Node *front, *rear;
    public:
        LQueue() { front = rear = NULL; }
        ~LQueue() { QClear(); }

        void QInsert(const int &item);
        bool QDelete(int &item);
        bool QFront(int &item);

        int IsEmpty()const { return front == NULL; }
        void QClear();Copy the code

5. To summarize

Data structure is the most important knowledge in computer development, it can be said that as long as programming, data structure will be used. This article is just the tip of the iceberg of data structures, but as you get deeper into your programming, you’ll find that the tip of the iceberg is the most important foundation of the iceberg.

The definition of data structure is very broad, including the use of C language or other languages to write a small struct structure, can be regarded as a data structure. Again, all complex things are made up of simple symbols.