Data structures and algorithms 4 - Stacks and queues

preface

Stacks and queues must be familiar, or at least heard of “fifo, fifO, fifO” these things. This article will describe the implementation and characteristics of stacks and queues.

Before we do that, we need to explain the corresponding characteristics of stacks and queues:

Stack: First in, last out, last in, first out.
Queue: first in, first out, last in, last out.

The stack

A stack is a linear structure because each data element in the stack is sequential. The data stored in the stack conforms to fifo, LIFO, fifO.

As we have seen in previous articles, a linear structure is a logical structure. Since the stack is a linear structure, it is obvious that the stack is also a logical structure. In other words, no matter how the data is stored in physical memory/disk, as long as it complies with the logical characteristics of the stack, it is a stack.

Here’s how to store a stack using sequential and chained structures in physical structures.

Order of the stack

Advantages: Simple implementation and operation, easy to understand. Disadvantages: Size is not easy to scale.

Implementation code:

#import <Foundation/Foundation.h>

#define MaxCount 20

/ / define the stack
typedef struct _Stack{
    int top;        // The position of the top element on the stack
    int data[MaxCount];   // The default stack size
} Stack;
// Create a stack
Stack createStack(a) {
    Stack s;
    s.top = - 1;     // -1 means there is nothing in the stack
    for (int i = 0; i < MaxCount; i++) {
        s.data[i] = 0;
    }
    return s;
}
/ / empty stack
void clearStack(Stack *s) {
    s->top = - 1;
}
// Get the top element of the stack
int getStackTopData(Stack s)
{
    if (s.top < 0) {
        printf("No element on the stack");
        return 0;
    }
    if (s.top >= MaxCount) {
        printf("Stack overflow, please make sure stack is correct.");
        return 0;
    }
    return s.data[s.top];
}
/ / into the stack
void inStack(Stack *s, int data) {
    if (s->top < - 1 || s->top >= MaxCount - 1) {
        printf("Stack full, cannot be pushed");
        return ;
    }
    s->top++;
    s->data[s->top] = data;
}
/ / out of the stack
int outStack(Stack *s) {
    if (s->top < - 1) {
        printf("There are no more elements in the stack. I can't get off the stack.");
        return 0;
    }
    return s->data[s->top--];
}
/ / traverse
void foreachStack(Stack s) {
    for (int i = 0; i < s.top + 1; i++) {
        printf("%-5d", s.data[i]);
    }
    printf("\n");
}
// Test the code
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        / / create a stack
        Stack s = createStack();
        / / into the stack
        for (int i = 0; i < 10; i++) {
            inStack(&s, i);
        }
        foreachStack(s);
        / / out of the stack
        printf("Top element = %d\n", getStackTopData(s));
        outStack(&s);
        foreachStack(s);
        
        printf("Top element = %d\n", getStackTopData(s));
        outStack(&s);
        foreachStack(s);
        
        printf("Top element = %d\n", getStackTopData(s));
        outStack(&s);
        foreachStack(s);
        
        
    }
    return 0;
}
Copy the code

Chain stack

Pros: Plenty of memory, theoretically unlimited expansion. Disadvantages: Nodes and header Pointers in the linked list need to be managed.

Implementation code:

#import <Foundation/Foundation.h>

// Define the node structure type
typedef struct _Node {
    int data;
    struct _Node *next;
} Node;
// Define the stack type
typedef struct _Stack {
    Node *top;
} Stack;

