【栈和队列】常见面试题

1.有效的括号

1.1 题目要求

判断所给字符串的括号是否有效。
有效的条件：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

1.2 利用栈解决

遍历给定字符串时，当我们遇到左括号时，把它入栈。目的是为了期望在后续的遍历中有一个相同类型的右括号与其匹配。
当我们遍历时遇到的是右括号，此时有3种情况：
1.栈为空，无法匹配返回false。
2.栈不为空，但不是与之匹配的左括号，返回false。
3.栈不为空，是与之匹配的左括号，继续遍历。
在2，3情况下，为了简化书写，我们可以先把栈顶元素出栈，用一个临时变量保存。
如果我们在遍历时都顺利通过，也不能代表这个字符串就是有效的。
比如这种情况：( ( ( ) )
遍历完后，栈中还会剩下(.
为此最后我们还需要判断栈是否为空，不为空返回false，为空返回true。
注意记得销毁栈

typedef struct stack
{char* a;int size;//写错了，代表top的意思int capacity;
}stack;void init(stack* ps)
{assert(ps);ps->a = (char*)malloc(sizeof(char)*4);ps->size = 0;ps->capacity = 4;
}bool empty(stack* ps)
{return ps->size == 0;
}void push(stack* ps,char x)
{assert(ps);if(ps->size == ps->capacity){char* tmp = (char*)realloc(ps->a,sizeof(char)*ps->capacity*2);if(tmp == NULL){perror("realloc");exit(-1);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->size] = x;ps->size+=1;
}
void pop(stack* ps)
{assert(ps);assert(ps->size>0);ps->size -= 1;
}char Top(stack* ps)
{assert(ps);assert(ps->size>0);return ps->a[ps->size-1];
}
void destory(stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
bool isValid(char* s) {stack st;init(&st);while(*s){if(*s == '('||*s == '['||*s == '{')push(&st,*s);else if(*s == ')'||*s == ']'||*s == '}'){if(empty(&st)){destory(&st);return false;}char top = Top(&st);pop(&st);if(*s == ')'&&top!='('||*s == ']'&&top!='['||*s == '}'&&top!='{'){destory(&st);return false;}}s+=1;}if(!empty(&st)){destory(&st);return false;}destory(&st);return true;
}

2. 用队列实现栈

2.1 题目要求

使用两个队列实现一个后入先出（LIFO）的栈

2.2 用队列实现栈

如何用两个队列来实现栈呢？我们知道队列是先进先出的。
先画两个队列出来。

此时插入了3个数据，为了让这两个队列实现后进先出的效果，我们得充分利用队列的特性。显然如果是栈，出数据是先出3的，但是队列的话是先出1。为了让队列先出3，我们就要把1和2先移动到另一个空队列中。

如此一来，就可以拿到3了。
那么用两个队列实现栈的主要逻辑就出来了。
首先是插入逻辑：有两种情况
1.两个队列都为NULL，随便插入一个队列
2.其中一个队列不为NULL，那么就把数据插入到不为NULL的队列。
然后就是删除逻辑：
在删除时，我们需要把有数据的一方队列的数据转移到没有数据的队列中，直到只剩下一个元素，这就是栈顶元素，用一个临时遍历存储完数据后就可以删除这个栈顶元素了。
再然后的返回栈顶元素：
因为不用删除的缘故，队列又提供返回队尾元素的功能，所以直接返回有数据的那个队尾元素即可。
最后都是一些简单的接口，相信大家没问题的。

typedef struct node
{int data;struct node* next;
}node;typedef struct queue
{node* head;node* tail;
}queue;void init(queue* q)
{assert(q);q->head = q->tail = NULL;
}void push(queue* q,int x)
{assert(q);node* newnode = (node*)malloc(sizeof(node));if(newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;if(q->head == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = newnode;}
}void pop(queue* q)
{assert(q);assert(q->head);if(q->head == q->tail){free(q->head);q->head = q->tail = NULL;}else{node* next = q->head->next;free(q->head);q->head = next;}
}int size(queue* q)
{assert(q);node* cur = q->head;int count = 0;while(cur){count+=1;cur = cur->next;}return count;
}bool empty(queue* q)
{assert(q);return q->head == NULL;
}int top(queue* q)
{assert(q);assert(q->head);return q->head->data;
}int back(queue* q)
{assert(q);assert(q->head);return q->tail->data;
}
void destory(queue* q)
{assert(q);node* cur = q->head;while(cur){node* next = cur->next;free(cur);cur = next;}q->head = q->tail = NULL;
}typedef struct {queue q1;queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* s = (MyStack*)malloc(sizeof(MyStack));init(&s->q1);init(&s->q2);return s;
}void myStackPush(MyStack* s, int x) {if(!empty(&s->q1)){push(&s->q1,x);}else{push(&s->q2,x);}
}int myStackPop(MyStack* s) {queue* em = &s->q1;queue* noem = &s->q2;if(!empty(em)){em = &s->q2;noem = &s->q1;}while(size(noem)>1){push(em,top(noem));pop(noem);}int t = top(noem);pop(noem);return t;
}int myStackTop(MyStack* s) {queue* em = &s->q1;queue* noem = &s->q2;if(!empty(em)){em = &s->q2;noem = &s->q1;}return back(noem);
}bool myStackEmpty(MyStack* s) {return empty(&s->q1)&&empty(&s->q2);
}void myStackFree(MyStack* s) {destory(&s->q1);destory(&s->q2);free(s);
}

3.用栈实现队列

3.1 题目要求

请使用两个栈实现先入先出队列

3.2 用栈实现队列

要用两个后进先出的栈实现先进先出的队列。先看图

为了实现队列，我们要把栈设计为一个进进数据栈，一个出数据栈。
当我们需要删除数据时，因为队列先进先出的特性，要出的数据为1，可是栈顶元素是3，所以我们需要把进数据栈的数据全部移动到出数据栈中，移动完后如图：

这样的话，程序的主体逻辑都出来了。
开始我们入数据的时候，全部都存储到pusht栈中。
然后当我们想要删除数据/读取队首元素时：会有两种情况
1.popt栈为空，那么我们就把pusht栈中的元素全部转移到popt栈。
2.popt栈不为空，直接取popt的栈顶元素就可以了。
为了简化代码，我们可以复用函数。先实现读取队首元素的功能（peek）再在删除队列元素时复用读取对手元素的功能。详见代码
最后都是写简单功能，大家看代码。

typedef struct stack
{int* a;int size;//写错了，代表top的意思int capacity;
}stack;void init(stack* ps)
{assert(ps);ps->a = (int*)malloc(sizeof(int)*4);ps->size = 0;ps->capacity = 4;
}bool empty(stack* ps)
{return ps->size == 0;
}void push(stack* ps,int x)
{assert(ps);if(ps->size == ps->capacity){int* tmp = (int*)realloc(ps->a,sizeof(int)*ps->capacity*2);if(tmp == NULL){perror("realloc");exit(-1);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->size] = x;ps->size+=1;
}
void pop(stack* ps)
{assert(ps);assert(ps->size>0);ps->size -= 1;
}
int Top(stack* ps)
{assert(ps);assert(ps->size>0);return ps->a[ps->size-1];
}
void destory(stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
int size(stack* ps)
{assert(ps);return ps->size;
}
typedef struct {stack pusht;stack popt;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));init(&q->pusht);init(&q->popt);return q;
}void myQueuePush(MyQueue* q, int x) {push(&q->pusht,x);
}int myQueuePeek(MyQueue* q) {if(empty(&q->popt)){while(!empty(&q->pusht)){push(&q->popt,Top(&q->pusht));pop(&q->pusht);}}return Top(&q->popt);
}int myQueuePop(MyQueue* q) {int top = myQueuePeek(q);pop(&q->popt);return top;
}bool myQueueEmpty(MyQueue* q) {return empty(&q->pusht)&&empty(&q->popt);
}
void myQueueFree(MyQueue* q) {destory(&q->pusht);destory(&q->popt);free(q);q = NULL;
}

4.设计循环队列

4.1 题目要求

设计一个大小为k的循环队列

4.2 设计循环队列

简单科普循环队列
这是一个循环队列

下面展示循环队列为空和为满时情形：
tail位置是不存储数据的，代表意思是队尾元素的下一个。

科普完成后，下面就是正式的题目讲解：
在初始化时，我们需要开k+1个空间，因为数组中的tial位是不存储数据的。
先写判断循环队列是否为空和为满的功能，写了两个函数书写其他函数时就比较轻松了。
正如上面所说，tail = head为空
为满的话，考虑到循环因素，我们需要利用取模操作。
为满就一种情况，head在tail前面，但是因为数组不像上面画的那样是一个环，所以为满就有了两种情况：
1.tial在head前面，多种情况
2.tail在head后面，在后面就一种情况，tail为k，head为0
(tail+1)%(k+1) = head就是判断条件。
后面的插入删除都没什么难点了，唯一要注意的就是当head和tial到达k时要注意下一步的操作。
还有返回队尾数据的，tail是指向队尾数据的下一个元素的！

typedef struct {int* a;int head;int tail;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q->a = (int*)malloc(sizeof(int)*(k+1));q->head = q->tail = 0;q->k = k;return q;
}
//函数声明
bool myCircularQueueIsEmpty(MyCircularQueue* q);
bool myCircularQueueIsFull(MyCircularQueue* q);bool myCircularQueueEnQueue(MyCircularQueue* q, int value) {if(myCircularQueueIsFull(q))return false;q->a[q->tail] = value;if(q->tail == q->k)q->tail = 0;elseq->tail+=1;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* q) {if(myCircularQueueIsEmpty(q))return false;if(q->head == q->k)q->head = 0;elseq->head+=1;return true;
}int myCircularQueueFront(MyCircularQueue* q) {if(myCircularQueueIsEmpty(q))return -1;return q->a[q->head];
}int myCircularQueueRear(MyCircularQueue* q) {if(myCircularQueueIsEmpty(q))return -1;if(q->tail == 0)return q->a[q->k];elsereturn q->a[q->tail-1];
}bool myCircularQueueIsEmpty(MyCircularQueue* q) {if(q->head == q->tail)return true;return false;
}bool myCircularQueueIsFull(MyCircularQueue* q) {if((q->tail+1)%(q->k+1) == q->head)return true;return false;}void myCircularQueueFree(MyCircularQueue* q) {free(q);q = NULL;
}

完