栈

栈的概念和结构

栈：只允许在固定的一端进行插入和删除元素的操作.进行数据的插入和删除的一端称为栈顶,另一端称为栈底.栈中的数据元素遵循LIFO（Last in First out）原则.

入栈：栈的插入操作叫做进栈/压栈/入栈.

出栈：栈的删除操作叫做出栈.

栈的实现

The idea of ​​stack and its structure are as described in the above figure,The ability to implement the above operations is called a stack,方法有挺多,但是一般使用数组或者链表实现,而其中数组Again the most common,Because compared to the linked list,Arrays have more advantages in tail insertion and tail deletion.

Sequence lists are implemented using arrays,So the stack implemented by array here has many similarities with the sequence list.

栈的结构声明

typedef int StackDateType;
typedef struct Stack
{
    
	StackDateType* array;
	int top;
	int capacity;
}Stack;

topThe subscript is always next to the top element on the stack,同时topIt also represents the number of elements in the stack;

capacityis the total capacity of the stack,当top与capacity相等时,需要扩容.

栈的初始化

void StackInit(Stack* p){
    
	assert(p);
	p->array = NULL;
	p->top = p->capacity = 0;
}

The initialization of the stack can also give space,It's okay not to give space(Give space when inserting elements).

栈的销毁

void StackDestroy(Stack* p){
    
	assert(p);
	free(p->array);
	p->array = NULL;
	p->top = p->capacity = 0;
}	

The inserted element of the stack（入栈）

void StackPush(Stack* p, StackDateType data){
    
	assert(p);
  //扩容
	if(p->top == p->capacity){
    
    //When using the stack for the first time,栈为空时,stack first4个元素的大小,each time it is expanded,doubled
		int NewCapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		StackDateType* NewArray = (StackDateType*)realloc(p->array, sizeof(StackDateType) * NewCapacity);
		if(NewArray == NULL){
    
			perror("realloc fail");
			exit(-1);
		}
		p->array = NewArray;
		p->capacity = NewCapacity;
	}
  //Insert an element into the stack,并且top自增
	p->array[p->top++] = data;
}

Removed element from the stack（出栈）

void StackPop(Stack* p){
    
	assert(p);
  //Assert when the stack is empty,无法出栈
	assert(!StackEmpty(p));
  //Since the stack is implemented by an array,The subscript is used to access the array,So when the end of the array is deleted,Just decrement the subscriptok
	p->top--;
}

获取栈顶元素

StackDateType StackTop(Stack* p){
    
	assert(p);
  //Assert when the stack is empty,无法获取栈顶元素
	assert(!StackEmpty(p));
  //由于top是栈顶元素的下一个元素的下标,So when getting the top element of the stack,需要top - 1
	return p->array[p->top - 1];
}

判断栈为空

int StackEmpty(Stack* p){
    
	assert(p);
  //topRepresents the number of elements in the stack,所以当top为0时,栈为空
	return p->top == 0;
}

Get the number of elements in the stack

int StackSize(Stack* p){
    
	assert(p);
  //topRepresents the number of elements in the stack
	return p->top;
}

队列

队列的概念和结构

队列：Inserting elements is only allowed at one end,Delete elements in another segment,The end that does the insertion of data is called队尾,The end that does the deletion of data is called队头.队列中的数据元素遵循FIFO（First in First out）原则.

入队：插入元素称为入队.

出队：删除元素称为出队.

队列的实现

Queues have a first-in, first-out feature,Therefore, tail insertion and head deletion are required,The head deletion is more good at linked lists,So using a linked list to implement a queue is the most common.

The structure declaration of the queue

typedef int QueueDateType;
typedef struct QueueNode{
    
	struct QueueNode* next;
	QueueDateType val;
}QueueNode;
typedef struct Queue{
    
	QueueNode* front;//指向链表的头
	QueueNode* back;//指向链表的尾
  int size;//Represents the number of nodes in the linked list
}Queue;

Here are two structures,The first is used to form a linked list,The second one is used to control the linked list.

队列的初始化

void QueueInit(Queue* p){
    
	assert(p);
	p->front = p->back = NULL;
	p->size = 0;
}

队列的销毁

void QueueDestroy(Queue* p){
    
	assert(p);
  //The classic operation of destroying a linked list
	QueueNode* curr = p->front;
	while(curr){
    
		QueueNode* next = curr->next;
		free(curr);
		curr = next;
	}
	p->front = p->back = NULL;
	p->size = 0;
}

The inserted element of the queue（入队）

void QueuePush(Queue* p, QueueDateType val){
    
	assert(p);
  //创建结点
	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
	if(node == NULL){
    
		perror("malloc fail");
		exit(-1);
	}
	node->next = NULL;
	node->val = val;
  //Associate the node with the head and tail pointers
  //若back为空,Then the queue has no node at this time,为空,所以将front和back都指向该结点
	if(p->back == NULL){
    
		p->front = p->back = node;
	}
  //此时,队列不为空,frontwill always point to the first node,而backA new node needs to be linked,并且更新back的指向
	else{
    
		p->back->next = node;//链接新结点
		p->back = node;//更新back的指向
	}
	p->size++;//Number of queue elements plus1
}

The removed element of the queue（出队）

void QueuePop(Queue* p){
    
	assert(p);
  //断言一下,当队列为空时,无法出队
	assert(!QueueEmpty(p));
  //当队列只有一个元素时
	if(p->front->next == NULL){
    
		free(p->front);
		p->front = p->back = NULL;
	}
  //When the queue has multiple elements,头删
	else{
    
		QueueNode* next = p->front->next;
		free(p->front);
		p->front = next;
	}
	p->size--;//队列元素数量减1
}

获取队头元素

QueueDateType QueueFront(Queue* p){
    
	assert(p);
	assert(!QueueEmpty(p));
	return p->front->val;
}

获取队尾元素

QueueDateType QueueBack(Queue* p){
    
	assert(p);
	assert(!QueueEmpty(p));
	return p->back->val;
}

判断队列为空

int QueueEmpty(Queue* p){
    
	assert(p);
	return p->size == 0;
}

获取队列中元素的数量

int QueueSize(Queue* p){
    
	assert(p);
	return p->size;
}