目录
前言
这些题目所用语言为C语言，由于C语言未提供栈和队列的数据结构，所以需要我们手动实现栈和队列。此外熟练掌握栈和队列的性质对解题尤为重要
正文
1.leetcode.20 有效的括号
解题思路：遍历字符串，如果碰到 ' ( ' 或 ' [ ' 或 ' { ' 就入栈；如果碰到字符是 ' ) ' ，栈顶的元素又是 ' ( '，就将栈顶的元素出栈。其他两种情况与之类似。
解题实战：
typedef char STDataType; typedef struct Stack { STDataType* a; //动态开辟数组 int capacity; //记录栈的容量大小 int top; //记录栈顶的位置 }Stack; //栈的初始化 void StackInit(Stack* ps); //释放动态开辟的内存 void StackDestroy(Stack* ps); //压栈 void StackPush(Stack* ps, STDataType data); //出栈 void StackPop(Stack* ps); //读取栈顶的元素 STDataType StackTop(Stack* ps); //判断栈是否为空 bool StackEmpty(Stack* ps); //栈存储的数据个数 int StackSize(Stack* ps); void StackInit(Stack* ps) { assert(ps); //初始化时，可附初值，也可置空 ps->a = NULL; ps->capacity = 0; ps->top = 0; } void StackDestroy(Stack* ps) { assert(ps); //若并未对ps->a申请内存，则无需释放 if (ps->capacity == 0) return; //释放 free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps,STDataType data) { assert(ps); //若容量大小等于数据个数，则说明栈已满，需扩容 if (ps->capacity == ps->top) { //若为第一次扩容，则大小为4，否则每次扩大2倍 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } //压栈 ps->a[ps->top] = data; ps->top++; } void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); //出栈 ps->top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); //返回栈顶的数据 return ps->a[ps->top - 1]; } bool StackEmpty(Stack* ps) { assert(ps); //返回top return ps->top == 0; } int StackSize(Stack* ps) { assert(ps); return ps->top; } bool isValid(char* s) { Stack ST; StackInit(&ST); int pos=0; //遍历字符串，遇到'\0'结束 while(*(s+pos) != '\0') { if(*(s+pos) == '(' || *(s+pos) == '[' || *(s+pos) == '{') { StackPush(&ST,*(s+pos)); } else { if(StackEmpty(&ST)) return false; if((ST.top != 0) && (*(s+pos) == ')' && StackTop(&ST) == '(')|| (*(s+pos) == ']' && StackTop(&ST) == '[')|| (*(s+pos) == '}' && StackTop(&ST) == '{')) { StackPop(&ST); } else { return false; } } pos++; } if( StackEmpty(&ST) ) { return true; } else { return false; } }
2.leetcode.225 用队列实现栈
解题思路：首先我们要清楚栈和队列的性质：
栈：先进后出。只在尾部删数据。
队列：先进先出。只在头部删数据。
也就是说，添加数据时，两个是一样的，区别在于删数据时。栈要pop一个数据时，其实pop的是队尾的数据，而不巧的是，队列不能在队尾pop数据。所以此时，我们用两个队列来完成。
栈的结构定义用两个队列来实现。
typedef struct { Queue q1; Queue q2; int size; } MyStack;
3.用栈实现队列
解题思路：同上一题的思路，本题也是用两个栈实现队列。其中s1用来push，s2用来pop和peek。与上一题不同的是，这次pop时，不用一直将s1的数据导入到s2中。而是当s2为空时再导入。
解题实战：
typedef int STDataType; typedef struct Stack { STDataType* a; //动态开辟数组 int capacity; //记录栈的容量大小 int top; //记录栈顶的位置 }Stack; //栈的初始化 void StackInit(Stack* ps); //释放动态开辟的内存 void StackDestroy(Stack* ps); //压栈 void StackPush(Stack* ps, STDataType data); //出栈 void StackPop(Stack* ps); //读取栈顶的元素 STDataType StackTop(Stack* ps); //判断栈是否为空 bool StackEmpty(Stack* ps); //栈存储的数据个数 int StackSize(Stack* ps); void StackInit(Stack* ps) { assert(ps); //初始化时，可附初值，也可置空 ps->a = NULL; ps->capacity = 0; ps->top = 0; } void StackDestroy(Stack* ps) { assert(ps); //若并未对ps->a申请内存，则无需释放 if (ps->capacity == 0) return; //释放 free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps,STDataType data) { assert(ps); //若容量大小等于数据个数，则说明栈已满，需扩容 if (ps->capacity == ps->top) { //若为第一次扩容，则大小为4，否则每次扩大2倍 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } //压栈 ps->a[ps->top] = data; ps->top++; } void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); //出栈 ps->top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); //返回栈顶的数据 return ps->a[ps->top - 1]; } bool StackEmpty(Stack* ps) { assert(ps); //返回top return ps->top == 0; } int StackSize(Stack* ps) { assert(ps); return ps->top; } typedef struct { Stack s1; //用来push数据 Stack s2; //用来pop和peek } MyQueue; MyQueue* myQueueCreate() { MyQueue* myqueue = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&myqueue->s1); StackInit(&myqueue->s2); return myqueue; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->s1, x); } int myQueuePeek(MyQueue* obj) { //s2不为空时，不用再将s1的数据导入到s2 if(StackEmpty(&obj->s2)) { //将s1的数据倒着push到s2中 while (!StackEmpty(&obj->s1)) { STDataType top = StackTop(&obj->s1); StackPop(&obj->s1); StackPush(&obj->s2, top); } } //此时s2的数据是逆置的，所以栈顶的数据也就是队头的数据 return StackTop(&obj->s2); } int myQueuePop(MyQueue* obj) { STDataType top= myQueuePeek(obj); //此时s2的数据是逆置的，pop s2栈顶的数据，也就是pop队头的数据 StackPop(&obj->s2); return top; } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->s1) && StackEmpty(&obj->s2); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->s1); StackDestroy(&obj->s2); free(obj); obj = NULL;
4.设计循环队列
解题思路：循环队列与普通的队列就两点差别。
1.增加一个capacity来记录队列的容量
2.队尾与队头相连（称之为循环）
解题实战：
typedef int QDataType; typedef struct QueueNode { QDataType data; //存储的数据 struct QueueNode* next; //记录下一个结点的位置 }QNode; typedef struct { QNode* head; QNode* tail; int size; int capacity; } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* tmp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); tmp->head=NULL; tmp->tail=NULL; tmp->size=0; tmp->capacity=k; return tmp; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc fail"); exit(-1); } newNode->next = NULL; newNode->data = value; if (obj->size == 0) { obj->head = obj->tail = newNode; obj->size++; } else { obj->tail->next = newNode; obj->tail = newNode; newNode->next=obj->head; obj->size++; } return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; QNode* cur=obj->head; obj->head=obj->head->next; obj->tail->next=obj->head; free(cur); obj->size--; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->head->data; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->tail->data; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return !obj->size; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->size==obj->capacity; } void myCircularQueueFree(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { free(obj); return; } while(obj->head!=obj->tail) { QNode* cur=obj->head; obj->head=obj->head->next; free(cur); } free(obj->head); free(obj); obj=NULL; }