// Initializes a chain stack
Stack initStack(void) {
    Stack st;
    st.top = NULL;
    return st;
}
/ / into the stack
void inStack(Stack *st, int data) {
    // Create a node
    Node *node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    // insert the header into the stack
    node->next = st->top;
    st->top = node;
}
/ / out of the stack
int outStack(Stack *st) {
    if (st->top == NULL) {
        printf("There is no more data in the stack! \n");
        return 0;
    }
    // Save the address of the first node
    Node *p = st->top;
    // Point top to the second node
    st->top = st->top->next;
    // Unstack and release the node
    int data = p->data;
    p->data = 0;
    p->next = NULL;
    free(p);
    
    return data;
}
// Get the top element of the stack
int getTopData(Stack st) {
    if (st.top == NULL) {
        printf("No data in the stack! \n");
        return 0;
    }
    return st.top->data;
}
/ / traversal stack
void foreachStack(Stack st) {
    while (st.top) {
        printf("%-5d", st.top->data);
        // The stack does not change its original appearance because the address is not passed
        st.top = st.top->next;
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // Initialize the stack
        Stack st = initStack();
        / / into the stack
        for (int i = 0; i < 10; i++) {
            inStack(&st, i);
        }
        foreachStack(st);
        / / out of the stack
        for (int i = 0; i < 6; i++) {
            printf("%-5d\n", outStack(&st));
        }
        printf("----------------------------------\n");
        foreachStack(st);
    }
    return 0;
}
Copy the code

The queue

Using the stack described above, compare to understanding queues. Queues differ from stacks in that they have different characteristics, and queues are logically linear structures. However, the queue is equivalent to a passage that can only accommodate one person, and the entrance and exit are not the same, similar to queuing in the canteen to buy food, the first person can wait for the second person to buy food, otherwise they have to wait.

Similarly, queues can be implemented using sequential storage and chained storage, respectively.

The order queue

In a sequential queue, we can define two variables, one to store the index of the next element to be queued and one to store the index of the next element to be queued.

In the figure below, assuming that the queue length is 6, q.front represents the subscript of the next queue exit and q.ear represents the subscript of the next queue entry.

Such a queue, obviously, is not reasonable, that is, does not meet our daily needs. Therefore, someone proposed the concept of circular queue, that is, to connect the end of the queue.

But this creates a problem:

Front == rear when the team is empty.
Front == rear when the line is full.

There is no way to tell if the queue is full or empty. In this case, we choose to waste a space to distinguish between a full queue and an empty queue. So it becomes theta

The queue is empty when front == rear.
(rear + 1) % MaxCount == front

Here is the code implementation:

#import <Foundation/Foundation.h>

#define MaxCount 20

// Create a loop queue
typedef struct _HYQueue {
    int data[MaxCount];
    int front;      // The index corresponding to the first data entered
    int rear;       // The index corresponding to the next entry
} HYQueue;

// Initialize a queue
HYQueue initQueue(void) {
    HYQueue hq;
    hq.front = 0;
    hq.rear  = 0;
    return hq;
}
// Clear the queue
BOOL clearQueue(HYQueue *hq) {
    hq->front = 0;
    hq->rear  = 0;
    return YES;
}
// Check whether the queue is empty
BOOL isNull(HYQueue hq) {
    return hq.front == hq.rear;
}
// Check whether the queue is full
BOOL isFull(HYQueue hq) {
    // prevent the special case when rear == MaxCount -1,front == 0, when the queue is full, but MaxCount! = 0
    // Rear indicates the location where the next queue data is stored. The space corresponding to the current rear position is wasted because the queue is full and the queue is empty
    if ((hq.rear + 1) % MaxCount == hq.front) {
        return YES;
    }
    else {
        returnNO; }}/ / team
