栈的2道面试题【有效的括号】【用栈实现队列】

发布于：2024-05-08 ⋅ 阅读:(29) ⋅ 点赞:(0)

栈的面试题：

1.有效的括号

题目：

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

思路：

  1. 首先我们可以知道我们需要去比较字符串内的元素，并且我们需要用到后进先出的场景，因此这里我们考虑用栈来解决问题
  2. 我们将前括号放到栈内，s指针如果指向的是后括号，就让其和栈内的栈顶元素对比，如果匹配就将栈顶元素弹出，s继续遍历
  3. 一旦不匹配，或者栈空了，s还有后括号没有匹配，或者栈还有元素，s没有后括号匹配了就是无效字符串，返回false

代码实现：

由于我们是使用C语言写oj题，因此我们需要自己去编写栈的定义和栈的接口实现

如果是在leetcode上，头文件之类的自己会包含，我们不用去管

接口：
// 这里的栈我们用动态顺序表实现 (也可以用静态顺序表实现[不好扩容和定义空间大小])
# include<stdio.h>
# include<assert.h>
# include<stdlib.h>
# include<stdbool.h>

typedef char SLDataType;
typedef struct Stack
{
	SLDataType* _a;
	int _top; // 栈顶下标 [规定栈顶下标：最后一个有效数据的下一个位置]
	int _capacity; // 数组的有效空间大小 
}Stack;


// 栈的初始化
void StackInit(Stack* ps);

// 栈的销毁
void StackDestory(Stack* ps);

// 栈是能从栈顶  存数据或者取数据，因此不存在尾插头插之类的
// 入栈
void StackPush(Stack* ps, SLDataType x);

// 出栈
void StackPop(Stack* ps);

// 栈的数据个数获取
//int StackSize(Stack st); //其实理论上获取元素个数只需要传值调用就行 但是为了保持接口一致性，我们采用指针
int StackSize(Stack* ps);

// 获取栈顶元素
SLDataType StackTop(Stack* ps);

// 判断栈是否为空
int StackEmpty(Stack* ps); // 是空返回1  不是空的返回0

// 栈的初始化
void StackInit(Stack* ps)
{
	assert(ps); // ps不能为NULL

	// 栈的初始化
	/*ps->_a = NULL;
	ps->_top = 0;
	ps->_capacity = 0;*/

	// 除了上面这种初始化。也可以这样初始化
	SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType) * 4); // 这样后面入栈时无需判断 空间是否为0 
	if (tmp == NULL)
	{
		perror("StackInit():malloc()");
		return;
	}

	ps->_a = tmp;
	ps->_top = 0;
	ps->_capacity = 4;
}

// 栈的销毁
void StackDestory(Stack* ps)
{
	assert(ps);

	free(ps->_a);
	ps->_a = NULL;

	ps->_top = ps->_capacity = 0;
}

// 入栈
void StackPush(Stack* ps, SLDataType x)
{
	assert(ps);

	// 插入之前 判断栈的空间是否足够新的数据插入
	if (ps->_top == ps->_capacity) // 判断空间是否足够 
	{
		int newcapacity = ps->_capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->_a, sizeof(SLDataType) * newcapacity); // 增容
		if (tmp == NULL) // 判断是否增容成功
		{
			perror("StackPush():realloc()");
			return;
		}

		// 更新栈
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}

	ps->_a[ps->_top] = x; // 入栈
	ps->_top++; // 让top记录的是栈顶 也就是最后一个数据的下一个位置
}

// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0); // 栈里面要有数据才能出栈

	ps->_top--; // 让top--就行 最后一个数据的下标是 top - 1
}

// 栈的数据个数获取
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->_top; // top代表栈顶下标，是最后的一个数据的下标 + 1  其实就是栈的数据个数
}

// 获取栈顶元素
SLDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0); // 没有数据还怎么获取

	return ps->_a[ps->_top - 1]; // top是栈顶下标，top - 1才是最后一个数据的下标
}

