栈和队列高频面试题

栈和队列高频面试题

题目一：括号匹配问题

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足：  1.左括号必须用相同类型的右括号闭合。  2.左括号必须以正确的顺序闭合。

要求：  时间复杂度：O(n)

思路：  该题是栈的典型应用，满足后进先出的规则（后入栈的前括号将优先与先出现的后括号相匹配）。  遍历字符串，遇到前括号直接入栈。遇到后括号，判断该后括号与栈顶的前括号是否匹配（若此时栈为空，则字符串无效），若不匹配则字符串无效；若匹配则删除栈顶元素，继续遍历字符串，直到字符串遍历完毕。当字符串遍历完后，检测栈是否为空，若为空，则字符串有效，若不为空，说明有前括号未匹配，字符串无效。

代码：

typedef char STDataType;//栈中存储的元素类型typedef struct Stack{ STDataType* a;//栈 int top;//栈顶 int capacity;//容量，方便增容}Stack;//初始化栈void StackInit(Stack* pst){ assert(pst); pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素 pst->top = 0;//初始时栈中无元素，栈顶为0 pst->capacity = 4;//容量为4}//销毁栈void StackDestroy(Stack* pst){ assert(pst); free(pst->a);//释放栈 pst->a = NULL;//及时置空 pst->top = 0;//栈顶置0 pst->capacity = 0;//容量置0}//入栈void StackPush(Stack* pst, STDataType x){ assert(pst); if (pst->top == pst->capacity)//栈已满，需扩容 { STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pst->a = tmp; pst->capacity *= 2;//栈容量扩大为原来的两倍 } pst->a[pst->top] = x;//栈顶位置存放元素x pst->top++;//栈顶上移}//检测栈是否为空bool StackEmpty(Stack* pst){ assert(pst); return pst->top == 0;}//出栈void StackPop(Stack* pst){ assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 pst->top--;//栈顶下移}//获取栈顶元素STDataType StackTop(Stack* pst){ assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 return pst->a[pst->top - 1];//返回栈顶元素}//获取栈中有效元素个数int StackSize(Stack* pst){ assert(pst); return pst->top;//top的值便是栈中有效元素的个数}/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/bool isValid(char * s){ Stack st;//创建一个栈 StackInit(&st);//初始化栈 char* cur = s;//cur用于遍历字符串 while(*cur) { if(*cur == '('||*cur == '{'||*cur == '[')//前括号统一入栈 { StackPush(&st, *cur); cur++; } else { if(StackEmpty(&st))//若遇到后括号，且栈为空，则字符串无效 { StackDestroy(&st); return false; } char top = StackTop(&st);//获取栈顶元素 if((top == '('&&*cur != ')') ||(top == '{'&&*cur != '}') ||(top == '['&&*cur != ']'))//后括号与栈顶的前括号不匹配 { StackDestroy(&st); return false; } else//匹配 { StackPop(&st); cur++; } } } bool ret = StackEmpty(&st);//检测栈是否为空 StackDestroy(&st); return ret;//栈为空返回true，栈不为空返回false}

题目二：用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：  void push(int x) 将元素 x 压入栈顶。  int pop() 移除并返回栈顶元素。  int top() 返回栈顶元素。  boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：

使用两个队列，始终保持一个队列为空。当我们需要进行压栈操作时，将数据压入不为空的队列中（若两个都为空，则随便压入一个队列）。当需要进行出栈操作时，将不为空的队列中的数据导入空队列，仅留下一个数据，这时将这个数据返回并且删除即可。判断栈是否为空，即判断两个队列是否同时为空。

代码：

