【数据结构】栈和队列
文章目录
- 栈和队列
- 栈
- 栈的概念及结构
- 栈的实现
- 初始化栈
- 入栈
- 出栈
- 获取栈顶元素
- 获取栈中有效元素个数
- 判断栈是否为空
- 销毁栈
- 括号匹配问题
- 队列
- 队列的概念及结构
- 队列的实现
- 初始化队列
- 队尾入队列
- 对头出队列
- 获取队头元素
- 获取队尾元素
- 销毁队列
- 判断队列是否为空
栈和队列
栈
栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除操作。**进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。**栈中的数据元素遵守后进先出的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
出栈就是少一个栈顶元素。
栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
初始化栈
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; }