queue

concept

Queues are a special linear structure that allows deletion only at the head of the queue, which is called "queue out" and insertion at the tail of the queue, which is called "queue entry". When there are no elements in the queue (head = tail), it is called an empty queue.

Queues have the principle of Frist In Frist Out (FIFO).

code implementation

struct queue {
  int data[101];
  int head;
  int tail;
};

Stack

concept

Stack is a last in, first out data structure. Limited to insert and delete operations only in one paragraph.

Examples

For example, there is a small bucket, the diameter of the bucket can only be placed a small ball, now the bucket in turn into 2, 1, 3 small balls. If you need to take out the No. 2 ball now, you must take out the No. 3 ball and the No. 1 ball first, and finally you can get the No. 2 ball. In the process of picking up the ball, the first to put in the last to take out, and the last to put in the first to take out.

linked list

Solve the problem

When storing a large wave number, arrays are usually used, but sometimes arrays are not flexible enough, such as:

There is a list of numbers that have been sorted from small to large. Now it's necessary to insert a number into the sequence to make the new sequence fit from small to large.

Dynamic storage

For example, to store an integer 10 in a program, there is another dynamic storage method besides applying for an area in memory in the way of int a:

malloc(4);

If you are not sure how many bytes the type is, you can use sizeof(), for example:

malloc(sizeof(int));

code implementation

Each node consists of two parts. One part is used to store specific values, and the other part is used to store the address of the next node. For example:

// Link list node
struct node {
  int data;
  struct node *next;
};

#include <stdio.h>
#include <stdlib.h>

// Link list node
struct node {
  int data;
  struct node *next;
};

void insert(struct node *head, int n) {
  struct node *p, *t;
  
  t = head;

  while (t != NULL) {
    if (t->next == NULL || t->next->data > n) {
      // Insert the current node if the value of the last node or the next node is greater than the number of inserts to be inserted
      p = (struct node*)malloc(sizeof(struct node));
      p->data = n;
      p->next = t->next;
      t->next = p;
      break;
    }

    t = t->next;
  }
}

int main(void) {
  struct node *head, *p, *q, *t;
  int i, n, a;
  
  scanf("%d", &n);

  // Initialization header pointer is empty
  head = NULL;

  for (i = 0; i < n; i++) {
    scanf("%d", &a);

    // Apply for a space dynamically to store a node and point to it with the temporary pointer p
    p = (struct node *)malloc(sizeof(struct node));
    p->data = a;
    p->next = NULL;

    if (head != NULL) {
      // If the head pointer is not empty, it means that there is already a node. Insert the end of that node.
      q->next = p;
    } else {
      // If the head pointer is empty, it means that there is no node, and the head pointer points to the node.
      head = p;
    }

    // Replace the previous node
    // q is used to store the current node
    q = p;
  }

  scanf("%d", &n);

  insert(head, n);
  
  t = head;

  while (t != NULL) {
    printf("%d ", t->data);
    t = t->next;
  }

  printf("\n");

  return 0;
}

Array Realization-Analog Link List

Ways of realization

Declare two variables, the integer array data and the integer array right. Data is used to store the specific numbers of the sequence species, right is used to store the right position of each element of the current sequence species in the array data, and no is 0.

code implementation

#include <stdio.h>
#define NUM 100

int main(void) {
  int data[NUM], right[NUM], i, n, len = 1;

  for (i = 0; i < NUM; i++) {
    data[i] = 0;
    right[i] = 0;
  }

  scanf("%d", &n);

  for (i = 1; i <= n; i++) {
    scanf("%d", &data[i]);

    right[len] = len + 1;
    len++;
  }

  // insert
  scanf("%d", &data[len]);

  i = 1;

  while (i != 0) {
    if (data[right[i]] > data[len]) {
      // If the value of the next node of the current node is greater than the number to be inserted, insert the number into the middle
      right[len] = right[i];ight[len] = right[i];
      right[i] = len;
      break;
    }
    i = right[i];
  }

  i = 1;

  while (i != 0) {
    printf("%d ", data[i]);
    i = right[i];
  }

  printf("\n");

  return 0;
}

Card game - kitten fishing

#include <stdio.h>

// queue
struct queue {
  int data[101];
  int head;
  int tail;
} q1, q2;

// Stack
struct stack {
  int data[101];
  int top;
} cards;

// Simulated hand cards
int c1[101] = {2, 4, 1, 2, 5, 6};
int c2[101] = {3, 1, 3, 5, 6, 4};


// The first approach
void play(struct queue *q1) {
  // play
  int i, flag = 0, t = q1->data[q1->head];
  q1->head++;

  // matching
  for (i = 0; i < cards.top; i++) {
    if (cards.data[i] == t) {
      flag = 1;
      break;
    }
  }

  if (flag == 1) {
    // Successful matching
    while (cards.data[cards.top - 1] != t) {
      q1->data[q1->tail++] = cards.data[cards.top - 1];
      cards.top--;
    }

    q1->data[q1->tail++] = t;
  } else {
    // Matching failure
    // Put the cards in the pile.
    cards.data[cards.top++] = t;
  }
}

// Second

int main(void) {
  // Initialization stack
  cards.top = 0;
  // Initialize the player
  int i;
  q1.head = 0;
  q1.tail = 0;
  q2.head = 0;
  q2.tail = 0;
  for (i = 0; i < 6; i++) {
    q1.data[i] = c1[i];
    q1.tail++;
    q2.data[i] = c2[i];
    q2.tail++;    
  }

  while (q1.head < q1.tail && q2.head < q2.tail) {
    play(&q1);
    play(&q2);
  }

  if (q1.head == q1.tail) {
    printf("winer is q2\n");
  } else {
    printf("winer is q1\n");    
  }

  printf("q1:");
  for (i = q1.head; i < q1.tail; i++) {
    printf("%d ", q1.data[i]);
  }
  printf("\nq2:");  
  for (i = q2.head; i < q2.tail; i++) {
    printf("%d ", q2.data[i]);
  }
  printf("\n");  
  for (i = 0; i < cards.top; i++) {
    printf("%d ", cards.data[i]);
  }

  return 0;
}