// 判断栈是否为空
int StackEmpty(Stack* ps) // 是空返回1  不是空的返回0
{
	assert(ps);

	return ps->_top == 0 ? 1 : 0; // ps->pos只要为0就说明栈内没有数据了
	//return !ps->_top; // ps->top 为0 就返回1，为真就返回 0 ，除了0的数都是真
}
代码：
bool isValid(char* s)
{
    // 由于这道题需要用到后进先出的特性，因此我们使用栈来解决
    // 创建一个栈
    Stack st;
    StackInit(&st); // 初始化
    bool ret = true; // 用来判断字符串是否有效

    // 遍历字符串
    while (*s != '\0')
    {
        // 如果s指针指向的是前括号就入栈
        if (*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st, *s);
            s++; // 让s往后走
        }
        else
        {
            // 走到这里有可能是s后括号多，栈内已经没有前括号了,那后面去取栈顶元素自然无法取出
            if (StackEmpty(&st))// 判断栈是否空了
            {
                // 走进来就说明栈内没有元素了，但是s还有后括号
                ret = false; // 无效字符串
                break;
            }
            // 判断s下一步指向的是否是后括号，是否匹配栈顶的前括号
            char top = StackTop(&st); // 取出栈顶元素
            // 每一种括号都要判断一下是否匹配到
            if (*s == ')' && top != '(')
            {
                // 走到这里说明没有匹配上
                ret = false; // 无效字符串
                break; // 不在这里return false是因为会有内存泄漏问题，跳出循环去外面统一调用销毁函数
            }
            if (*s == ']' && top != '[')
            {
                // 走到这里说明没有匹配上
                ret = false; // 无效字符串
                break;
            }
            if (*s == '}' && top != '{')
            {
                // 走到这里说明没有匹配上
                ret = false; // 无效字符串
                break;
            }

            // 走到这里说明有括号配对成功，让s继续往后遍历
            s++;
            // 栈顶元素匹配成功之后要弹出来，防止后面还有括号要配对
            StackPop(&st);
        }

    }
    // 走到这里，有可能是全部匹配完是true。 
    //也有可能是s字符串只有前括号比后括号多 退出循环时，栈内还有许多前括号
    if (!StackEmpty(&st)) // 判断栈是否为空
        ret = false; // 不是空的就是无效字符串

    StackDestory(&st); // 销毁栈

    if (ret == false)
        return false;

    // 走到这里就说明是有效字符串
    return true;
}

2.用栈实现队列

题目：

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路：

  1. 要通过两个栈实现先进先出的队列，我们要思考数据转移的特性

  2. 我们发现，我们把栈的数据转移到另外一个栈的时候，数据的顺序会倒转

  3. image-20240507223619789

  4. image-20240507223635988

  5. 然后我们发现，这样就是先进先出了，1，2， 3， 4压进去，出来也是从栈顶出来，1, 2, 3, 4。 也就是说 第一个栈的栈顶就是队列的队尾，第二个栈的栈顶就是队列的队头。

    • 那我们给这个队列插入数据时候，要从队尾插入，也就是要把数据从第二个栈全部转移到第一个栈。
    • 队列导出数据的时候，也就是从队头出，那就要把数据从第一个栈全部转移到第二个栈。

代码实现：

接口：
// 这里的栈我们用动态顺序表实现 (也可以用静态顺序表实现[不好扩容和定义空间大小])

typedef int SLDataType;
typedef struct Stack
{
	SLDataType* _a;
	int _top; // 栈顶下标 [规定栈顶下标：最后一个有效数据的下一个位置]
	int _capacity; // 数组的有效空间大小 
}Stack;


// 栈的初始化
void StackInit(Stack* ps);

// 栈的销毁
void StackDestory(Stack* ps);

// 栈是能从栈顶  存数据或者取数据，因此不存在尾插头插之类的
// 入栈
void StackPush(Stack* ps, SLDataType x);

// 出栈
void StackPop(Stack* ps);

// 栈的数据个数获取
//int StackSize(Stack st); //其实理论上获取元素个数只需要传值调用就行 但是为了保持接口一致性，我们采用指针
int StackSize(Stack* ps);

// 获取栈顶元素
SLDataType StackTop(Stack* ps);

// 判断栈是否为空
int StackEmpty(Stack* ps); // 是空返回1  不是空的返回0

// 栈的初始化
void StackInit(Stack* ps)
{
	assert(ps); // ps不能为NULL

	// 栈的初始化
	/*ps->_a = NULL;
	ps->_top = 0;
	ps->_capacity = 0;*/

	// 除了上面这种初始化。也可以这样初始化
	SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType) * 4); // 这样后面入栈时无需判断 空间是否为0 
	if (tmp == NULL)
	{
		perror("StackInit():malloc()");
		return;
	}

	ps->_a = tmp;
	ps->_top = 0;
	ps->_capacity = 4;
}

// 栈的销毁
void StackDestory(Stack* ps)
{
	assert(ps);

	free(ps->_a);
	ps->_a = NULL;

	ps->_top = ps->_capacity = 0;
}

// 入栈
void StackPush(Stack* ps, SLDataType x)
{
	assert(ps);

	// 插入之前 判断栈的空间是否足够新的数据插入
	if (ps->_top == ps->_capacity) // 判断空间是否足够 
	{
		int newcapacity = ps->_capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->_a, sizeof(SLDataType) * newcapacity); // 增容
		if (tmp == NULL) // 判断是否增容成功
		{
			perror("StackPush():realloc()");
			return;
		}

		// 更新栈
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}

	ps->_a[ps->_top] = x; // 入栈
	ps->_top++; // 让top记录的是栈顶 也就是最后一个数据的下一个位置
}

// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0); // 栈里面要有数据才能出栈

	ps->_top--; // 让top--就行 最后一个数据的下标是 top - 1
}

// 栈的数据个数获取
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->_top; // top代表栈顶下标，是最后的一个数据的下标 + 1  其实就是栈的数据个数
}

// 获取栈顶元素
SLDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0); // 没有数据还怎么获取

	return ps->_a[ps->_top - 1]; // top是栈顶下标，top - 1才是最后一个数据的下标
}

