栈的概念以及结构
栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
栈的结构
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
知道了栈的概念以及结构，接下来我们来实现一下栈。
栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的
代价比较小。我们这里实现数组栈。
结构：
typedef int STDateType; typedef struct Stack { STDateType* arr; int top; int capacity; }Stack;
栈的接口
// 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDateType x); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDateType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);
各个接口的实现
有了顺序表的基础，栈与其相比就太简单了。大家直接看代码就知道了：
// 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->arr = NULL; ps->capacity = 0; ps->top = 0; } // 入栈 void StackPush(Stack* ps, STDateType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDateType* pa = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType)); if (ps == NULL) { perror("realloc fail"); exit(-1); } ps->arr = pa; ps->capacity = newcapacity; } ps->arr[ps->top] = x; ps->top++; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(ps ->top > 0); ps->top--; } // 获取栈顶元素 STDateType StackTop(Stack* ps) { assert(ps); return ps->arr[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 检测栈是否为空 bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0 ? true : false; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = 0; ps->top = 0; }
队列的概念和结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
队列的结构
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。所以我们用链表来实现队列。
typedef int QDataType; typedef struct QNode { QDataType date; struct QNode* next; }QNode; typedef struct Queue { QNode* head; //记录尾，方便入队 QNode* tail; //记录队列里有效数据的个数 int size; }Queue;
队列的实现
队列的接口
//初始化队列 void QueueInit(Queue* pq); //入队列 void QueuePush(Queue* pq, QDataType x); //出队列 void QueuePop(Queue* pq); //获取队头的元素 QDataType QueueFront(Queue* pq); //获取队头尾的元素 QDataType QueueBack(Queue* pq); //获取队列中有效数据的个数 int QueueSize(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); //销毁队列 void QueuDestroy(Queue* pq);
接口的实现
//初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } //入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->date = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } //出队列 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } //获取队头的元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->date; } //获取队头尾的元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->date; } //获取队列中有效数据的个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; } //判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } //销毁队列 void QueuDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; }
有效的括号
这个题放在这里讲，它一定是需要用到栈的，但是由于我们的C语言没有栈，所以我们写这个题时需要手写一个栈，我们这里说一下思路，括号匹配，我们可以将左括号入栈，然后碰到右括号然后保存栈顶的元素，然后出栈，然后看是否匹配，匹配的情况我们不关心，但是只要不匹配我们就返回false，但是每次是右括号是我们都要判断是不是空栈，如果是空栈，就一定不匹配，这是我们要返回false，等字符串遍历完一遍后，如果不是空栈，就一定不匹配，返回false，但是如果字符串遍历完了，是空栈，就一定匹配，返回true，注意在返回之前一定要销毁栈。
代码：
typedef char STDateType; typedef struct Stack { STDateType* arr; int top; int capacity; }Stack; // 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->arr = NULL; ps->capacity = 0; ps->top = 0; } // 入栈 void StackPush(Stack* ps, STDateType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDateType* pa = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType)); if (ps == NULL) { perror("realloc fail"); exit(-1); } ps->arr = pa; ps->capacity = newcapacity; } ps->arr[ps->top] = x; ps->top++; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(ps ->top > 0); ps->top--; } // 获取栈顶元素 STDateType StackTop(Stack* ps) { assert(ps); return ps->arr[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 检测栈是否为空 bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0 ? true : false; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = 0; ps->top = 0; } bool isValid(char * s) { Stack st; StackInit(&st); char top = 0; while(*s) { if(*s=='('||*s=='{'||*s=='[') { StackPush(&st,*s); } else { //数量不匹配 if(StackEmpty(&st)) { StackDestroy(&st); return false; } else { top = StackTop(&st); StackPop(&st); //判断是否匹配 if((top=='['&&*s!=']') ||top=='('&&*s!=')' ||top=='{'&&*s!='}') { StackDestroy(&st); return false; } } } *s++; } //判断数量是否匹配 if(!StackEmpty(&st)) { StackDestroy(&st); return false; } StackDestroy(&st); return true; }