typedef int QDataType;//队列中存储的元素类型typedef struct QListNode{ struct QListNode* next;//指针域 QDataType data;//数据域}QListNode;typedef struct Queue{ QListNode* head;//队头 QListNode* tail;//队尾}Queue;//初始化队列void QueueInit(Queue* pq){ assert(pq); //起始时队列为空 pq->head = NULL; pq->tail = NULL;}//销毁队列void QueueDestroy(Queue* pq){ assert(pq); QListNode* cur = pq->head;//接收队头 //遍历链表，逐个释放结点 while (cur) { QListNode* next = cur->next; free(cur); cur = next; } pq->head = NULL;//队头置空 pq->tail = NULL;//队尾置空}//队尾入队列void QueuePush(Queue* pq, QDataType x){ assert(pq); QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));//申请新结点 if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x;//新结点赋值 newnode->next = NULL;//新结点指针域置空 if (pq->head == NULL)//队列中原本无结点 { pq->head = pq->tail = newnode;//队头、队尾直接指向新结点 } else//队列中原本有结点 { pq->tail->next = newnode;//最后一个结点指向新结点 pq->tail = newnode;//改变队尾指针指向 }}//检测队列是否为空bool QueueEmpty(Queue* pq){ assert(pq); return pq->head == NULL;}//队头出队列void QueuePop(Queue* pq){ assert(pq); assert(!QueueEmpty(pq));//检测队列是否为空 if (pq->head->next == NULL)//队列中只有一个结点 { free(pq->head); pq->head = NULL; pq->tail = NULL; } else//队列中有多个结点 { QListNode* next = pq->head->next; free(pq->head); pq->head = next;//改变队头指针指向 }}//获取队列头部元素QDataType QueueFront(Queue* pq){ assert(pq); assert(!QueueEmpty(pq));//检测队列是否为空 return pq->head->data;//返回队头指针指向的数据}//获取队列尾部元素QDataType QueueBack(Queue* pq){ assert(pq); assert(!QueueEmpty(pq));//检测队列是否为空 return pq->tail->data;//返回队尾指针指向的数据}//获取队列中有效元素个数int QueueSize(Queue* pq){ assert(pq); QListNode* cur = pq->head;//接收队头 int count = 0;//记录结点个数 while (cur)//遍历队列 { count++; cur = cur->next; } return count;//返回队列中的结点数}/*---以上代码是队列的基本功能实现，以下代码是题解主体部分---*/typedef struct { Queue q1;//第一个队列 Queue q2;//第二个队列} MyStack;/** Initialize your data structure here. */MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack));//申请一个MyStack类型的栈 QueueInit(&pst->q1);//初始化第一个队列 QueueInit(&pst->q2);//初始化第二个队列 return pst;}/** Push element x onto stack. */void myStackPush(MyStack* obj, int x) { //数据压入非空的那个队列 if (!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); }}/** Removes the element on top of the stack and returns that element. */int myStackPop(MyStack* obj) { Queue* pEmpty = &obj->q1;//记录空队列 Queue* pNoEmpty = &obj->q2;//记录非空队列 if (!QueueEmpty(&obj->q1)) { pEmpty = &obj->q2; pNoEmpty = &obj->q1; } while (QueueSize(pNoEmpty) > 1) { QueuePush(pEmpty, QueueFront(pNoEmpty)); QueuePop(pNoEmpty); }//将非空队列中的数据放入空队列中，只留下一个数据 int front = QueueFront(pNoEmpty);//获取目标数据 QueuePop(pNoEmpty);//删除目标数据 return front;}/** Get the top element. */int myStackTop(MyStack* obj) { //获取非空队列的队尾数据 if (!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); }}/** Returns whether the stack is empty. */bool myStackEmpty(MyStack* obj) { //两个队列均为空，则MyStack为空 return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1);//释放第一个队列 QueueDestroy(&obj->q2);//释放第二个队列 free(obj);//释放MyStack}

题目三：用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

实现 MyQueue 类：  void push(int x) 将元素 x 推到队列的末尾。  int pop() 从队列的开头移除并返回元素。  int peek() 返回队列开头的元素。  boolean empty() 如果队列为空，返回 true ；否则，返回 false。

思路：

使用两个栈，第一个栈只用于数据的输入，第二个栈只用于数据的输出。当需要输出数据，但第二个栈为空时，先将第一个栈中的数据一个一个导入到第二个栈，然后第二个栈再输出数据即可。

这样就能够模拟实现一个队列了，即先输入的数据先输出。

代码：

