详解栈和队列面试题

✨✨大家好呀！博主这几天正在用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);
*/