BOOL inQueue(HYQueue *hq, int data) {
    // Check whether the queue is full
    if (isFull(*hq)) {
        printf("Queue is full, unable to join, please wait... \n");
        return NO;
    }
    // Add data to the queue
    hq->data[hq->rear] = data;
    hq->rear = (hq->rear + 1) % MaxCount;
    
    return YES;
}
/ / out of the team
BOOL outQueue(HYQueue *hq, int *outData) {
    // Check whether the queue is empty
    if (isNull(*hq)) {
        printf("Queue empty \n");
        return NO;
    }
    / / out of the team
    *outData = hq->data[hq->front];
    hq->front = (hq->front + 1) % MaxCount;
    
    return YES;
}
/ / traverse
void foreachQueue(HYQueue hq) {
    while(hq.front ! = hq.rear) {printf("%-5d", hq.data[hq.front]);
        hq.front = (hq.front + 1) % MaxCount;
    }
    printf("\n");
}
// Test the code
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // Create a queue
        HYQueue hq = initQueue();
        // Join the queue, when only in the queue but not out of the queue, this will waste a space, because the default value of front is 0, but 0 is not out of the queue
        for (int i = 0; i < 15; i++) {
            inQueue(&hq, i);
        }
        foreachQueue(hq);
        / / out of the team
        for (int i = 0; i < 10; i++) {
            int data = 0;
            outQueue(&hq, &data);
            printf("%-5d out of line \n", data);
        }
        / / team again
        for (int i = 0; i < 20; i++) {
            inQueue(&hq, i + 15);
        }
        foreachQueue(hq);
    }
    return 0;
}
Copy the code

Chain queue

The chained queue has the following advantages over the sequential queue:

The length is infinite, the used space is released directly, there is no waste of space like non-cyclic sequential queue.
There will be no team full situation, there is no team empty and team full conflict problem.
Joining and unjoining are simple. Joining is to insert a node at the end of the list, and unjoining is to delete the head node.

Disadvantages: The disadvantages of linked lists, not easy to traverse, need to maintain the opening and release of node space.

Personally, I think it’s better to use chained storage for queues. Implementation code:

#import <Foundation/Foundation.h>

// Define a node
typedef struct _Node {
    int data;
    struct _Node *next;
} Node;
// Define the queue
typedef struct {
    Node *front;        / / team head
    Node *rear;         / / of the
} HYQueue;

// Initialize the queue
HYQueue initQueue(void) {
    HYQueue hq;
    hq.front = NULL;
    hq.rear  = NULL;
    return hq;
}
// The queue is empty
BOOL isNull(HYQueue hq) {
    return (hq.rear == NULL) && (hq.front == NULL);
}
// No queue full, no judgment

/ / team
void inQueue(HYQueue *hq, int data) {
    // Create a node
    Node *node = malloc(sizeof(Node));
    node->next = NULL;
    node->data = data;
    / / team
    if (isNull(*hq)) {
        hq->rear  = node;
        hq->front = node;
    }
    else{ hq->rear->next = node; hq->rear = node; }}/ / out of the team
BOOL outQueue(HYQueue *hq, int *data) {
    if (isNull(*hq)) {
        printf("No element in queue, cannot exit queue \n");
        return NO;
    }
    Node *p = hq->front;
    *data = p->data;
    // Check whether there is only one node
    if (hq->front == hq->rear) {
        // The pointer is null
        hq->front = hq->rear = NULL;
    }
    else {
        // A pointer to the next node
        hq->front = hq->front->next;
    }
    p->data = 0;
    p->next = NULL;
    free(p);
    return YES;
}
/ / traverse
void foreachQueue(HYQueue hq) {
    while (hq.front) {
        printf("%-5d", hq.front->data);
        hq.front = hq.front->next;
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // Create a queue
        HYQueue hq = initQueue();
        / / team
        for (int i = 0; i < 20; i++) {
            inQueue(&hq, i);
        }
        foreachQueue(hq);
        / / out of the team
        for (int i = 0; i < 10; i++) {
            int data = 0;
            outQueue(&hq, &data);
            printf("%d- > out of line \n", data);
        }
        foreachQueue(hq);
    }
    return 0;
}
Copy the code

— — — — — — — — — — — — — — — — — — — — – I am a line — — — — — — — — — — — — — — — — — — — — — — — —

Problem off

Now that the stack and queue related concepts and implementations have been covered, here is a little digress.

recursive

What’s the recursion? In plain English, recursion is a function that calls the function under some internal conditions.

