【数据结构】3道经典面试题带你玩转栈与队列

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

目录

一.有效的括号

二.用栈实现队列

三.用队列实现栈

结语

一.有效的括号

题目链接

20. 有效的括号https://leetcode.cn/problems/valid-parentheses/

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

题目详情

解题思路

本题解题思路为:

创建一个栈

遍历字符串s,遇到左括号则将其入栈

遇到右括号则取栈顶元素和它匹配

匹配成功则将栈顶元素出栈继续遍历,失败则返回false

直到遍历完字符串s,栈中元素也都恰好匹配完毕则返回true

细节问题:动态开辟的内存需要换给系统,在程序设置好几个return点的情况下特别要保证每个return前都应有Destroy的操作.

解题代码

综上,本题解题代码如下:

typedef char STDataType;




typedef struct Stack

{

    STDataType*arr;

    int top;

    int capacity;

}ST;




bool STEmpty(ST* ps)//判空,为空则真

{

    assert(ps);

    return ps->top==0;

}




void STInit(ST* ps)

{

    assert(ps);




    ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);

    if (ps->arr == NULL)

    {

        perror("malloc fail::\n");

        return;

    }

    ps->capacity = 4;

    ps->top = 0; //top表示栈顶元素的下一个

     //top指向栈顶元素的话,top给-1

}




void STDestroy(ST* ps)

{

    assert(ps);

    free(ps->arr);

    ps->arr = NULL;

    ps->top = 0;

    ps->capacity = 0;

}




void STPush(ST* ps, STDataType x)

{

    assert(ps);




    if (ps->top == ps->capacity)//扩容

    {

        STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * ps->capacity * 2);

        if (tmp == NULL)

        {

            perror("realloc fail::\n");

            return;

        }

        ps->arr = tmp;

        ps->capacity *= 2;

    }

    ps->arr[ps->top] = x;

    ps->top++;

}




void STPop(ST* ps)

{

    assert(ps);

    assert(!STEmpty(ps));

    ps->top--;

}




STDataType STTop(ST* ps)

{

    assert(ps);

    assert(!STEmpty(ps));

    return ps->arr[ps->top - 1];

}




bool isValid(char* s)

{

ST st;

STInit(&st);

char*cur=s;




while(*cur!='\0')

{

//如果是左括号,入栈

if(*cur=='{'||*cur=='['||*cur=='(')

{

STPush(&st,*cur);

}

//如果是右括号,和栈顶元素匹配,相同就出栈,不同就false

else

{

if(STEmpty(&st))

{

STDestroy(&st);

return false;

}

if(*cur==')'&&STTop(&st)=='(')

{

STPop(&st);

}

else if(*cur==']'&&STTop(&st)=='[')

{

STPop(&st);

}

else if(*cur=='}'&&STTop(&st)=='{')

{

STPop(&st);

}

else

{

STDestroy(&st);

return false;

}

}

cur++;

}

if(STEmpty(&st))

{

STDestroy(&st);

return true;

}

else

{

STDestroy(&st);

return false;

}




}

提交运行:

二.用栈实现队列

题目链接

232. 用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/

题目描述

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

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

题目详情

解题思路

本题解题思路为:

先定义栈的结构并完成其相关操作函数(即定义栈,实现栈)

创建MyQueue结构体,其中包含两个栈(push栈和pop栈)

MyQueue入队入push栈即可.

MyQueue出队出pop栈顶的元素,如果pop栈为空,则先将push栈中的所有元素依次入pop栈后再出pop栈顶元素,图示如下:

MyQueue初始化,取队头元素,查空,销毁函数逻辑较简单,思路见下方解题代码注释.

解题代码

综上,本题解题代码如下:

//先创建两个栈及栈的相关操作,然后组合实现队列的效果

//定义栈:

typedef int STDataType;

typedef struct Stack

{

    STDataType*arr;

    int top;

    int capacity;

}ST;




void STInit(ST* ps);

void STDestroy(ST* ps);

void STPush(ST* ps, STDataType x);

void STPop(ST* ps);

int STSize(ST* ps);

bool STEmpty(ST* ps);//判空,为空则真

STDataType STTop(ST* ps);

//实现栈:

void STInit(ST* ps)

{

    assert(ps);

    ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);

    if (ps->arr == NULL)

    {

        perror("malloc fail::\n");

        return;

    }

    ps->capacity = 4;

    ps->top = 0; //top表示栈顶元素的下一个

     //top指向栈顶元素的话,top给-1

}




