# 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;
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.

## 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>

struct node {
int data;
struct node *next;
};

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

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

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 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.
}

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

scanf("%d", &n);

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

printf("\n");

return 0;
}``````

## 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;
int tail;
} q1, q2;

// Stack
struct stack {
int data;
int top;
} cards;

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

// The first approach
void play(struct queue *q1) {
// play
int i, flag = 0, t = q1->data[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.tail = 0;
q2.tail = 0;
for (i = 0; i < 6; i++) {
q1.data[i] = c1[i];
q1.tail++;
q2.data[i] = c2[i];
q2.tail++;
}

play(&q1);
play(&q2);
}

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;
}``````

Keywords: C

Added by kincet7 on Thu, 13 Jun 2019 01:33:34 +0300