devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

（C语言）数据结构之栈和队列面试题_typedef struct stack { datatype* data; // 顺序栈 int

作者：Cpp五条 | 2024-04-09 06:57:22

赞

踩

typedef struct stack { datatype* data; // 顺序栈 int top; // 栈顶指针 } stac

目录

题目1.括号匹配问题

题目链接

思路：
判断括号的有效性可以使用栈这一数据结构来解决。
我们遍历给定的字符串s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。
当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串s 无效，返回False。在上述的基础之上，在遍历结束后，如果栈中没有左括号，说明我们将字符串 s中的所有左括号闭合，返回True，否则返回 False。

实现代码：

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);


void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void StackDestory(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->capacity==ps->top)
	{
		int newcapcaity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, newcapcaity * sizeof(STDataType));
		if (ps->a==NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapcaity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
	
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool isValid(char * s){
    ST MY_st;
    StackInit(&MY_st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            StackPush(&MY_st, *s);
        }
        else
        {
            if(StackEmpty(&MY_st))
            {
                StackDestory(&MY_st);
                return false;
            }

            char tmp = StackTop(&MY_st);

            if((tmp=='('&&*s!=')')||(tmp=='['&&*s!=']')||(tmp=='{'&&*s!='}'))
            {
                StackDestory(&MY_st);
                return false;
            }
            StackPop(&MY_st);
        }
        s++;
    }

    if(StackEmpty(&MY_st))
    {
        StackDestory(&MY_st);
        return true;
    }
    else
    {
        StackDestory(&MY_st);
        return false;
    }

}

  • 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

题目2.用队列实现栈

题目链接

思路：
为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，
入栈操作时，首先将元素入队到 q1，然后出栈时先将q1的n-1个元素依次出队并入队到 q2
，此时q1仅剩的那一个元素即为栈顶元素，出队即可。此时q1没有元素了
下一次想出栈的时候就再倒一次，也就是把q2的前n-1个元素出队并入队到q1，然后q2把剩下的那个元素出队即可，此时q2为空下一次再入栈的时候，也就不用管q1还是q2，就直接谁有元素就往谁的里面入队元素即可。
总结：出栈倒一下，入栈入非空。

在这里插入图片描述

实现代码：

typedef int QDataType;

typedef struct QueueNode
{
	struct Queue* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;


void QueueInit(Queue* pq);//队列的初始化
void QueueDestroy(Queue* pq);//队列的销毁
void QueuePush(Queue* pq, QDataType x);//入队
void QueuePop(Queue* pq);//出队
QDataType QueueFront(Queue* pq);//队头元素
QDataType QueueBack(Queue* pq);//队尾元素
bool QueueEmpty(Queue* pq);//队列判空
int QueueSize(Queue* pq);//判断有效元素个数


void QueueInit(Queue* pq)//队列的初始化
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)//队列的销毁
//head->node->node->node->node->node->node->tail//单链表的结构
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)//入队
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data=x;
		newnode->next = NULL;
	}

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;//pq->tail=newnode;
	}
	pq->size++;
}

void QueuePop(Queue* pq)//出队
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		del = NULL;
	}
	pq->size--;
}

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;
}

bool QueueEmpty(Queue* pq)//队列判空
{
	assert(pq);
	return pq->head==NULL&&pq->tail == NULL;//
}

int QueueSize(Queue* pq)//判断有效元素个数
{
	assert(pq);

	return pq->size;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));//
    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* Empty=&obj->q1;
    Queue* nonEmpty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        nonEmpty=&obj->q1;
        Empty=&obj->q2;
    }
    int num=QueueSize(nonEmpty);
    if(nonEmpty==NULL)
    {
        return;
    }
    while(num>1)
    {
        QueuePush(Empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
        num--;
    }
    int tmp=QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return tmp;
}

