详解栈和队列面试题

详解栈和队列面试题,第1张

✨✨大家好呀!博主这几天正在用C语言学习简单的数据结构😇😇
🌀🌀刚好学习到了栈和队列,学了这么久,想着能不能找几道题来做做😥😥
🌝🌝虽说用C语言做题着实很痛苦💫💫,被小小地打击了一下😟😟
🐸🐸但也加深了博主对数据结构的理解,下面整理了几道栈和队列的题与大家分享。


🌏🌏

山外青山楼外楼,自然探秘永无休
成功易使人陶醉,莫把百尺当尽头

文章目录
  • 😊0.前言😊
  • 💥1.栈和队列面试题💥
    • 🌎1.1 括号匹配问题🌎
    • 🐸1.2. 用队列实现栈🐸
    • 🌀1.3 用栈实现队列🌀
    • 😇1.4 设计循环队列😇

😊0.前言😊

前提知识:
C语言实现栈和队列

💥1.栈和队列面试题💥 🌎1.1 括号匹配问题🌎

题目链接
思路分析:初始化栈,如果是左括号就入栈,如果是右括号就出栈一个左括号元素,出栈了之后与右括号进行匹配,如果不匹配就return false,匹配就继续比。


如果左右括号的数量不相等怎么办呢?只要在最后判断一下栈是否为空就行了,栈为空return true;栈不为空,return false;另外只有右括号时也要单独判断一下,因为只有右括号,栈就是空了,此时再出栈就越界了。



💫友情提醒,return之前别忘了free哦,防止内存泄漏,养成好习惯。


💫

//C语言实现栈
/******************************************************************************************/
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);
bool StackEmpty(ST* ps);
STDataType StackTop(ST* ps);


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;
		ps->a = (STDataType*)realloc(ps->a, newCapacity* sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}

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

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
/******************************************************************************************/


//做题
bool isValid(char * s)
{
    ST st;
    StackInit(&st);
    while(*s)
    {
        //如果是左括号就入栈
        if(*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&st, *s);
            ++s;
        }
        else
        {
            //只有右括号,匹配失败
            if(StackEmpty(&st))
            return false;
            
            //如果是右括号,出栈一个左括号进行匹配
            char top = StackTop(&st);
            StackPop(&st);
            if((*s==']' && top !='[')
            ||(*s=='}' && top !='{')
            ||(*s==')' && top !='('))
            {
                //匹配失败,return false,return之前销毁栈防止内存泄漏
                StackDestroy(&st);
                return false;
            }
            else
            {
                //匹配成功,继续比
                ++s;
            }
        }
    }
    //栈为空,说明所有括号都匹配了
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}
🐸1.2. 用队列实现栈🐸

题目链接

两个队列模拟出栈:

再入栈再出栈:

结构实现:

//C语言实现队列
/******************************************************************************************/
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

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

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

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

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);

	newnode->data = x;
	newnode->next = NULL;

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

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);

	return pq->tail->data;
}
/******************************************************************************************/



//做题
typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() 
{
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    assert(pst);
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

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

int myStackPop(MyStack* obj) 
{
    assert(obj);
    //默认q1是空队列,q2是非空队列
    Queue* emptyQ = &obj->q1;
    Queue* nonEmptyQ = &obj->q2;
    //修正
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonEmptyQ = &obj->q1;
    }

    //把非空队列的前N-1个数据,倒入空队列
    //就实现了后进先出
    while(QueueSize(nonEmptyQ)>1)
    {
        int front = QueueFront(nonEmptyQ);
        QueuePush(emptyQ,front);
        QueuePop(nonEmptyQ);
    }
    int top = QueueFront(nonEmptyQ);
    //剩下一个删掉
    QueuePop(nonEmptyQ);
    return top;
}

