This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Basic data structure

Introduction: This article focuses on several basic and common data structures: linked lists, stacks, and queues.

The stack

The stack implements a first-in, first-out strategy, where elements inserted first are removed last. There are many ways to implement stacks in computers, but here we simply use arrays. The structure is similar to the following:

The first element to be inserted is at the bottom of the stack, and the second element is at the top. When it comes to fetching an element, the element at the top of the stack is fetched. The stack can be represented as an array with a top attribute that points to the most recently inserted element.

In the figure above, the array is a stack with s.tip pointing to the top of the stack. To retrieve an element, return the element to which S.tip refers, then s.tip –. The element is still in the array, but it is no longer on the stack.

The pseudo-code for the stack operation is as follows:

// Check whether the stack is empty
STACK-EMPTY(S) // S indicates an array
if S.top == 0
    return TRUE
else
    return FALSE
    
// Put elements
PUSH(S,x)
S.top = S.top+1
S[S.top] = x

// Fetch the element
POP(S)
if STACK-EMPTY(S)
    error 'underflow'
else
    return S[S.top--]
Copy the code

The queue

Queues are dynamic collections like stacks, but queues implement a first-in, first-out strategy. There’s a lot of ways to do queues, but I’m going to do arrays. The queue structure is as follows:

To implement the queue using an array, two Pointers are required, one pointing to the end of the queue and the other to the head of the queue. They are set to q.ail and q.ead respectively. Q.ail +1 when inserting elements and Q.ead +1 when taking elements out. Thrusting when the line is full causes overflows. Therefore, you need to determine whether the overflow occurs.

The pseudo code for its queue is as follows:

// Check whether it is null
QUEUE-EMPTY(Q)
if Q.tail==Q.head
    return TRUE
return FALSE

QUEUE-FULL(Q)
if (Q.tail+1)%Q.size==Q.head
    return TRUE
return FALSE

ENQUEUE(Q,x)
if QUEUE-FULL(Q)
    error 'Overflow'
Q[Q.tail] = x
if Q.tail==Q.length
    Q.tail = 1
else  Q.tail = Q.tail+1

DEQUEUE(Q)
if QUEUE-EMPTY(Q)
    error 'underflow'
x = Q[Q.head]
if Q.head = Q.length
    Q.head = 1
else Q.head = Q.head+1
return x
Copy the code

The list

Linked list, alias chain storage structure or singularly linked list, used to store data with a “one to one” logical relationship. The list does not limit the physical storage state of the data, that is, the order of the list is random, and the order is determined by the Pointers in each object.

The list consists mainly of a key and next and some satellite data. Of course, in the bidirectional linked list, it is composed of key, next and prev, where next and prev are two Pointers to the node before and after the node, respectively. The key is the data stored. If x.rev ==NIL means the node is the head of the list, and x.ext ==NIL means the node is the tail of the list. Read refers to the head node of the list. If it equals NIL, the list is null. The structure of the two-way linked list is similar to the following figure:

Insert, delete, and search for a two-way list:

search

The list is searched linearly, looking for a keyword and returning a pointer to that element. Returns NIL if there is none.

LIST-SEARCH(L,k)
x = L.head
whilex ! = NILandx.key ! = k x = x.nextreturn x
Copy the code

insert

LIST-INSERT(L,x)
x.next = L.head
ifL.head ! = NIL L.head.prev = x L.head = x x.prev = NILCopy the code

delete

The deletion operation is to first find the specified pointer, and then by modifying some Pointers, x is removed from the list.

LIST-DELETE(L,x)
ifx.prev ! = NIL x.prev.next = x.nextelse L.head = x.next
ifx.next ! = NIL x.next.prev = x.prevCopy the code