catalogue

one , Stack

        introduce

        Initial preparation

        Initialization and destruction of stack

        Stack is empty

        Inbound and outbound

        Number of valid data in stack

        Stack top data

        All codes

two , queue

        introduce

        Initial preparation

        Queue initialization and destruction

        Queue is empty

        In queue and out queue

        Number of valid data in the queue

        Head and tail data

        All codes

one , Stack

introduce

Stack is a linear structure , Similar to linked list and sequential list , But it also has its uniqueness , Only stack top in , Stack ejection , So is the stack “ In and out ” perhaps “ Last in first out ”

The stack can adopt chain structure or array structure , Array structure is adopted here

Chain structure

Single linked list , The head is the top of the stack , Header insert data , Header delete data

 

Double linked list , Tail as stack top , Tail insert data , Tail delete data

Array structure

The tail is the top of the stack , The head is the bottom of the stack , Tail insert data , Tail delete data

 

Initial preparation

In order to make the stored data type not fixed , It can be easily modified when storing other types of data , So use typedef Modify type name

Then you have to build a structure , There are three members , One is the starting address of the dynamic array ( Pointer ), The other is the stack top variable , Used to fetch stack top data , Use and number of valid data when judging whether there is still space , Another is the array capacity
 

use typedef Change its type name , Make it simple and convenient to use

Initialization and destruction of stack

Initialize its three members , Null pointer , The other two are set to 0 that will do

When destroying the stack , Similar to initialization stack , Just an extra one free To free up space , Place memory leak

 

Stack is empty

Adopted here bool type , Determine whether the stack is empty , True is empty , If it is false, there is data

be careful : stay C Used in bool Type to reference header file stdbool.h

 

Inbound and outbound

Before entering data, you must first judge whether there is space , Increase capacity without , It is generally expanded to the original 2 times , Avoid frequent capacity expansion

Then add the data

When deleting data , You have to judge whether the stack is empty first , Otherwise, it keeps coming out , It's easy to make mistakes , Assertion is better

 

Number of valid data in stack

Valid data is top Size of , because top from 0 start , Every time you add data +1

 

Stack top data

When fetching stack top data , You have to judge whether the stack is empty first , Assertion is better

Because the number of valid data is larger than its subscript 1, So -1

