大家中秋节快乐,玩了好几天没有学习,今天分享的是栈以及队列的相关知识,以及栈和队列相关的面试题
1.栈
1.1栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
1.2栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈的接口函数
// 初始化栈 voidStackInit(Stack*ps); // 入栈 voidStackPush(Stack*ps, STDataTypedata); // 出栈 voidStackPop(Stack*ps); // 获取栈顶元素 STDataTypeStackTop(Stack*ps); // 获取栈中有效元素个数 intStackSize(Stack*ps); // 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 intStackEmpty(Stack*ps); // 销毁栈 voidStackDestroy(Stack*ps);
栈的实现
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef struct Stack//定义一个栈的结构体变量 { int * a; int top; // 栈顶 int capacity; // 容量 }Stack; void StackInit(Stack* ps) { assert(ps);//断言,防止为空指针 ps->a = NULL;//所指向的地址为空 ps->capacity = ps->top = 0;//容量和栈中元素个数均为0 } void StackPush(Stack* ps, int data) { assert(ps); if (ps->capacity == ps->top)//如果栈中的元素个数等于栈的容量时考虑扩容, { int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果刚开始时都等于0,就先给4个空间大小,后面如果满的话,容量扩大1倍 int* newnode = (int*)realloc(ps->a,sizeof(int)* newcapcity);//申请空间,将申请好的空间首地址传给newnode指针 assert(newnode);//断言,防止malloc失败 ps->a = newnode;//将newnode保存的申请空间的首地址传给ps->a,让ps->a指向创建好的空间 ps->capacity = newcapcity;//容量大小更新为新容量大小 } ps->a[ps->top] = data;//像存数组一样存数据 ps->top++;//指向下一个 } // 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps->top ==0;//ps->top为栈中元素个数.==0栈中无元素,无元素要返回1, 无元素ps->t0p==0,这个表达式结果是1,返回1; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps));//防止栈内无元素,继续出栈 ps->top--; } // 获取栈顶元素 int StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1];//ps->top为栈中元素个数,由于数组下标是从0开始,所以栈顶元素下标为ps->top-1; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a);//free掉动态申请的内存 ps->a = NULL;//防止野指针 ps->capacity = ps->top = 0;//容量和栈中元素个数置为0 }
栈的功能测试
int main() { Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); while (!StackEmpty(&st)) { printf("%d", StackTop(&st)); StackPop(&st); } StackDestroy(&st); }
实现了栈的后入先出
2.队列
2.1队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾出队列:进行删除操作的一端称为队头
队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低
队列的接口函数
// 初始化队列 voidQueueInit(Queue*q); // 队尾入队列 voidQueuePush(Queue*q, QDataTypedata); // 队头出队列 voidQueuePop(Queue*q); // 获取队列头部元素 QDataTypeQueueFront(Queue*q); // 获取队列队尾元素 QDataTypeQueueBack(Queue*q); // 获取队列中有效元素个数 intQueueSize(Queue*q); // 检测队列是否为空,如果为空返回非零结果,如果非空返回0 intQueueEmpty(Queue*q); // 销毁队列 voidQueueDestroy(Queue*q);
队列的实现
typedef struct QListNode { struct QListNode* next;//保存结点的下一个结点的地址 int data;//该节点的数据 }QNode; typedef struct Queue { QNode* front; QNode* tail; }Queue;//定义一个队列结构体,指向队列的前结点和尾结点 // 初始化队列 void QueueInit(Queue* q) { assert(q); q->front = q->tail = NULL;//头节点尾结点置为NULL } // 队尾入队列 void QueuePush(Queue* q, int data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode));//新结点申请空间 assert(newnode);//防止申请失败 newnode->next = NULL;//新节点的下一个结点的地址为空,不保存 newnode->data = data;//新结点的数据 if (q->front == NULL)//没有一个结点 { q->front = q->tail = newnode;//就让指向头节点和指向尾结点的指针指向新结点 } else//有结点 { q->tail->next = newnode;//新结点尾插到后面 q->tail = newnode;//移动指向尾结点的指针到队列末尾结点,也就是新结点 } } // 检测队列是否为空,如果为空返回非零结果,如果非空返回0 int QueueEmpty(Queue* q) { return q->front == NULL;//如果没有结点,则q->front==NULL,表达式成立返回1,表明队列为空 } // 队头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q));//防止队列为空在出数据 if (q->front->next == NULL)//如果只有一个结点 { q->front = q->tail ==NULL;//那就把这个结点置空,指向头结点指针和指向尾结点的指针指向空 } else { QNode* next = q->front->next;//保存下一个结点的地址 free(q->front);//从头结点开始释放一个结点,也就是头删 q->front = next;//指向头结点的指针移动到下一个位置 } } // 获取队列头部元素 int QueueFront(Queue* q) { assert(q); assert(q->front);//防止头节点为空 return q->front->data;//头结点数据 } // 获取队列队尾元素 int QueueBack(Queue* q) { assert(q); assert(q->tail);//防止尾节点为空 return q->tail->data;//尾节点数据 } // 获取队列中有效元素个数 int QueueSize(Queue* q) { int size = 0;//记录元素个数变量 assert(q); QNode* cur = q->front;//遍历队列的指针先指向头 while (cur) { size++;//遍历记数 cur = cur->next; } return size;//返回有效数据个数 } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->front;//遍历队列的指针 while (cur) { QNode* next = cur->next;//保存下一个节点的地址 free(cur);//释放掉当前cur指针指向当前位置的空间 cur = next;//指向下一个位置 } q->front = q->tail = NULL;//防止野指针 }
队列功能测试
int main() { Queue st; QueueInit(&st); QueuePush(&st, 1); QueuePush(&st, 2); QueuePush(&st, 3); QueuePush(&st, 4); while (!QueueEmpty(&st)) { printf("%d ", QueueFront(&st)); QueuePop(&st); } QueueDestroy(&st); }
3.栈和队列面试题
思路:定义一个栈,将之前的功能都添在前面,使用栈解决这个问题,就是遍历这个字符串,如果是左括号的话,就入栈,然后s++,遇到右括号的话就取出栈顶元素,和这个右括号匹配,匹配上了就出栈栈顶元素,然后s++;没匹配上说明匹配不上,直接return false;当不是左括号的时候,出现右括号时,可能栈里还没有左括号,此时也匹配不上,直接return false;当遍历完s字符串后(s字符串一直是左括号),此时也属于匹配不上,就是判断栈中是否有元素,有元素都是左括号,然后就判空函数返回0==false,(当然定义栈需要初始化栈,和销毁栈)。
代码实现:
typedef struct Stack { char* a; int top; // 栈顶 int capacity; // 容量 }Stack; void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps, int data) { assert(ps); if (ps->capacity == ps->top) { int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2; char* newnode = (char*)realloc(ps->a,sizeof(char) * newcapcity); assert(newnode); ps->a = newnode; ps->capacity = newcapcity; } ps->a[ps->top] = data; ps->top++; } // 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } // 获取栈顶元素 char StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } bool isValid(char * s){ Stack st; StackInit(&st); while(*s) {if(*s=='['||*s=='('||*s=='{')//左括号入栈 {StackPush(&st,*s); s++;//移动到下一个字符位置 } else {if(StackEmpty(&st))//可能出现无左括号 return false; char top=StackTop(&st);//获取栈顶元素 if(*s==']'&&top=='['||*s=='}'&&top=='{'||*s==')'&&top=='(')//匹配上就出栈 { StackPop(&st); s++;//移动下一个字符位置 } else return false;//匹配不上直接return false } } int ret=StackEmpty(&st);// s字符串全是左括号,全部入栈,栈内不为空return 0匹配不上 StackDestroy(&st);//销毁栈 return ret; }
思路:队列是先进先出,而栈是后进先出,要用两个队列实现栈,一个队列是空的,然后要出栈栈顶元素,也就是队尾元素,可以先将队尾元素的前面的所有元素都入另一个空的队列,然后在pop这个队尾的元素,就能实现后进的先出,由于两个队列构成的栈,将一个队列中的元素入另一个队列,肯定不是出栈。
1.入栈函数的实现
如果哪个队列不为空就把元素入哪个队列中,保证一个队列为空,刚开始的时候,两个队列都为空,入哪个队列都行,在第二次入队列时候,就能保证元素都入不为空的队列了
2.出栈函数的实现
当保证一个队列为空的时候,要实现对应的后入的先出,就可以将非空队列的除队尾元素其他的都入另一个队列中,当非空队列只剩一个元素时,也就是后入的这个元素,将这个元素出队列,并且不入另一个队列,就相当于出栈,出队列前用一个变量存储这个队尾元素,也就是栈顶元素。
3.返回栈顶元素函数
使用定义好的QueueBack函数返回队尾元素,也就是栈顶元素,==注意肯定返回的是非空队列的队尾元素,也就是栈顶元素
4.判断栈为空的函数
使用定义好的QueueEmpty函数,return QueueEmpty(第一个队列地址)&&QueueEmpty(第二个队列地址),当两个队列都为空的时候,QueueEmpty函数就返回1 ,return 1;表示栈为空,如果有一个队列不为空的话,与的结果就是0, return 0,就是栈不为空。
5.释放栈的函数
使用QueueDestroy,销毁两个队列,然后free掉动态申请来的空间。
//队列功能的实现 typedef struct QListNode { struct QListNode* next; int data; }QNode; typedef struct Queue { QNode* front; QNode* tail; }Queue; void QueueInit(Queue* q) { assert(q); q->front = q->tail = NULL; } // 队尾入队列 void QueuePush(Queue* q, int x) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data =x; newnode->next = NULL; if (q->tail == NULL) { q->tail = q->front = newnode; } else { q->tail->next = newnode; q->tail = newnode; } } bool QueueEmpty(Queue* q) { assert(q); return q->front == NULL; } // 队头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q->front->next == NULL) { free(q->tail); q->tail = q->front = NULL; } else { QNode* next = q->front->next; free(q->front); q->front = next; } } // 获取队列头部元素 int QueueFront(Queue* q) { assert(q); assert(q->front); return q->front->data; } // 获取队列队尾元素 int QueueBack(Queue* q) { assert(q); assert(q->tail); return q->tail->data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); int size = 0; QNode* cur = q->front; while (cur) { size++; cur = cur->next; } return size; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->front; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->front = q->tail = NULL; } //队列功能实现到这里 typedef struct { Queue a; Queue b; } MyStack;//定义栈 MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack));//给栈申请动态空间 if(obj==NULL) {perror("malloc fail"); } QueueInit(&obj->a);//栈中两个队列的初始化 QueueInit(&obj->b); return obj;//返回申请栈空间的地址 } void myStackPush(MyStack* obj, int x)//入栈函数 { if(!QueueEmpty(&obj->a))//哪个队列不为空就入哪个队列 {QueuePush(&obj->a,x); } else {QueuePush(&obj->b,x); } } int myStackPop(MyStack* obj) { Queue* empty=&obj->a;//不知道哪个为空的队列,先随便保存一个 Queue* nonempty=&obj->b; if(!QueueEmpty(&obj->a))//如果a队列不是空的,就将队列b的地址保存在空的指针里面 {empty=&obj->b; nonempty=&obj->a; } while(QueueSize(nonempty)>1)//当非空的队列只剩下一个元素时,队尾元素,也就是栈顶元素 {QueuePush(empty,QueueFront(nonempty));//将非空队列的除队尾元素全部入到另一个空的队列中 QueuePop(nonempty);//队头元素出队列 } int ret=QueueFront(nonempty);//循环结束,只剩下队尾元素,将队尾元素保存在变量中 QueuePop(nonempty);//队尾元素出队列,并且不进另一个队列,相当于出栈 return ret;//返回栈顶元素 } int myStackTop(MyStack* obj) { if(QueueEmpty(&obj->a)) {return QueueBack(&obj->b); } else {return QueueBack(&obj->a); //哪个队列不为空,直接使用QueueBack返回不为空队列的队尾元素 } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->a)&&QueueEmpty(&obj->b); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->a); QueueDestroy(&obj->b); free(obj); }
思路:使用两个栈实现队列,栈为后入先出,队列为后入后出,当要出队头元素,也就是栈底元素时,可以将栈顶元素一个接一个放入另一个栈中popst,然后栈底元素到另一个栈就变成了栈顶元素,然后就可以实现队头元素,也就是栈底元素先出栈。
1.入队列函数的实现
使用 StackPush函数将数据入到栈pushst中
2.出队列函数实现
将pushst栈中的栈顶元素一个接一个全部入到栈popst中,将pushst栈中的元素全部pop掉,此时popst栈顶的元素就是队头元素,用一个变量保存他,然后将popst栈顶元素pop掉,return 栈顶元素。
3.返回队列开头的元素的函数
和出队列函数大致相同,这个不需要pop掉队头元素
4.判断队列为空函数
使用StackEmpty函数,return
StackEmpty(&obj->popst)&&StackEmpty(&obj->pushst);当两个栈都为空的时候返回1 ,表示队列为空,只要有一个不为空的话返回0,表示队列不为空。
5.释放队列函数
使用StackDestroy函数销毁两个栈,然后free掉动态开辟的内存。
typedef struct Stack { int* a; int top; // 栈顶 int capacity; // 容量 }Stack; void StackInit(Stack* ps)//初始化栈 { ps->a = NULL; ps->top = 0; ps->capacity = 0; } void StackPush(Stack* ps, int data)//入栈 { assert(ps); if (ps->capacity == ps->top) { int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2; int* tmp = (int*)realloc(ps->a, sizeof(int) * newcapcity); if (tmp == NULL) { perror("realloc fail"); } else { ps->a = tmp; ps->capacity = newcapcity; } } ps->a[ps->top] = data; ps->top++; } // 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps->top ==0; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } // 获取栈顶元素 int StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } typedef struct { Stack popst; Stack pushst; } MyQueue;//定义队列 MyQueue* myQueueCreate() { MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));//动态给队列申请空间 StackInit(&obj->popst); //初始化两个栈 StackInit(&obj->pushst); return obj;//返回队列的地址 } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushst,x);//入队列都入到pushst栈中 } int myQueuePop(MyQueue* obj) { if(StackEmpty(&obj->popst))//如果popst栈中为空的话 {while(StackSize(&obj->pushst))//将pushst栈中的元素全部入到popst栈中 {StackPush(&obj->popst,StackTop(&obj->pushst));//栈顶元素一个接一个放到popst的栈中 StackPop(&obj->pushst);//栈顶元素出栈 } } int ret=StackTop(&obj->popst);//变量接收popst栈顶元素的值,然后pop掉 StackPop(&obj->popst); return ret;//返回队列头元素,也就是popst栈顶元素 } int myQueuePeek(MyQueue* obj) //与上一个函数同理 { if(StackEmpty(&obj->popst)) {while(StackSize(&obj->pushst)) {StackPush(&obj->popst,StackTop(&obj->pushst)); StackPop(&obj->pushst); } } int ret=StackTop(&obj->popst); return ret; } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->popst)&&StackEmpty(&obj->pushst); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->popst); StackDestroy(&obj->pushst); free(obj); }
思路:用数组实现这个队列较简单,在开辟空间大小时,需要k个空间,我们给他开辟k+1个空间,如果尾的下一个是头的话,就说明队列满了,如果头和尾在一个地方,则队列为空,获取队首元素就是返回obj->a[obj->head]即可,获取队尾元素一般要找到obj->tail-1的位置,因为tail是后加,当存最后一个后,他的tail+1;插入元素,就让obj->a[obj->tail]=value;然后tail++;删除一个元素就让head++就行。
注意边界:
检查队列是否满的边界处理:
插入元素的边界处理:
删除元素边界处理:
获取尾部元素的边界处理
typedef struct { int*a;//指向队列空间的指针 int k;//队列空间大小 int head;//队列头下标 int tail;//队列尾下标 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//给描述队列的变量创建空间 obj->a=(int *)malloc(sizeof(int)*(k+1));//给队列创建空间 obj->k=k;//队列空间大小赋值 obj->head=obj->tail=0;//初始化队列队尾队头下标 return obj;//返回创建队列信息的地址 } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head==obj->tail;//空的话,头下标等于尾下标 } bool myCircularQueueIsFull(MyCircularQueue* obj) { int next=obj->tail+1;//记录尾下标的下一个下标 if(obj->tail==obj->k)//边界处理 next=0; return next==obj->head;//相等说明tail对应的下一个元素是head,表示已经满了 } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj))//满的话直接返回 return false; obj->a[obj->tail]=value;//插入元素 obj->tail++;//尾下标更新+1 if(obj->tail==obj->k+1)//边界处理 obj->tail=0; return true;//插入成功 } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//空的不能删除return false return false; obj->head++; 头下标更新+1; if(obj->head==obj->k+1)//边界处理 obj->head=0; return true; //删除成功return true } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//空的话返回-1; return -1; return obj->a[obj->head];//不空返回头下标对应的元素 } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//空的话返回-1; return -1; int prev=obj->tail-1;//记录尾下标的上一个下标 if(prev==-1)//边界处理 prev=obj->k; return obj->a[prev];//返回队列尾元素 } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
先free掉obj的话,obj->a指针中存放的队列的地址置为随机值,永远free不了obj->a,存在内存泄漏,所以先free obj->a,然后free obj.