typedef int STDataType;//栈中存储的元素类型typedef struct Stack{ STDataType* a;//栈 int top;//栈顶 int capacity;//容量，方便增容}Stack;//初始化栈void StackInit(Stack* pst){ assert(pst); pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素 pst->top = 0;//初始时栈中无元素，栈顶为0 pst->capacity = 4;//容量为4}//销毁栈void StackDestroy(Stack* pst){ assert(pst); free(pst->a);//释放栈 pst->a = NULL;//及时置空 pst->top = 0;//栈顶置0 pst->capacity = 0;//容量置0}//入栈void StackPush(Stack* pst, STDataType x){ assert(pst); if (pst->top == pst->capacity)//栈已满，需扩容 { STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pst->a = tmp; pst->capacity *= 2;//栈容量扩大为原来的两倍 } pst->a[pst->top] = x;//栈顶位置存放元素x pst->top++;//栈顶上移}//检测栈是否为空bool StackEmpty(Stack* pst){ assert(pst); return pst->top == 0;}//出栈void StackPop(Stack* pst){ assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 pst->top--;//栈顶下移}//获取栈顶元素STDataType StackTop(Stack* pst){ assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 return pst->a[pst->top - 1];//返回栈顶元素}//获取栈中有效元素个数int StackSize(Stack* pst){ assert(pst); return pst->top;//top的值便是栈中有效元素的个数}/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/typedef struct { Stack pushST;//插入数据时用的栈 Stack popST;//删除数据时用的栈} MyQueue;/** Initialize your data structure here. */MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));//申请一个队列类型 StackInit(&obj->pushST);//初始化pushST StackInit(&obj->popST);//初始化popST return obj;}/** Push element x to the back of queue. */void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST, x);//插入数据，向pushST插入}/** Get the front element. */int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popST))//popST为空时，需先将pushST中数据导入popST { while(!StackEmpty(&obj->pushST))//将pushST数据全部导入popST { StackPush(&obj->popST, StackTop(&obj->pushST)); StackPop(&obj->pushST); } } return StackTop(&obj->popST);//返回popST栈顶的元素}/** Removes the element from in front of queue and returns that element. */int myQueuePop(MyQueue* obj) { int top = myQueuePeek(obj); StackPop(&obj->popST);//删除数据，删除popST中栈顶的元素 return top;}/** Returns whether the queue is empty. */bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);//两个栈均为空，则“队列”为空}void myQueueFree(MyQueue* obj) { //先释放两个栈，再释放队列的结构体类型 StackDestroy(&obj->pushST); StackDestroy(&obj->popST); free(obj);}

题目四：设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。  循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

实现 MyCircularQueue 类：  MyCircularQueue(k): 构造器，设置队列长度为 k 。  Front: 从队首获取元素。如果队列为空，返回 -1 。  Rear: 获取队尾元素。如果队列为空，返回 -1 。  enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。  deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。  isEmpty(): 检查循环队列是否为空。  isFull(): 检查循环队列是否已满。

思路：

在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。

注意：环形队列的队尾不能像常规队列中队尾一样指向最后一个数据，如果这样的话，我们将不能区别环形队列的状态是空还是满，因为此时队头和队尾都指向同一个位置。这就意味着，我们必须留出一个空间，这个空间不能存放数据，这样我们才能很好的区别环形队列的状态是空还是满。

我们如果用一个数组来实现这个环形队列的话，上面这三种状态就对应于以下三种状态：

可以看出，此时这个数组和环形完全扯不上关系，这其实很简单，我们只需注意判断两个地方：

1.当指针指向整个数组的后方的时候，让该指针重新指向数组的第一个元素。

2.当指针指向整个数组的前方的时候，让该指针直接指向数组最后一个有效元素的后面。这样就使得该数组在逻辑上是“环形”的了。

代码：

typedef struct { int* a;//数组模拟环形队列 int k;//队列可存储的有效数据总数 int front;//队头 int tail;//队尾的后一个位置} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个环形队列 obj->a = (int*)malloc(sizeof(int)*(k+1));//开辟队列空间 //初始时，队头和队尾均为0 obj->front = 0; obj->tail = 0; obj->k = k;//设置队列可存储的有效数据个数 return obj;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail;//当front和tail指向同一位置时，队列为空}bool myCircularQueueIsFull(MyCircularQueue* obj) { int tailNext = obj->tail+1; if(tailNext == obj->k+1)//当指针指到队列末尾时，指针返回队列开头，使队列循环 { tailNext = 0; } return tailNext == obj->front;//当tail+1指向的位置与front相同时，队列满}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj))//队列已满，不能再插入数据 { return false; } else//插入数据 { obj->a[obj->tail] = value; obj->tail++; if(obj->tail == obj->k+1)//使队列循环 obj->tail = 0; return true; }}bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//当队列为空时，无法再删除数据 { return false; } else//删除数据 { obj->front++; if(obj->front == obj->k+1)//使队列循环 obj->front = 0; return true; }}int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//当队列为空时，无数据可返回 { return -1; } else { return obj->a[obj->front];//返回队头指向的数据 }}int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj))//当队列为空时，无数据返回 { return -1; } else//返回tail-1指向位置的数据 { int tailPrev = obj->tail-1; if(tailPrev == -1)//使队列循环 tailPrev = obj->k; return obj->a[tailPrev]; }}void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a);//先释放动态开辟的数组 free(obj);//再释放动态开辟的结构体}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。