栈和队列面试题
- 20. 有效的括号
- 题目
- 解法一:建立栈解决
- 解法二:数组模拟栈解决
- 225. 用队列实现栈
- 题目
- 解法:两个队列实现栈
- 232. 用栈实现队列
- 题目
- 解法:两个栈实现队列
- 622. 设计循环队列
- 题目
- 解法一:数组
- 解法二:链表
- 结语
20. 有效的括号
题目
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
题目链接:有效的括号
解法一:建立栈解决
代码如下:
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
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;
}
STDataType 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
在C语言中,因为没有现成的栈可以调用,所以这里首先我们建立一个栈结构及各种操作函数建立,以便于这里的函数实现进行调用,这里我们首先建立一个栈st,初始化栈st,第一层while循环判定数组中有没有元素,进入循环后如果首元素为左括号入栈,并将指针位置后移一位,再看else语句,如果栈为空,说明上一段条件语句没执行,直接返回false,不执行这句,说明栈中有元素,则先将栈顶值记录,再删除栈顶元素,再进行括号匹配,如果s此时指向的是右括号并且top不等于左括号,说明不匹配,等于就将指针位置后移再进行匹配,最后遍历完,如果栈为空,则都匹配,否则就不匹配。这种写法代码虽然长,但是相对来说很好理解。
如下图:
解法二:数组模拟栈解决
代码如下:
char pairs(char a)
{
if(a==')') return '(';
if(a=='}') return '{';
if(a==']') return '[';
return 0;
}
bool isValid(char * s){
int n=strlen(s);
if(n%2==1)
return false;
int stk[n],i=0,top=0;
for(i=0;i<n;i++)
{
char ch=pairs(s[i]);
if(ch)
{
if(top==0||stk[top-1]!=ch)
return false;
top--;
}
else
stk[top++]=s[i];
}
return top==0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
这里我们创建一个pairs函数进行返回匹配,如果a是右括号则返回左括号,否则返回0,再看我们的主调函数,我们首先记录字符串长度,如果长度为奇数,直接返回false,如果没进入条件语句,则执行下面语句,首先我们建立字符串长度的数组stk,然后就是一个for循环,循环次数为字符串长度(防止最坏情况,全为左括号),首先记录第一个字符调用pairs函数进行匹配,如果是左括号,返回0;进入else语句,stk首元素记录第一个字符,top+1,再进行第二次循环,如果为右括号,则ch记录为左括号,进行匹配,如果相同,top-1,不相同则直接返回false,循环结束,如果top等于0,则返回ture,否则为false,其实这种写法原理和上面是一样的,只不过编写形式不一样。
如下图:
225. 用队列实现栈
题目
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
注意
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
题目链接:用队列实现栈
解法:两个队列实现栈
代码如下:
typedef struct {
int queue1[100];
int queue2[100];
int front1;
int front2;
int rear1;
int rear2;
} MyStack;
MyStack* myStackCreate() {
MyStack* stack=malloc(sizeof(MyStack));
stack->front1=0;
stack->front2=0;
stack->rear1=0;
stack->rear2=0;
return stack;
}
void myStackPush(MyStack* obj, int x) {
obj->queue1[(obj->rear1)++]=x;
}
int myStackPop(MyStack* obj) {
int front1=obj->front1;
int front2=obj->front2;
int rear1=obj->rear1;
int rear2=obj->rear2;
while(rear1-front1>1)
{
obj->queue2[rear2++]=obj->queue1[front1++];
}
int top=obj->queue1[front1++];
while(front2!=rear2)
{
obj->queue1[rear1++]=obj->queue2[front2++];
}
obj->front1=front1;
obj->front2=front2;
obj->rear1=rear1;
obj->rear2=rear2;
return top;
}
int myStackTop(MyStack* obj) {
return obj->queue1[obj->rear1-1];
}
bool myStackEmpty(MyStack* obj) {
return obj->queue1[obj->front1]==obj->queue2[obj->front2];
}
void myStackFree(MyStack* obj) {
obj->front1=obj->front2=obj->rear1=obj->rear2=0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
具体思路如下图:
入栈
入栈
出栈
232. 用栈实现队列
题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
说明
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
解法:两个栈实现队列
代码如下:
typedef struct {
int* stk;
int stksize;
int stkcapacity;
}Stack;
Stack* createStack(int capacity)
{
Stack* ret=malloc(sizeof(Stack));
ret->stk=malloc(sizeof(int)*capacity);
ret->stksize=0;
ret->stkcapacity=capacity;
return ret;
}
void stackpush(Stack* obj,int x)
{
obj->stk[obj->stksize++]=x;
}
void stackpop(Stack* obj)
{
obj->stksize--;
}
int stacktop(Stack* obj)
{
return obj->stk[obj->stksize-1];
}
bool stackempty(Stack* obj)
{
return obj->stksize==0;
}
void stackfree(Stack* obj)
{
free(obj->stk);
}
typedef struct {
Stack* inqueue;
Stack* outqueue;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* ret=malloc(sizeof(MyQueue));
ret->inqueue=createStack(100);
ret->outqueue=createStack(100);
return ret;
}
void inout(MyQueue* obj)
{
while(!stackempty(obj->inqueue))
{
stackpush(obj->outqueue,stacktop(obj->inqueue));
stackpop(obj->inqueue);
}
}
void myQueuePush(MyQueue* obj, int x) {
//stackpush(obj->inqueue,x);
obj->inqueue->stk[obj->inqueue->stksize++]=x;
}
int myQueuePop(MyQueue* obj) {
if(stackempty(obj->outqueue))
{
inout(obj);
}
int x=stacktop(obj->outqueue);
stackpop(obj->outqueue);
return x;
}
int myQueuePeek(MyQueue* obj) {
if(stackempty(obj->outqueue))
{
inout(obj);
}
return stacktop(obj->outqueue);
}
bool myQueueEmpty(MyQueue* obj) {
return (stackempty(obj->inqueue)&&stackempty(obj->outqueue));
}
void myQueueFree(MyQueue* obj) {
stackfree(obj->inqueue);
stackfree(obj->outqueue);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
具体思路如下图:
622. 设计循环队列
题目
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
题目链接:设计循环队列
解法一:数组
代码如下:
typedef struct {
int front;//队首
int rear;//队尾
int capacity;//容量
int* elem;//元素
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* ret=malloc(sizeof(MyCircularQueue));
ret->capacity=k+1;
ret->elem=malloc(sizeof(int)*ret->capacity);
ret->front=ret->rear=0;
return ret;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if((obj->rear+1)%obj->capacity==obj->front)
return false;
obj->elem[obj->rear]=value;
obj->rear=(obj->rear+1)%obj->capacity;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(obj->front==obj->rear)
return false;
obj->front=(obj->front+1)%obj->capacity;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(obj->front==obj->rear)
return -1;
return obj->elem[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(obj->front==obj->rear)
return -1;
return obj->elem[(obj->rear-1+obj->capacity)%obj->capacity];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear+1)%obj->capacity==obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->elem);
free(obj);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
首先是队列结构体的建立,然后是队列初始化创建,和普通队列不同的是这里的capacity是给定值k+1,这里的用处在后面的函数会体现。
入队列:首先判定队尾下标+1模上容量等于队首下标,说明队列已经满了,返回false。入队为队尾值为下标,更新队尾值为+1模上容量,而不是直接++。
出队列:题目要求是直接删除,返回逻辑值,所以这里直接删除队首值对应下标元素,同样是队首值+1模上容量,实际此时并没删除,但是等到队尾值对应下标访问该位置入队列时会直接覆盖,而且此时这个位置也不是合法位置,所以不需要直接将其删除。
返回队首值:题目要求队列为空返回-1,只有队首等于队尾时,队列才为空,否则直接返回队首值对应下标元素即为队首。
返回队尾值:为空和上面一样,否则返回队尾值-1加上容量值再%上容量,很多人看不懂这句,举个例子,假设这时队列是满的,那么如果队尾值为0,减去1的话为负值,再去取余数就出现了越界,而且返回值是错的。
返回队列是否为空:返回队首队尾是否相等即可
返回队列是否已满:队尾值+1模上容量如果等于front,那就满了
讲到这你会发现容量的初始值设定非常的奇妙,它是循环队列思路的关键。
解法二:链表
代码如下:
typedef struct {
struct ListNode *head;//队首指针
struct ListNode *tail;//队尾指针
int capacity;//容量
int size;//长度
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
obj->capacity = k;
obj->size = 0;
obj->head = obj->tail = NULL;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (obj->size >= obj->capacity) {
return false;
}
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->val = value;
node->next = NULL;
if (!obj->head) {
obj->head = obj->tail = node;
} else {
obj->tail->next = node;
obj->tail = node;
}
obj->size++;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (obj->size == 0) {
return false;
}
struct ListNode *node = obj->head;
obj->head = obj->head->next;
obj->size--;
free(node);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (obj->size == 0) {
return -1;
}
return obj->head->val;
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (obj->size == 0) {
return -1;
}
return obj->tail->val;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->size == 0;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->size == obj->capacity;
}
void myCircularQueueFree(MyCircularQueue* obj) {
for (struct ListNode *curr = obj->head; curr;) {
struct ListNode *node = curr;
curr = curr->next;
free(node);
}
free(obj);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
这种写法是使用双向循环链表的写法,个人觉得这种写法比上面的要更好理解
首先是队列结构体的建立和初始化队列
入队列:如果长度等于容量队列已满,返回false,这里插入分两种情况,第一种是第一次插入时,首位指针都指向该元素结点,之后每次插入为第二种情况,一直挪动尾指针即可,插入成功,size+1,返回true
出队列:如果size为0,返回false,头指针指向下一结点,size-1,返回true
返回队首值:直接返回队首指针指向元素即为队首。
返回队尾值:直接返回队尾指针指向元素即为队尾。
返回队列是否为空:返回队首size是否为0。
返回队列是否已满:size等于capacity就满了。
结语
这里的解法代码部分来自力扣官方和作者自己的解法,作者只是进行了详细的剖析和部分改动方便大家理解和提升自己,学会多角度观察问题,解决问题。
有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!
制作不易,如有不正之处敬请指出
感谢大家的来访,UU们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!