• 栈和队列经典oj面试题

    作者：[南航科院小张
    南航科院小张的博客
    专栏：从c语言的入门到进阶
    学习知识不只是要懂，还要会用；想要找到好的工作，这里给大家介绍一件可以斩获诸多大厂offer的利器–牛客网
    点击免费注册和我一起开始刷题之路吧！！！

    文章目录

    一、有效的括号

    在这里插入图片描述

    题解：这里我们可以用栈的特性：先进后出；要是遇到左括号就入栈，要是右括号就和栈顶的元素进行比较，看是否匹配，要是匹配，就把栈顶出栈，要是不匹配，直接返回false；下面有几个要注意的点：

    1. 全部都是左括号；这个情况的话就是可以出循环，但是我们要在后面判断一下栈是否为空，要是空，那么就符合题意，返回true；否则返回false；
    2. 全部是右括号；这个问题当第一个右括号的时候就会返回法false，因为不匹配；
    3. 右括号比左括号多；这个情况的话也是最后面的判断栈是否空可以解决；
      下面代码要注意的是c语言没有栈，我自己实现的一个栈，然后就是在返回true或者false之前的时候一定要销毁栈！！！
    // 支持动态增长的栈
typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
void StackInit(Stack* ps) {
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, STDataType data) {
	assert(ps);
	if (ps->top == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity *2;
		STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (temp == NULL) {
			perror("realloc fail");
			exit(-1);
		}
		ps->a = temp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	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;
}

int StackEmpty(Stack* ps) {
	assert(ps);
	return ps->top ==0;
}

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);
    }
    else{
        if(StackEmpty(&st)){//为了防止栈为空，下面的StackPop接口还在用；
            StackDestroy(&st);
            return false;
        }
        char top=StackTop(&st);
        if(*s==')'&&top!='('
        ||*s=='}'&&top!='{'
        ||*s==']'&&top!='[')
        {
            StackDestroy(&st);
            return false;
        }
        else{
            StackPop(&st);
        }
    }
    ++s;
}
bool flag=StackEmpty(&st);
StackDestroy(&st);
return flag;
}

    • 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

    二、用队列实现栈

    在这里插入图片描述

    思路很简单，但是用代码实现起来还是有点挑战的哈哈；
    栈的特点：先进后出；队列特点：先进先出；
    用两个队列实现栈，利用队列的特点，把先进的数据导到另外一个队列里面，然后剩下一个数据，然后出这个数据（pop数据），这样就实现了栈的出数据特点，栈顶出数据；我们要控制那里的队列为空就往空队列导数据，非空队列留下一个来出数据，就这样一直在两个队列里面操作，然后入数据就往非空队列里入数据；我这里是直接写的队列哈，所以比较多代码；

    // 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	size_t sz;
	QNode* head;
	QNode* tail;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

void QueueInit(Queue* q) {
	assert(q);
	q->head = q->tail = NULL;
	q->sz = 0;
}

void QueuePush(Queue* q, QDataType data) {
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	else {
		newnode->data = data;
		newnode->next = NULL;
	}
	if (q->head == NULL) {
		q->head = q->tail = newnode;
		q->sz++;
	}
	else {
		q->tail->next = newnode;
		q->tail = newnode;
		q->sz++;

	}
}
void QueuePop(Queue* q) {
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head->next == NULL) {
		free(q->head);
		q->head = q->tail = NULL;
		q->sz--;
	}
	else {
	QNode* cur = q->head->next;
	free(q->head);
	q->head = cur;
	q->sz--;

	}
	
}

QDataType QueueFront(Queue* q) {
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}

QDataType QueueBack(Queue* q) {
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}
int QueueSize(Queue* q) {
	assert(q);
	return q->sz;
}
int QueueEmpty(Queue* q) {
	assert(q);
	return q->head == NULL && q->tail == NULL;
}
void QueueDestroy(Queue* q) {
	assert(q);
	QNode* cur = q->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL){
        perror("malloc fail");
        exit(-1);
    }
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1)){
        QueuePush(&obj->q1,x);
    }
    else{
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* EmptyQ=&obj->q1;
    Queue* noEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1)){
        EmptyQ=&obj->q2;
        noEmptyQ=&obj->q1;
    }
    while(QueueSize(noEmptyQ)>1){
        int top=QueueFront(noEmptyQ);
        QueuePop(noEmptyQ);
        QueuePush(EmptyQ,top);
    }
    int top=QueueFront(noEmptyQ);
    QueuePop(noEmptyQ);
    return top;
}

