每日算法题【栈和队列】：栈和队列的实现、有效的括号、设计循环队列

(1)栈的实现

// 支持动态增长的栈
typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;		// 栈顶int capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* ps){//判空assert(ps);//初始化ps->a = NULL;ps->top = ps->capacity = 0;	//top = 0，top指向的是下一个要插入的位置
}// 入栈 
void StackPush(Stack* ps, STDatatype data){assert(ps);//如果没有空间插入需要申请空间扩容if(ps->top == ps->capacity){//先给容量标志位更新到扩容之后的容量int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//再给数组进行扩容STDatatype* tmp = (STDatatype*)realloc(ps->a,newcapacity*sizeof(STDatatype));//检查是否扩容成功if(tmp == NULL){perror("realloc fail");return;}//成功就进行更新ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = data;ps->top++; 
}// 出栈 
void StackPop(Stack* ps){assert(ps);//删除数据之前确保有数据assert(ps->top > 0);ps->top--;
}// 获取栈顶元素 
STDatatype StackTop(Stack* ps){assert(ps);assert(pd->top > 0);return ps->a[ps->top-1];
}// 获取栈中有效元素个数 
int StackSize(Stack* ps){assert(ps);return ps->top;
} // 检测栈是否为空，如果为空返回true，如果不为空返回fasle
int StackEmpty(Stack* ps){assert(ps);if(ps->top == 0){return true;}else{return false;}
}// 销毁栈 
void StackDestroy(Stack* ps){assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

(2)括号匹配问题

• [20. 有效的括号 - 力扣（LeetCode）]:

• 解题思路：

  • 如果是左括号就入栈，如果是右括号就出栈进行比较，如果比较相同类型就出栈并继续这一步骤，如果是不同类型或者栈为空就报错
  • 当s全部被遍历一遍之后，查看栈中是否还有符号，有就报错，没有就返回true

  bool isValid(char* s) {Stack st;StackInit(&st);while(*s){//如果是左括号就入栈if(*s == '('|| *s == '{'|| *s == '['){StackPush(&st,*s);++s;}else{//如果是右括号就出栈进行比较//如果栈中没有左括号，则不匹配if(StackEmpty(&st) == true){StackDestroy(&st);return false;}//如果出栈的括号不匹配也返回falseSTDatatype top = StackTop(&st);StackPop(&st);if((*s == '}' && top != '{')|| (*s == ')' && top != '(')|| (*s == ']' && top != '[')){StackDestroy(&st);return false;}else{++s;}}}//当s全部被遍历一遍之后，查看栈中是否还有符号，有就报错，没有就返回truebool ret = StackEmpty(&st);StackDestroy(&st);return ret == false ? false : true;}
  

(3)队列的实现

// 链式结构：表示队列 
//队列中的节点
typedef struct QListNode 
{ struct QListNode* next; QDatatype val; 
}QNode; // 队列的结构 
typedef struct Queue 
{ QNode* head; //链表头QNode* tail;  //链表尾int size;	//记录队列中的元素个数
}Queue; // 初始化队列 
void QueueInit(Queue* q){assert(q);q->head = NULL;q->tail = NULL;q->size = 0;
}// 队尾入队列 
void QueuePush(Queue* q, QDatatype x){assert(q);//为新节点申请空间QNode* newnode = (QNode*)malloc(sizeof(QNode));if(newnode == NULL){perror("malloc fail");return;}//对新节点进行初始化newnode->next = NULL;newnode->val = x;//如果队列链表为空if(q->tail == NULL){q->head = q->tail = newnode;}else{//如果队列链表不为空q->tail->next = newnode;q->tail = newnode;}q->size++;
}// 队头出队列 
void QueuePop(Queue* q){assert(q);assert(q->tail != NULL); //不能对空链表进行头删//如果链表只有一个节点if(q->size == 1){free(q->head); //释放点head指针所指的节点q->head = q->tail = NULL;}else{//如果链表有多个节点QNode* Next = q->head->next;free(q->head);q->head = Next;}q->size--;   
}// 获取队列头部元素 
QDatatype QueueFront(Queue* q){assert(q);assert(q->tail != NULL);return q->head->val;
}// 获取队列队尾元素 
QDatatype QueueBack(Queue* q){assert(q);assert(q->tail != NULL);return q->tail->val;   
}// 获取队列中有效元素个数 
int QueueSize(Queue* q){assert(q);return q->size;
}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q){assert(q);    return q->size == 0; //队列为空返回TRUE 不为空返回FALSE
}// 销毁队列 
void QueueDestroy(Queue* q){assert(q);//循环遍历释放队列链表的每一个节点QNode* cur = q->head;while(cur){QNode* Next = cur->next;free(cur);cur = Next;}q->head = NULL;q->tail = NULL;q->size = 0;
}

(4)设计循环队列

• [622. 设计循环队列 - 力扣（LeetCode）]:

• 解题思路：

  循环队列的结构：
  在普通的线性队列中，队列指针（如队头指针和队尾指针）的范围是从 0 到队列容量减一。而在循环队列中，队尾指针在达到队列容量时不再继续增加，而是从队列的开头重新开始，形成了一个环形结构。

  取模运算的作用：
  在循环队列中，我们使用取模运算（%）来实现队列指针的循环移动。具体来说，当队尾指针需要向后移动时，我们计算新的队尾位置为 (tail + 1) % capacity，其中 tail 是当前队尾指针的位置，capacity 是队列的容量。这样可以保证当队尾指针达到队列容量时，取模运算会使其重新回到队列的开头，实现了环形结构。

  #include<stdio.h>
  #include<stdlib.h>
  #include<stdbool.h>typedef struct {int * array; //数组指针int front; //队头指针int rear; //队尾指针int capacity; //容量int size; //有效元素个数    
  } MyCircularQueue; //先进先出结构// 函数前向声明
  MyCircularQueue* myCircularQueueCreate(int k);
  bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);
  bool myCircularQueueDeQueue(MyCircularQueue* obj);
  int myCircularQueueFront(MyCircularQueue* obj);
  int myCircularQueueRear(MyCircularQueue* obj);
  bool myCircularQueueIsEmpty(MyCircularQueue* obj);
  bool myCircularQueueIsFull(MyCircularQueue* obj);
  void myCircularQueueFree(MyCircularQueue* obj);//创建环形队列
  MyCircularQueue* myCircularQueueCreate(int k) {//申请循环队列结构体的内存空间MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请队列数组的内存空间obj->array = (int*)malloc(k * sizeof(int));obj->capacity = k;obj->size = 0;obj->front = 0;obj->rear = -1; //初始化队尾指针为-1，这样第一个元素的下标正好是0return obj;
  }//插入值
  bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {// 如果队列已满，则返回 falseif (myCircularQueueIsFull(obj)) {return false;}// 队尾指针后移一位，考虑到环形结构，使用取模运算确保指针位置在合法范围内（尾进）obj->rear = (obj->rear + 1) % obj->capacity;// 将元素值插入到队尾指针所指向的位置obj->array[obj->rear] = value;obj->size++;  // 更新队列的当前元素个数return true;
  }//删除值
  bool myCircularQueueDeQueue(MyCircularQueue* obj) {// 如果队列为空，则返回 falseif (myCircularQueueIsEmpty(obj)) {return false;}// 队头指针后移一位，考虑到环形结构，使用取模运算确保指针位置在合法范围内（头出）obj->front = (obj->front + 1) % obj->capacity;obj->size--;  // 更新队列的当前元素个数return true;
  }//返回队首元素
  int myCircularQueueFront(MyCircularQueue* obj) {return myCircularQueueIsEmpty(obj) ? -1 : obj->array[obj->front]; //如果队列为空返回-1
  }//返回队尾元素
  int myCircularQueueRear(MyCircularQueue* obj) {return myCircularQueueIsEmpty(obj) ? -1 : obj->array[obj->rear]; //如果队列为空返回-1
  }//判断队列是否为空
  bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
  }//判断队列是否为满
  bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
  }//循环队列的销毁
  void myCircularQueueFree(MyCircularQueue* obj) {free(obj->array);  // 先释放数组内存free(obj);         // 再释放结构体内存
  }/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
  */