All codes
// Header file #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h>
#include<stdbool.h> typedef int DataType; typedef struct Stack { DataType* a;
int top; int capacity; }ST; // Stack initialization void STInit(ST* ps); // Push void STPushTop(ST*
ps, DataType x); // Out of stack void STPopTop(ST* ps); // Stack top data DataType STTop(ST* ps);
// Number of valid data int STDataSize(ST* ps); // Destroy stack void STDestroy(ST* ps); // Stack is empty bool
STEmpty(ST* ps); // Definition file #include"Stack.h" void STInit(ST* ps) { assert(ps);
ps->a = NULL; ps->top = 0; ps->capacity = 0; } void STPushTop(ST* ps, DataType
x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity
== 0 ? 4 : 2 * ps->capacity; DataType* ptr = (DataType*)realloc(ps->a,
sizeof(DataType) * newcapacity); if (ptr == NULL) { printf("realloc fail\n");
exit(-1); } ps->a = ptr; ps->capacity = newcapacity; } ps->a[ps->top] = x;
ps->top++; } void STPopTop(ST* ps) { assert(ps); assert(!STEmpty(ps));
ps->top--; } bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } DataType
STTop(ST* ps) { assert(ps); assert(!STEmpty(ps)); return ps->a[ps->top - 1]; }
int STDataSize(ST* ps) { assert(ps); return ps->top; } void STDestroy(ST* ps) {
assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; } // Test file
#include"Stack.h" void test1() { ST st; STInit(&st); STPushTop(&st, 1);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 2);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 3);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 4);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 5);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STPushTop(&st, 6);
STPopTop(&st); printf("%d ", (&st)->a[(&st)->top]); STDestroy(&st); } void
test2() { ST st; STInit(&st); STPushTop(&st, 1); STPushTop(&st, 2);
STPushTop(&st, 3); STPushTop(&st, 4); printf("%d\n", STTop(&st));
STDestroy(&st); } int main() { test1(); //test2(); return 0; }
two , queue

introduce

Queue is also a linear structure , Similar to linked list and sequential list , But it also has its uniqueness , Only the tail of the team can enter , Team leader , So is the queue “ fifo ” perhaps “ last in last out ” 

Because it is not convenient to implement queue with array structure , Low efficiency , Whether the beginning of the array is the head of the team , Or the tail of the array as the head of the team , Move the data

The beginning of the array is the head of the team , End of array , Convenient data entry , But you have to get data from the beginning of the array , Header deletion , Need to move data forward , Relatively troublesome   

 

The beginning of the array is the end of the queue , The tail of the array is the head of the team , Input data must be input from the beginning of the array , Plug in , Need to move data back , so much trouble , Convenient data output

Therefore, the chain structure is better , Single linked list is used here

Initial preparation

In order to make the stored data type not fixed , It can be easily modified when storing other types of data , So use typedef Modify type name

Then you have to create a structure , have 2 Members , One is used to store data , Another address used to store the next data  

For the convenience of entering and leaving the queue , So two pointers are defined , A pointing head node , The other points to the tail node , The two are encapsulated together in the form of structure

  Queue initialization and destruction

Set the two pointers of the second structure to null

 

When destroying a queue , You have to traverse from the beginning , One by one free release , Finally, set the head pointer and tail pointer to null

Queue is empty

Judge whether the queue is empty , Just judge whether the header pointer is empty , Still use bool type

In queue and out queue

When data is queued , You have to use it first malloc Open up space , Then judge whether the development is successful , Then assign values to its members , Score two cases

The first is to enter data into the queue for the first time , Directly as head node

  The second is to link nodes at the end of the queue

Whether the queue is empty must also be considered when sending data , Data cannot be sent out all the time , Otherwise, random values will appear when fetching data , Using assertion judgment

There is another situation to consider when publishing data , Is when the last data is deleted , You have to set the tail pointer to null , Otherwise, a wild pointer will appear  

 

Number of valid data in the queue

Because the queue is implemented by a single linked list , Therefore, we can only use the method of traversing the count from the beginning node

  Head and tail data

  Since the head and tail pointers have been defined , So you can access it directly , Just judge whether the queue is empty

 

  All codes
// Header file #include<stdio.h> #include<stdlib.h> #include<assert.h>
#include<stdbool.h> typedef int DataType; typedef struct QueueNode { DataType
data; struct QueueNode* next; }QueueNode; typedef struct Queue { QueueNode*
head; QueueNode* tail; }Queue; // Initialize queue void QueueInit(Queue* pq); // Destroy queue void
QueueDestroy(Queue* pq); // Tail insertion void QueuePushBack(Queue* pq, DataType x);
// Header deletion void QueuePopFront(Queue* pq); // Header data DataType QueueTop(Queue* pq);
// Tail data DataType QueueTail(Queue* pq); // Queue is empty bool QueueEmpty(Queue* pq);
// Number of linked list data int QueueSize(Queue* pq); // Definition file #include"Queue.h" void
QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void
QueuePushBack(Queue* pq, DataType x) { assert(pq); QueueNode* newnode =
(QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { printf("malloc
fail\n"); exit(-1); } newnode->next = NULL; newnode->data = x; if (pq->head ==
NULL) { pq->head = newnode; pq->tail = pq->head; } else { pq->tail->next =
newnode; pq->tail = newnode; } } void QueuePopFront(Queue* pq) { assert(pq);
assert(!QueueEmpty(pq)); QueueNode* Next = pq->head->next; if (pq->head ==
pq->tail) { pq->tail = NULL; } free(pq->head); pq->head = Next; } bool
QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } DataType
QueueTop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return
pq->head->data; } DataType QueueTail(Queue* pq) { assert(pq);
assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Queue* pq) {
assert(pq); QueueNode* cur = pq->head; int count = 0; while (cur) { count++;
cur = cur->next; } return count; } void QueueDestroy(Queue* pq) { assert(pq);
QueueNode* cur = pq->head; while (cur) { QueueNode* next = cur->next;
free(cur); cur = next; } pq->head = NULL; pq->tail = NULL; } // Test file
#include"Queue.h" void test1() { Queue q; QueueInit(&q); QueuePushBack(&q, 1);
QueuePushBack(&q, 2); QueuePushBack(&q, 3); QueuePushBack(&q, 4);
QueuePushBack(&q, 5); QueuePopFront(&q); QueuePopFront(&q); QueuePopFront(&q);
QueuePopFront(&q); //QueuePopFront(&q); //QueuePopFront(&q); QueueNode* cur =
(&q)->head; while (cur) { printf("%d ", cur->data); cur = cur->next; }
QueueDestroy(&q); } void test2() { Queue q; QueueInit(&q); QueuePushBack(&q,
1); QueuePushBack(&q, 2); QueuePushBack(&q, 3); QueuePushBack(&q, 4); DataType
top = QueueTop(&q); printf("%d ", top); QueuePopFront(&q); top = QueueTop(&q);
printf("%d ", top); printf("\n"); DataType tail = QueueTail(&q); printf("%d ",
tail); printf("\n"); int sz = QueueSize(&q); printf("%d\n",sz);
QueuePopFront(&q); sz = QueueSize(&q); printf("%d\n", sz); QueueDestroy(&q); }
int main() { test1(); //test2(); return 0; }

Technology
©2019-2020 Toolsou All rights reserved,
Dynamic Simple registration login interface HTML+CSS+JQCSS Implement overflow display ellipsis 802.11 CCA and NAV mechanism Programmer refused due to low salary offer,HR become shame , Netizens instantly blew up ..abaqus Value of mass scaling factor _ABAQUS Mass scaling for Java Student information management system console version C Classic topics of language —— Insert a number into the sorted array Computer level 1 multi-point , How many points can I pass the computer test level 1 VINS-Fusion run kitti stereo and stereo+GPS data TS stay vue2 Writing in the project