int myStackTop(MyStack* obj) 
{
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

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

void myStackFree(MyStack* obj) 
{
    assert(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.3 用栈实现队列🌀

题目链接

模拟QueuePop:

再入队列再出队列:

// 使用两个数组(栈)和指针定义队列,两个指针分别指向对应的栈顶
typedef struct {
    int PushSTTop, PopSTTop;
    int PushST[100], PopST[100];
} MyQueue;

// 开辟一个队列
MyQueue* myQueueCreate() {
    MyQueue* queue = malloc(sizeof(MyQueue));
    queue->PushSTTop = 0;
    queue->PopSTTop = 0;
    return queue;
}

// 将元素存入输入栈中,存入后栈顶指针 +1
void myQueuePush(MyQueue* obj, int x) {
    obj->PushST[(obj->PushSTTop)++] = x;
}

int myQueuePop(MyQueue* obj) {
    // 优化:复制栈顶指针,减少对内存的访问次数
    int PushSTTop = obj->PushSTTop;
    int PopSTTop = obj->PopSTTop;

    // 若输出栈为空
    if (PopSTTop == 0) {
        // 将输入栈中所有元素复制到输出栈中
        while (PushSTTop > 0) {
            obj->PopST[PopSTTop++] = obj->PushST[--PushSTTop];
        }
    }
    // 将输出栈栈顶元素出栈并保存
    int top = obj->PopST[--PopSTTop];
    // 将输出栈中元素放回输入栈中
    while (PopSTTop > 0) {
        obj->PushST[PushSTTop++] = obj->PopST[--PopSTTop];
    }

    // 更新栈顶指针
    obj->PushSTTop = PushSTTop;
    obj->PopSTTop = PopSTTop;

    // 返回队列中的第一个元素
    return top;
}

// 返回输入栈的栈底元素
int myQueuePeek(MyQueue* obj) {
    return obj->PushST[0];
}

// 若输入栈和输出栈都为空,则队列为空
bool myQueueEmpty(MyQueue* obj) {
    return obj->PushSTTop == 0 && obj->PopSTTop == 0;
}

// 将栈顶指针都归 0
void myQueueFree(MyQueue* obj) {
    obj->PushSTTop = 0;
    obj->PopSTTop = 0;
}

😇1.4 设计循环队列😇

题目链接

思路分析:

Push:

为了避免空和满混淆,无法区分,多开一个空间(比如开4个空间只能存3个数据)。


front==tail时是空,tail的下一个位置是front,就是满。


满又分为两种情况:
1.

2.

此时已经是满了,不能再进行Push数据,必须先Pop数据。



Pop:

只要队列不是满的,就可以继续插入数据,front == tail就删为空。


继续Push数据:

此时队列又写满了,必须删除数据再写入数据,以此达到循环队列的目的。


typedef struct 
{
    int* a;
    int front;
    int tail;
    int k;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //数组多开一个空间
    obj->a =(int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->tail = 0;
    obj->k = k;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //满了就不能写入数据
    if(myCircularQueueIsFull(obj))
    return false;
    obj->a[obj->tail] = value;
    //tail走到最后一个空间,到了边界,就置回第一个位置
    if(obj->tail == obj->k)
    {
        obj->tail = 0;
    }
    else
    {
        obj->tail++;
    }
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    //空了就不能删除数据
    if(myCircularQueueIsEmpty(obj))
    return false;
    //front走到最后一个空间,到了边界,置回第一个位置
    if(obj->front == obj->k)
    {
        obj->front = 0;
    }
    else
    {
        obj->front++;
    }
    return true;
}

//取队头数据
int myCircularQueueFront(MyCircularQueue* obj) 
{
   //题目要求队列为空返回-1
   if(myCircularQueueIsEmpty(obj))
   return -1;
   return obj->a[obj->front];
}

//取队尾数据
int myCircularQueueRear(MyCircularQueue* obj)
{
    //题目要求,空队列返回-1
    if(myCircularQueueIsEmpty(obj))
    return -1;
    //如果tail在第一个位置,队尾是在k
    if(obj->tail == 0)
    {
        return obj->a[obj->k];
    }
    else
    {
        //否则队尾就是tail-1
        return obj->a[obj->tail-1];
    }
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
	//满的第二种情况
    if(obj->tail == obj->k && obj->front == 0)
    {
        return true;
    }
    else
    {
    	//满的第一种情况
        return obj->tail+1 == obj->front;
    }
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->a);
    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);
*/

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/langs/562259.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-04-01
下一篇2022-04-01

随机推荐

  • 水浒传主要人物及情节概括_水浒传的著名故事情节概括

    《水浒传》主要故事人物情节概括一、鲁智深 绰号:花和尚“生得面圆身大,鼻直口方,腮边一部貉绒须。身长八尺,腰阔十围。手持一柄禅杖,腰系一把戒刀。”性格特点:嫉恶如仇、脾气火爆、侠肝义胆、粗中有细、豁达明理。主要故事情节简介:1.鲁

    2022-12-29
    2100
  • 怎么和孩子一起看抖音直播呢

    1、首先打开抖音APP,进入直播间。点击中心,选择一起看。2、然后点击个人界面的好友,选择下面的邀请,即可一起观看。抖音,是由字节跳动孵化的一款音乐创意短视频社交软件。该软件于2016年9月20日上线,是一个面向全年龄的短视频社区平台,用户

    2022-12-29
    1900
  • 成立业主委员会要注意什么

    导读:业主委员会是从小区业主当中选出,协助与制约物业公司,维护好业主的权益的。那么,成立业主委员会要注意什么呢?1、成立之前,必须先和当地政府或者是居委会进行申请和沟通,申请通过以后,再根据规定的法律程序来办理正式的业主委员选举大会,同时还

    2022-12-29
    1700
  • 洛阳桥位于何地

    很多地方都有自己特色的建筑物,并且很多地方因为某些特殊的建筑物而闻名,受到各地人的旅游,其中一个地方有座桥叫洛阳桥。那么洛阳桥位于何地呢?洛阳桥位于何地1、洛阳桥位于福建省泉州市,位于洛阳江水道之上。2、著名的跨海梁式大石桥,素有“海内第一

    2022-12-29
    1200
  • 蓝盒子和菠萝斑马哪个好(蓝盒子 菠萝斑马)

    在挑选家具上面,床垫是尤为重要的,如果经济条件不错,建议大家选择实体店购买,自己躺上去体验了才知道哪款床垫是最舒适的。而目前网上刮风比较大的蓝盒子和菠萝斑马哪个好呢?一起来看看网友们的评测再进行选择吧!蓝盒子和菠萝斑马哪个好首先说斑马菠萝,

    2022-12-29
    2000
  • 1升等于多少毫升

    在生活中,我们经常会用升和毫升来表示液体,那有想过一升等于多少毫升吗?下面一起来看解答。1升等于多少毫升 1、1升等于1000毫升。升是容积单位,升在国际单位制中表示为L,其次级单位为毫升(mL)。2、民间也有一种以“升”为计量单位的方法,

  • 以人名命名的城市

    中国现存以人名命名的城市有中山市、茂名市、尚志市、秦皇岛、任丘市、黄骅市、志丹县、子长县、子洲县、1、中山市,以孙中山的名字命名。孙中山故里、孙文西路步行街、岐江公园、中山城等。2、茂名市,以潘茂名的名字命名。浮山岭、虎头山、放鸡岛、中国第

  • 博世2.2尿素泵膜片怎么装_万能万能表的使用方法

    博世2.2尿素膜片泵是博世系列生产的第二代选择性催化还原系统的升级版,主要针对柴油商用车及非道路工程机械开发研究。尿素泵由上下盖及泵体三大部分组成,其中连接部件有进液管、回液管、喷射管三个尿素管路接口;内部元件有保护电阻、尿素泵主泵、主板、

    2022-12-29
    1800
  • 外墙保温锚固钉一平方多少个

    导读:为了增强外墙保温施工的牢固性,通常需要在墙面上加装锚固钉。锚固钉需要用到的数量一般根据房屋楼层数量而定,那么外墙保温锚固钉一平方多少个呢?外墙保温锚固钉一平方一般都是五个到六个左右,这个问题并没有固定答案,一般都需要看房屋楼层数量。若

    2022-12-29
    1900

发表评论

登录后才能评论

评论列表(0条)

    保存