void STDestroy(ST* ps)

{

    assert(ps);

    free(ps->arr);

    ps->arr = NULL;

    ps->top = 0;

    ps->capacity = 0;

}




void STPush(ST* ps, STDataType x)

{

    assert(ps);

    if (ps->top == ps->capacity)//扩容

    {

        STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * ps->capacity * 2);

        if (tmp == NULL)

        {

            perror("realloc fail::\n");

            return;

        }

        ps->arr = tmp;

        ps->capacity *= 2;

    }

    ps->arr[ps->top] = x;

    ps->top++;

}




void STPop(ST* ps)

{

    assert(ps);

    assert(!STEmpty(ps));

    ps->top--;

}




int STSize(ST* ps)

{

    assert(ps);

    return ps->top;

}




bool STEmpty(ST* ps)//判空,为空则真

{

    assert(ps);

    return ps->top==0;

}




STDataType STTop(ST* ps)

{

    assert(ps);

    assert(!STEmpty(ps));

    return ps->arr[ps->top - 1];

}




//实现队列







typedef struct {

ST pushst;

ST popst;

} MyQueue;







MyQueue* myQueueCreate() //MyQueue结构体初始化,将两个栈分别初始化即可

{

MyQueue *obj=(MyQueue*)malloc(sizeof(MyQueue));

if(obj==NULL)

{

perror("malloc fail::\n");

return NULL;

}

STInit(&obj->pushst);

STInit(&obj->popst);

return obj;

}




void myQueuePush(MyQueue* obj, int x) //MyQueue进栈,进栈元素进pushst栈即可

{

STPush(&obj->pushst , x);

}




int myQueuePop(MyQueue* obj)//MyQueue出栈

{

//如果pop栈不为空就出pop栈顶的元素

if(!STEmpty(&obj->popst))

{

int x=STTop(&obj->popst);

STPop(&obj->popst);

return x;

}

else//如果pop栈为空,就先倒Push栈的元素过来,再出pop栈顶的元素

{

while(!STEmpty(&obj->pushst))//倒push栈必须将现有的元素全部倒过来

{

int x=STTop(&obj->pushst);

STPush(&obj->popst , x);

STPop(&obj->pushst);

}

//倒完出pop栈顶元素

int x=STTop(&obj->popst);

STPop(&obj->popst);

return x;

}

}




int myQueuePeek(MyQueue* obj)//MyQueue取栈顶元素(逻辑比出栈少一个出)

{

if(!STEmpty(&obj->popst))

{

return STTop(&obj->popst);

}

else//如果pop栈为空,就先倒Push的过来,再pop

{

while(!STEmpty(&obj->pushst))

{

int x=STTop(&obj->pushst);

STPush(&obj->popst , x);

STPop(&obj->pushst);

}

return STTop(&obj->popst);

}

}




bool myQueueEmpty(MyQueue* obj)//MyQueue查空,push和pop栈都为空则MyQueue为空

{

return (STEmpty(&obj->pushst)&&STEmpty(&obj->popst));

}




void myQueueFree(MyQueue* obj) //MyQueue销毁,分别将push栈和pop栈销毁后把obj销毁即可

{

STDestroy(&obj->pushst);

STDestroy(&obj->popst);

free(obj);

}

提交运行:

三.用队列实现栈

题目链接

225. 用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

题目详情

解题思路

本题解题思路为:

先定义队列的结构并完成其相关操作函数(即定义队列,实现队列)

创建MyStack结构体,其中包含两个队列(q1队列和q2队列),结构图示如下:

我们需要一直保持q1和q2中有一个空队列,以便可以模拟出栈.

MyStack入栈时入q1和q2中的非空栈,图示如下:

MyStack出栈时将q1和q2中的非空队的前n-1个元素全部入队到空队列中,然后将剩下的那个元素出栈,图示如下:

MyStack取栈顶元素相当于取非空队的队尾元素.

MyStack初始化,判空,销毁逻辑较为简单,思路见下方解题代码注释.

解题代码

//先自己创建两个队列,然后调用这两个队列完成栈的操作.




//定义队列

typedef int QDatatype;

typedef struct QueueNode//一个是结点结构

{

    struct QueueNode* next;

    QDatatype data;

}QNode;