// As in the following two functions
// Print a a-1 a-2 ··· 21
void printInt(int a) {
    if (a > 0) {
        printf("%-5d", a);
        printInt(a - 1);
    }
    else {
        printf("\n"); }}// Calculate 1 + 2 + 3 + ··· + a-1 + a
int sumInt(int a) {
    if (a > 0) {
        return a + sumInt(a - 1);
    }
    return 0;
}
Copy the code

Problems that recursion can solve

The definition of the problem is recursion. Such as Fibonacci series, factorial, order addition and so on.
The data structure is recursive. Data structures themselves are recursive, such as linked lists, trees, etc.
The solution to the problem is recursive. Some problems have no obvious recursive structure, but it is easier to solve them recursively than iteratively.

Divide and conquer method

The idea of divide-and-conquer is to divide a big problem that is difficult to solve directly into smaller, identical or similar problems so that they can be broken down separately.

Problems that can be solved by divide-and-conquer generally have the following characteristics:

The problem can be easily solved if it is scaled down to a certain extent.
The problem can be broken down into several smaller identical problems.
The solution of the word problem decomposed by the problem can be combined to solve the problem.
The subproblems decomposed from this problem are independent of each other.

The basic steps of divide-and-conquer:

Decomposition: Decompose the original problem into several smaller, independent sub-problems of the same form as the original problem.
Solution: some problems are small and easy to be solved directly, otherwise, recursively solve each sub-problem.
Merge: Combine solutions of subproblems into solutions of the original problem.

Dynamic programming

To put it simply, dynamic programming is the method to dynamically select the optimal process in the process of solving multi-order decision making. That is, step by step, improvisation, dynamic programming, to ensure that every step must be optimal, then the optimal solution of these sub-problems combined is the optimal solution of the problem.

Differences with divide-and-conquer:

Subproblems are generally not independent of each other. It can be understood as an improvement of the divide-and-conquer method, which does not need to solve the subproblem of the existing solution (the subproblem of the existing solution can be recorded).

Applicable conditions:

Principle of optimization (optimal substructure) : The subpolicies of an optimal policy are always optimal, that is, local optimal, global optimal.
No aftereffect: Each state is a complete summary of past history.
Subproblem overlap: high efficiency (Optimal substructure: when the optimal solution of a problem contains the optimal solution of its subproblem, the problem is said to have the most substructure; An overlapping subproblem is a recursive solution that contains many subproblems, but few different subproblems. A small number of subproblems are repeated many times.
Optimization principle of dynamic programming: as a property of the whole process strategy, no matter what the past decisions are, the remaining decisions must be procedually optimal for the state formed by the previous decisions.

conclusion

This article describes the concepts and characteristics of stacks and queues, and how to implement both data structures using sequential storage and chained storage, respectively.

The other thing is that it summarizes the concept of recursion and what problems can recursion solve?

Also understand the following divide-and-conquer method and dynamic programming method of their respective characteristics, as well as the differences and connections between them. (THIS part of my own understanding is not too deep, I read the explanation of other people’s articles and my own understanding to write down, if there is not enough understanding, you are welcome to correct, I will update this part of the content when I have a deeper understanding).

This paper addresses https://juejin.cn/post/6844904150321496071

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structures and algorithms 4 — Stacks and queues

preface

The stack

Order of the stack

Chain stack

The queue

The order queue

Chain queue

Problem off

recursive

Problems that recursion can solve

Divide and conquer method

Dynamic programming

Differences with divide-and-conquer:

Applicable conditions:

conclusion

Data structures and algorithms 4 — Stacks and queues

preface

The stack

Order of the stack

Chain stack

The queue

The order queue

Chain queue

Problem off

recursive

Problems that recursion can solve

Divide and conquer method

Dynamic programming

Differences with divide-and-conquer:

Applicable conditions:

conclusion

Related Posts

Do you really judge _objc_msgForward_stret

Ali, Byte: a set of effective iOS interview questions

Circular references in iOS