int myStackTop(MyStack* obj) {
    Queue* EmptyQ=&obj->q1;
    Queue* noEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1)){
        EmptyQ=&obj->q2;
        noEmptyQ=&obj->q1;
    }
    while(QueueSize(noEmptyQ)>1){
        int top=QueueFront(noEmptyQ);
        QueuePop(noEmptyQ);
        QueuePush(EmptyQ,top);
    }
    int top=QueueFront(noEmptyQ);
    QueuePop(noEmptyQ);
    QueuePush(EmptyQ,top);
    return top;
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(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
    • 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
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192

    三. 用栈实现队列

    在这里插入图片描述

    思路很简单，但是用代码实现起来还是有点挑战的哈哈；
    栈的特点：先进后出；队列特点：先进先出；
    用栈来模拟队列的特点，有了上面的题解，想必我们很容易想到方法了，这题比上一题简单哦，我们搞两个栈，一个栈专门用来入数据，一个栈专门用来出数据，因为入数据完后将全部数据到入专门的出数据的栈里面的时候，出数据的栈的数据是符合队列的出数据规则的了；所以可以对两个栈分开工作；
    要注意的是：出数据的栈要判断是否为空，要是空的话就导数据，然后再出；

    //Stack
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 

void StackInit(Stack* ps) {
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, STDataType data) {
	assert(ps);
	if (ps->top == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (temp == NULL) {
			perror("realloc fail");
			exit(-1);
		}
		ps->a = temp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	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;
}

int StackEmpty(Stack* ps) {
	assert(ps);
	return ps->top == 0 ? 1 : 0;
}

void StackDestroy(Stack* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}


typedef struct {
    Stack PopST;
    Stack PushST;
} MyQueue;


MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
if(obj==NULL){
    perror("malloc fail");
    exit(-1);
}
StackInit(&obj->PopST);
StackInit(&obj->PushST);
return obj;
}

void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->PushST,x);
}
//判断PopST队列是否为空，要是空，就导数据；
void PushSTTOPopST(MyQueue* obj){
if(StackEmpty(&obj->PopST)){
    while(!StackEmpty(&obj->PushST)){
    int top=StackTop(&obj->PushST);
    StackPop(&obj->PushST);
    StackPush(&obj->PopST,top);
}
}

}
int myQueuePop(MyQueue* obj) {
PushSTTOPopST(obj);
int top=StackTop(&obj->PopST);
StackPop(&obj->PopST);
return top;
}

int myQueuePeek(MyQueue* obj) {
PushSTTOPopST(obj);
int top=StackTop(&obj->PopST);
return top;
}

bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}

void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->PopST);
StackDestroy(&obj->PushST);
free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(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
    • 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
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141

    四. 设计循环队列

    在这里插入图片描述

    这道题其实难，可以用链表也可以用顺序表，不过我觉得用顺序表更简单容易实现一点；为了可以判断什么时候是满的什么时候是空的，我们有两个方法，一个是用size来计数，第二个是直接加一个节点；加了一个节点后当数据为空，就是head等于tail的时候，当(tail+1)%N等于head的时候为满数据，这个时候不能再插入数据了；我们一定要注意这是一个循环的，到边界的时候一定要有回去，这个时候我的实现是%N，返回尾元素则很巧,(tail-1+n)%n;我们要画图多观察才容易理解；要是不容易理解代码，可以画图然后看着代码来还原思路；

    typedef struct {
int* a;
int head;
int tail;
int N;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if(obj==NULL){
    perror("obj malloc fail");
    exit(-1);
}
obj->a=(int*)malloc(sizeof(int)*(k+1));//加一个空间，便于判断空和满；
if(obj->a==NULL){
    perror("a malloc fail");
    exit(-1);
}
obj->N=k+1;//作用很大，便于下标的循环恢复；
obj->head=obj->tail=0;
return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->tail==obj->head;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->N)==obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->tail]=value;
obj->tail++;
obj->tail%=obj->N;//防止在最大下标+1的情况，要循环进行恢复最小下标；
return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->head++;
obj->head%=obj->N;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->head];

}


int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->tail-1+obj->N)%(obj->N)];
}


void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->a=NULL;
free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(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
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    总结

    在这里插入图片描述

  • 相关阅读:
    掌握核心技巧就能创建完美的目录！如何在Word中自动创建目录
    Linux扩展篇之Shell编程二(变量)
    Go是如何处理goroutine阻塞的？
    终于找到一个很赞的相亲社交软件了，而且还是公众号java+vue
    树莓派 开机启动
    数据挖掘题目：根据规则模板和信息表找出R中的所有强关联规则，基于信息增益、利用判定树进行归纳分类，计算信息熵的代码
    【Linux信号专题】五、SIGCHLD信号详解
    什么是工业DTU？工业DTU特点及应用领域分析
    Landsat Collection 2 T1一级数据详细介绍（数据处理过程和几何精度）
    14：00面试，14：06就出来了，问的问题过于变态了。。。
  • 原文地址：https://blog.csdn.net/qq_68844357/article/details/126498031