栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。栈向下增长
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
动态开辟在堆区，堆向上增长，递归次数过多会导致栈溢出
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
习题
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
B 先进后出
2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
C A1先入，再出1，然后入2，3，4，出4，3，2
B先入1，2出2，入3，出3，入4，出4，出1
D入1，2，3出3，入4，出4，出2，出1
结构体的创建
typedef int STDdtaTtype; typedef struct Stcak { STDdtaTtype* data; int top; int capacity; }ST;
初始化
void StackInit(ST* ps) { assert(ps); ps->data = NULL; ps->capacity = ps->top = 0; }
销毁开辟空间
void StackDestory(ST* ps) { assert(ps); free(ps->data); ps->capacity = ps->top = 0; ps->data = NULL; }
入栈
void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1 { assert(ps); int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; if (ps->capacity == ps->top)//判断是否满了 { STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->data = tmp; ps->capacity = newcapacity; } ps->data[ps->top] = x; ps->top++; }
出栈
void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; }
当前栈顶
STDdtaTtype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->data[ps->top - 1]; }
判断栈是否为空
bool StackEmpty(ST* ps)//判断是否为空栈 { assert(ps); return ps->top == 0; }
统计个数
int StackSize(ST* ps) { assert(ps); return ps->top; }
力扣习题——有效的括号
20. 有效的括号 - 力扣（LeetCode）
当s指向左括号时，把该括号放入栈内
入完栈之后s不等于左括号，s等于右括号，然后将栈内的元素一个个拿出来跟s所指括号比较，若能匹配成功，则进行下一轮比较，反之则直接返回false
typedef char STDdtaTtype; typedef struct Stcak { STDdtaTtype* data; int top; int capacity; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps, STDdtaTtype x); void StackPop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps); STDdtaTtype StackTop(ST* ps); void StackInit(ST* ps) { assert(ps); ps->data = NULL; ps->capacity = ps->top = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->data); ps->capacity = ps->top = 0; ps->data = NULL; } void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1 { assert(ps); int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; if (ps->capacity == ps->top)//判断是否满了 { STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->data = tmp; ps->capacity = newcapacity; } ps->data[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; } STDdtaTtype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->data[ps->top - 1]; } bool StackEmpty(ST* ps)//判断是否为空栈 { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
把上面栈的函数都复制下来，进行括号匹配
bool isValid(char * s){ ST st; StackInit(&st); while(*s) { if(*s=='['||*s=='{'||*s=='(') { StackPush(&st,*s); } else { if(StackEmpty(&st))//若栈内为空，直接返回false，这种情况如只S数组只有一个[ { StackDestory(&st);//防止内存泄漏 return false; } STDdtaTtype top=StackTop(&st); StackPop(&st); if(*s==']'&&top!='[' ||*s=='}'&&top!='{' ||*s==')'&&top!='(') { return false; } } s++; } bool flag=(StackEmpty(&st));//若全部匹配则，栈内为空，若没有则不为空 StackDestory(&st); return flag; }
队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头，一般用单链表实现队列，双向链表比较浪费
结构体的建立
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; size_t size; }Queue;
初始化
void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
动态内存销毁
void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); del = NULL; } pq->head = pq->tail = NULL; }
入队
void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; }
出队
void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; }//如果只剩一个节点，单独处理，要不染当head遍历到tail时候，tail会成为野指针，这里要防止tail变为野指针 else { QNode* cur = pq->head; pq->head = pq->head->next; free(cur); cur = NULL; } pq->size--; }
提取数据
QDataType QueueFront(Queue* pq)//取头数据 { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq)//取尾数据 { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
判断是否为空
bool QueueEmpty(Queue* pq) { assert(pq); return pq->head==NULL && pq->tail==NULL; }
队内元素个数统计
int QueueSize(Queue* pq) { return pq->size; }
