栈和队列
栈
栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除操作。**进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。**栈中的数据元素遵守后进先出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
出栈就是少一个栈顶元素。
栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
初始化栈
void StackInit(Stack* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { perror("malloc fail"); exit(-1); } ps->top = 0; ps->capacity = 4; }
入栈
void StackPush(Stack* ps, STDataType x) { assert(ps); //判断栈是否满了，如果满了就扩容 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; 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]; }
获取栈中有效元素个数
int StackSize(Stack* ps) { assert(ps); return ps->top; }
判断栈是否为空
bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; }
销毁栈
void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
括号匹配问题
思路：这题主要思路，就是遇见左括号就入栈，遇见右括号就将栈顶元素，拿出来对比是否匹配，如果不匹配就直接返回
false.
typedef char STDatatype; typedef struct Stack { STDatatype* a; int capacity; int top; // 初始为0，表示栈顶位置下一个位置下标 }ST; bool StackEmpty(ST* ps) { assert(ps); return ps->top == -1; } void StackInit(ST* ps) { assert(ps); //ps->a = NULL; //ps->top = 0; //ps->capacity = 0; ps->a = (STDatatype*)malloc(sizeof(STDatatype)* 4); if (ps->a == NULL) { perror("malloc fail"); exit(-1); } ps->top = -1; ps->capacity = 4; } void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = -1; ps->capacity = 0; } void StackPush(ST* ps, STDatatype x) { assert(ps); // if (ps->top+1 == ps->capacity) { STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->top++; ps->a[ps->top] = x; } // 20:20 void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } STDatatype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top]; } int StackSize(ST* ps) { assert(ps); return ps->top+1; } bool isValid(char * s){ ST st; StackInit(&st); while(*s) { if(*s == '[' || *s == '(' || *s == '{') { StackPush(&st, *s); s ++; }else { if(StackEmpty(&st)) { StackDestroy(&st); return false; } char top = StackTop(&st); StackPop(&st); if(*s == ']' && top != '[' || *s == '}' && top != '{' || *s == ')' && top != '(') { StackDestroy(&st); return false; }else { s ++; } } } bool ret = StackEmpty(&st); StackDestroy(&st); return ret; }
由于C语言没有栈这个类，所以我们需要自己实现栈，并调用来实现。
队列
队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出特性。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为对头
队列的实现
队列也可以数组和链表的结构实现，使用链表的结构更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率比较低。
初始化队列
void QueueInit(Queue* q) { assert(q); q->front = NULL; q->rear = NULL; q->size = 0; }
队尾入队列
void QueuePush(Queue* q, QDataType data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = data; newnode->pNext = NULL; if (q->rear == NULL) { q->front = q->rear = newnode; } else { q->rear->pNext = newnode; q->rear = newnode; } q->size++; }
队头出队列
void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q->front->pNext == NULL) { free(q->front); q->front = q->rear = NULL; } else { QNode* del = q->front; q->front = q->front->pNext; free(del); } q->size--; }
获取队头元素
QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->front->data; }
获取队尾元素
QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->rear->data; }
销毁队列
void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->front; while (cur) { QNode* del = cur; cur = cur->pNext; free(del); } q->front = q->rear = NULL; q->size = 0; }
判断队列是否为空
bool QueueEmpty(Queue* q) { assert(q); return q->front == NULL && q->rear == NULL; }
用队列实现栈
思路：
队列：先进先出 栈：先进后出
保持一个队列存数据，一个队列为空，队列出数据是在队头的，而栈相当于在队尾出数据。
代码：
typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); }else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj) { Queue* emptyQ = &obj->q1; Queue* noemptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; noemptyQ = &obj->q1; } while(QueueSize > 1) { QueuePush(emptyQ, QueueFront(noemptyQ)); QueuePop(noemptyQ); } int top = QueueFront(noemptyQ); QueuePop(noemptyQ); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); }else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
用栈实现队列
思路：两个栈一个栈用来插入数据，另一个栈用来弹出数据。
代码：
typedef struct { ST pushst; ST popst; } MyQueue; MyQueue* myQueueCreate() { MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&pq->pushst); StackInit(&pq->popst); return pq; } void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->pushst, x); } int myQueuePop(MyQueue* obj) { assert(obj); assert(!myQueueEmpty(obj)); int peek = myQueuePeek(obj); StackPop(&obj->popst); return peek; } int myQueuePeek(MyQueue* obj) { assert(obj); assert(!myQueueEmpty(obj)); if(StackEmpty(&obj->popst)) { while(!StackEmpty(&obj->pushst)) { StackPush(&obj->pushst, StackTop(&obj->popst)); StackPop(&obj->pushst); } } return StackTop(&obj->popst); } bool myQueueEmpty(MyQueue* obj) { assert(obj); return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst); } void myQueueFree(MyQueue* obj) { assert(obj); StackDestroy(&obj->pushst); StackDestroy(&obj->popst); free(obj); }