typedef struct Queue//一个是队列整体结构

{

    QNode* head;

    QNode* tail;

    int size ;

}Que;

void QueueInit(Que* pq);

void QueueDestroy(Que* pq);

void QueuePush(Que* pq,QDatatype x);

void QueuePop(Que* pq);

int QueueSize(Que* pq);

bool QueueEmpty(Que* pq);

QDatatype QueueFront(Que* pq);

QDatatype QueueBack(Que* pq);




//实现队列操作

void QueueInit(Que* pq)

{

    assert(pq);

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

    pq->size = 0;

}

void QueueDestroy(Que* pq)

{

    assert(pq);

    QNode* cur = pq->head;

    while (cur)

    {

        QNode* next = cur->next;

        free(cur);

        cur = next;

    }

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

    pq->size = 0;

}




void QueuePush(Que* pq, QDatatype x) //入队是尾插

{

    QNode* newnode = (QNode*)malloc(sizeof(QNode));

    if (newnode == NULL)

    {

        perror("malloc fail");

        return;

    }

    newnode->data = x;

    newnode->next = NULL;

    if (pq->head == NULL)//头插

    {

        assert(pq->tail == NULL);

        pq->head = pq->tail = newnode;

    }

    else//尾插

    {

        pq->tail->next = newnode;

        pq->tail = newnode;

    }

    pq->size++;

}




void QueuePop(Que* pq)//出队是头删

{

    assert(pq);

    assert(!QueueEmpty(pq));//assert为假会终止程序

    QNode* cur = pq;

    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;

    }

    pq->size--;

}




int QueueSize(Que* pq)

{

    assert(pq);

    return pq->size;

}




bool QueueEmpty(Que* pq)//判空!为空返回真!

{

    assert(pq);

    return pq->size==0;

}




QDatatype QueueFront(Que* pq)

{

    assert(pq);

    assert(!QueueEmpty(pq));

    return pq->head->data;

}




QDatatype QueueBack(Que* pq)

{

    assert(pq);

    assert(!QueueEmpty(pq));

    return pq->tail->data;

}




//实现栈

typedef struct

{

Que q1;

Que q2;

} MyStack;




MyStack* myStackCreate()

{

MyStack*obj=(MyStack*)malloc(sizeof(MyStack));

if(obj==NULL)

{

perror("malloc fail::\n");

return NULL;

}

QueueInit(&obj->q1);

QueueInit(&obj->q2);

return obj;

}




void myStackPush(MyStack* obj, int x) //入栈入非空队

{

if(QueueEmpty(&obj->q1))//如果q1为空,入q2

{

QueuePush(&obj->q2,x);

}

else

{

QueuePush(&obj->q1,x);

}




//都为空走else,也可以

}




//出栈把非空队前n-1个元素全部插入空队,然后出非空队

int myStackPop(MyStack* obj)

{

if(QueueEmpty(&obj->q1))//如果q1为空,出q2的n-1元素到q1

{

int n=QueueSize(&obj->q2)-1;

while(n--)//先出q2再入q1

{

int x=QueueFront(&obj->q2);

QueuePush(&obj->q1,x);

QueuePop(&obj->q2);

}

//q2的最后一个元素出函数

int top=QueueFront(&obj->q2);

QueuePop(&obj->q2);

return top;

}

else//如果q2为空,出q1的n-1元素到q2

{

int n=QueueSize(&obj->q1)-1;

while(n--)//先出q2再入q1

{

int x=QueueFront(&obj->q1);

QueuePush(&obj->q2,x);

QueuePop(&obj->q1);

}

//q2的最后一个元素出函数

int top=QueueFront(&obj->q1);

QueuePop(&obj->q1);

return top;

}

}




int myStackTop(MyStack* obj)//栈顶=队尾

{

if(QueueEmpty(&obj->q1))//如果q1为空,返回q2队尾

{

return QueueBack(&obj->q2);

}

else

{

return QueueBack(&obj->q1);

}

}




bool myStackEmpty(MyStack* obj) //q1&&q2为空才为空

{

return (QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2));

}




void myStackFree(MyStack* obj) //释放q1,q2,obj

{

QueueDestroy(&obj->q1);

QueueDestroy(&obj->q2);

free(obj);

}

提交运行:

结语

希望通过上面的题目能使大家对栈和队列这两个经典的数据结构的理解以及运用能够更上一层楼,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

​