// 判断栈是否为空
int StackEmpty(Stack* ps) // 是空返回1  不是空的返回0
{
	assert(ps);

	return ps->_top == 0 ? 1 : 0; // ps->pos只要为0就说明栈内没有数据了
	//return !ps->_top; // ps->top 为0 就返回1，为真就返回 0 ，除了0的数都是真
}
代码（自己实现的版本）：
typedef struct 
{
    Stack _s1;
    Stack _s2;    
} MyQueue;


MyQueue* myQueueCreate() 
{
    // 创建栈
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pq->_s1);
    StackInit(&pq->_s2);

    return pq;
}

void myQueuePush(MyQueue* obj, int x) 
{
    // 给队列插入元素，要在第一个栈插入
    // 如果第二个栈有数据，要将其全部转移到第一个栈
    if(!StackEmpty(&obj->_s2))
    {
        // 第二个栈的数据有数据，将其全部转移到第一个栈
        while(StackSize(&obj->_s2) > 0)
        {
            // 转移
            StackPush(&obj->_s1, StackTop(&obj->_s2));
            // 让第二个栈的数据出栈
            StackPop(&obj->_s2);
        }
    }

    // 走到这里，如果第二个栈有数据，也全部转移到第一个栈
    // 如果第二个栈没有数据，那就直接在第一个栈插入数据就好
    StackPush(&obj->_s1, x);    
}

int myQueuePop(MyQueue* obj) 
{
    // 要找到队头（队列开头的元素）就要把全部数据都放在第二个栈，栈顶的数据就是队头
    if(!StackEmpty(&obj->_s1)) 
    {
        // 第一个栈的数据有数据，将其全部转移到第二个栈
        while(StackSize(&obj->_s1) > 0)
        {
            // 转移
            StackPush(&obj->_s2, StackTop(&obj->_s1));
            // 让第一个栈的数据出栈
            StackPop(&obj->_s1);
        }
    }
    // 由于题目说了一个空的队列不会调用 pop 或者 peek 操作
    // 因此这里不用判断两个栈是否为空

    // 走到这里数据一定在第二个栈
    int ret = StackTop(&obj->_s2);
    StackPop(&obj->_s2); // 移除元素
    return ret;
}

int myQueuePeek(MyQueue* obj) 
{
      // 要找到队头（队列开头的元素）就要把全部数据都放在第二个栈，栈顶的数据就是队头
    if(!StackEmpty(&obj->_s1))
    {
        // 第一个栈的数据有数据，将其全部转移到第二个栈
        while(StackSize(&obj->_s1) > 0)
        {
            // 转移
            StackPush(&obj->_s2, StackTop(&obj->_s1));
            // 让第一个栈的数据出栈
            StackPop(&obj->_s1);
        }
    }
    // 由于题目说了一个空的队列不会调用 pop 或者 peek 操作
    // 因此这里不用判断两个栈是否为空

    // 返回队头，也就是第二个栈的栈顶数据
    return StackTop(&obj->_s2);
}

bool myQueueEmpty(MyQueue* obj) 
{
    // 如果两个栈都为空，队列才是空
    return StackEmpty(&obj->_s1) && StackEmpty(&obj->_s2);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestory(&obj->_s1);
    StackDestory(&obj->_s2);

    free(obj);
    obj = NULL;
}
优化后的代码：
typedef struct 
{
    Stack _pushST; // 用于插入数据
    Stack _popST; // 用于出数据
} MyQueue;


MyQueue* myQueueCreate() 
{
    // 创建栈
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pq->_pushST);
    StackInit(&pq->_popST);

    return pq;
}

void myQueuePush(MyQueue* obj, int x) 
{
    // 直接把数据插入到pushST栈内
    StackPush(&obj->_pushST, x);
}

int myQueuePop(MyQueue* obj) 
{
    // 这个函数的功能和peek函数的功能就多了一个要移除，也就是让队头数据弹出
    // 那我们就考虑让代码复用
    int ret = myQueuePeek(obj);
    StackPop(&obj->_popST); // 代码复用
    return ret;
}

int myQueuePeek(MyQueue* obj) 
{
    // 要找到队头 也就是popST的栈顶数据
    // 要分两种情况，
    //1.如果popST栈没有数据，那就把pushST栈的数据转移到popST栈内
    //2.如果popST有数据，直接返回栈顶的数据，这个数据就是队头
    if(!StackEmpty(&obj->_popST))
    {
        // popST有数据，直接返回栈顶数据，就是队头
        return StackTop(&obj->_popST);
    }
    else
    {
        // popST为空，将pushST栈的数据转移到popST栈内
        while(!StackEmpty(&obj->_pushST)) // 判断是否为空
        {
            StackPush(&obj->_popST, StackTop(&obj->_pushST));
            StackPop(&obj->_pushST); // 出栈
        } 

        return StackTop(&obj->_popST);
    }

}

bool myQueueEmpty(MyQueue* obj) 
{
    // 如果两个栈都为空，队列才是空
    return StackEmpty(&obj->_pushST) && StackEmpty(&obj->_popST);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestory(&obj->_popST);
    StackDestory(&obj->_pushST);

    free(obj);
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布