int myStackTop(MyStack* obj) {
    Queue* Empty=&obj->q1;
    Queue* nonEmpty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        nonEmpty=&obj->q1;
        Empty=&obj->q2;
    }
    return QueueBack(nonEmpty);
}

bool myStackEmpty(MyStack* obj) {
    if(&obj->q1==NULL||&obj->q2==NULL)
    {
        return true;
    }
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q1);
    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
  • 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
  • 193

题目3.用栈实现队列

题目链接

思路：
一个队列是 FIFO 的，但一个栈是 LIFO 的。
这就意味着最新压入的元素必须得放在栈底。为了实现这个目的，我们创建两个栈一个专门用来进元素（pushST），一个用来出元素（popST），入队时只往pushST里存放元素，要出队时先把pushST中所有的元素移到popST 中，直接从 popST 弹出就可以了，
注意：当popST不为空的情况下是不需要从pushST里往popST中倒元素的。要出队时直接从popST里出栈即可。
这样设计可以避免来回颠倒元素，减少不必要的麻烦。

在这里插入图片描述
实现代码：

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void StackDestory(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->capacity==ps->top)
	{
		int newcapcaity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, newcapcaity * sizeof(STDataType));
		if (ps->a==NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapcaity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
	
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushST);
    StackInit(&obj->popST);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST,x);
}

int myQueuePop(MyQueue* obj) {
    int tmp=0;
    if(!StackEmpty(&obj->popST))
    {
        tmp=StackTop(&obj->popST);
        StackPop(&obj->popST);
    }
    else
    {
        while(!StackEmpty(&obj->pushST))/犯错之处！！！！！！！！！！！！
        {
        StackPush(&obj->popST,StackTop(&obj->pushST));
        StackPop(&obj->pushST);
        }
        tmp=StackTop(&obj->popST);
        StackPop(&obj->popST);
    }
    return tmp;
}

int myQueuePeek(MyQueue* obj) {
    
    
    if(StackEmpty(&obj->popST)&&!StackEmpty(&obj->pushST))
    {
        while(!StackEmpty(&obj->pushST))/犯错之处！！！！！！！！！！！！
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->popST)&&StackEmpty(&obj->pushST);
}

void myQueueFree(MyQueue* obj) {
    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
  • 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

题目4.设计循环队列

题目链接
思路：
循环队列可用链表实现也可以用数组实现，链表要实现“循环”直接让最后结点的那个next域指向头结点即可，但是用数组实现的话怎么实现循环呢？
设有效个数为k个(为了解决判空和判满，多留出了一个空间，有效个数为k，实际数组个数为k+1)，数组的队头元素下标为front，队尾元素下一个位置的下标为back，（也有书上写front是对头元素的前一个，队尾元素为back，判空判满的表达式一样。）
每次入队的时候先要判断当先队列是否是满的，不为满，让back当前位置赋值要入队的元素，然后back正常++往后走，关键的来了再进行back=back %（k+1）操作即可实现循环。
那怎么区分什么时候空和什么时候满呢？
解决方法：
1、加一个size来记录当前元素的个数。
2、增加一个空间， 假如说长度4，那么就开5个空间，back位置下一个是front就满了（这样做是为了更好的区分队空和队满），所以说满的时候永远留一个空位置。

我们这里用第二种方法。
判断空：
当front和back相等的时候为空。

判断满：
当back的下一个为front时，即(back+1)%k+1和front相等的时候就是满了。
这个比较难想，可以看下面的动图：
下图的k应该是5，这里画错了。
在这里插入图片描述

实现代码：

typedef struct {
    int*a;
    int front;
    int back;
    int N;

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
     MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
     obj->a=(int *)malloc(sizeof(int)*(k+1));///犯错之处！！！！！！！！
     obj->front=obj->back=0;
     obj->N=k+1;

     return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return ((obj->back)+1)%obj->N==obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->back]=value;
    obj->back++;
    obj->back%=obj->N;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front++;
    obj->front%=obj->N;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}

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


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    
    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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/391016
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号