栈与队列面试题

本篇内容是建立在Stack.c与Queue.c函数已经做好！！！
链接：https://blog.csdn.net/sifanchao/article/details/80628348

实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值）的时间复杂度为O(1)

思路：
    定义两个栈，一个栈（st）进行入栈出栈操作，一个栈(minst)放当前最小值。那么什么时候更新最小栈数据呢？有两种情况：
    1.当最小栈为空栈时，将此时压栈st的数据拷贝到最小栈里。
    2.如果当前最小栈的数据>=压栈的数据，满足条件时，进行数据拷贝。
    最后对Push、Pop就对st进行操作，取Min值时对minst操作

函数声明（Topic.h）

#pragma once 
#include "Stack.h"
typedef struct MinStack
{
    Stack st;
    Stack minst;
}MinStack, *pMinStack;
void MinStackInit(pMinStack mst);
void MinStackDestory(pMinStack mst);
void MinStackPush(pMinStack mst, DataType x);
void MinStackPop(pMinStack mst);
DataType MinStackTop(pMinStack mst);
int MinStackEmpty(pMinStack mst);
DataType MinStackMin(pMinStack mst);

函数定义（Topic.c）

#include "Topic.h"
void MinStackInit(pMinStack mst)//初始化
{
    assert(mst);
    StackInit(&(mst->st),10);
    StackInit(&(mst->minst), 10);
}
void MinStackPush(pMinStack mst, DataType x)//压栈
{
    assert(mst);
    StackPush(&(mst->st), x);
    if (StackEmpty(&(mst->minst)) == 0 || StackTop(&(mst->minst))>=x)
        StackPush(&(mst->minst), x);
    /*else StackPush(&(mst->minst), StackTop(&(mst->minst)));*/
}
void MinStackPop(pMinStack mst)//出栈
{
    assert(mst);
    DataType x = StackTop(&(mst->st));
    DataType min = StackTop(&(mst->minst));
    StackPop(&(mst->st));
    if (x == min)
        StackPop(&(mst->minst));
}
DataType MinStackTop(pMinStack mst)//返回栈顶元素
{
    assert(mst);
    return StackTop(&(mst->st));
}
DataType MinStackMin(pMinStack mst)//返回最小值
{
    assert(mst);
    return StackTop(&(mst->minst));
}
int MinStackEmpty(pMinStack mst)//判断书否为空
{
    assert(mst);
    return StackEmpty(&(mst->st));
}
void MinStackDestory(pMinStack mst)//销毁
{
    assert(mst);
    StackDestory(&(mst->st));
    StackDestory(&(mst->minst));
}

测试代码

void TestMinStack()
{
    MinStack mst;
    MinStackInit(&mst);
    MinStackPush(&mst, 10);
    MinStackPush(&mst, 5);
    MinStackPush(&mst, 4);
    MinStackPush(&mst, 8);
    MinStackPush(&mst, 0);
    MinStackPush(&mst, 9);
    MinStackPush(&mst, 7);
    while (MinStackEmpty(&mst) != 0)
    {
        DataType top = MinStackTop(&mst);
        DataType min = MinStackMin(&mst);
        printf("Top ：%d Min ：%d\n", top, min);
        MinStackPop(&mst);
    }
    MinStackDestory(&mst);
}

使用两个栈实现一个队列

思路：
    创建两个栈s1、s2，其中一个栈（s1）只管压栈数据，另一个栈（s2）出数据。所以问题就好解决了！需要考虑的就是什么时候从s2出栈。两种情况：
    1.当s2为空栈时，需要将s1的数据全部倒过来，然后出栈s2。
    2.当s2不为空栈时，直接从s2出栈。
    最后从s2出的数据就是满足后进先出（队列）的特性。

函数声明（ QueueByTwoStack.h）

#pragma once
#include "Stack.h"

typedef struct QueueByTwoStack
{
    Stack s1;
    Stack s2;
}QueueByTwoStack, *pQueueByTwoStack;

void QueueByTwoStackInit(pQueueByTwoStack q);
void QueueByTwoStackPush(pQueueByTwoStack q, DataType x);
void QueueByTwoStackPop(pQueueByTwoStack q);
DataType QueueByTwoStackFront(pQueueByTwoStack q);
int QueueByTwoStackEmpty(pQueueByTwoStack q);
void QueueByTwoStackDestory(pQueueByTwoStack q);

函数声明（ QueueByTwoStack.c）

#include "QueueByTwoStack.h"

void QueueByTwoStackInit(pQueueByTwoStack q)//初始化
{
    assert(q);
    StackInit(&(q->s1), 10);
    StackInit(&(q->s2), 10);
}
void QueueByTwoStackPush(pQueueByTwoStack q,DataType x)//压栈
{
    assert(q);
    StackPush(&(q->s1), x);
}

void QueueByTwoStackPop(pQueueByTwoStack q)//出栈
{
    if (StackEmpty(&(q->s2)) == 0)//倒数据
    {
        while (StackEmpty(&(q->s1)))
        {
            StackPush(&(q->s2), StackTop(&(q->s1)));
            StackPop(&(q->s1));
        }
    }
    StackPop(&(q->s2));
}
DataType QueueByTwoStackFront(pQueueByTwoStack q)//队头元素
{
    if (StackEmpty(&(q->s2)) == 0)//倒数据
    {
        while (StackEmpty(&(q->s1)))
        {
            StackPush(&(q->s2), StackTop(&(q->s1)));
            StackPop(&(q->s1));
        }
    }
    return StackTop(&(q->s2));
}

int QueueByTwoStackEmpty(pQueueByTwoStack q)//判断是否为空
{
    return StackEmpty(&(q->s1)) + StackEmpty(&(q->s2));
}
void QueueByTwoStackDestory(pQueueByTwoStack q)//销毁
{
    assert(q);
    StackDestory(&(q->s1));
    StackDestory(&(q->s2));
}

测试代码

void TestQueueByTwoStack()
{
    QueueByTwoStack q;
    QueueByTwoStackInit(&q);
    QueueByTwoStackPush(&q, 1);
    QueueByTwoStackPush(&q, 4);
    QueueByTwoStackPush(&q, 1);
    QueueByTwoStackPush(&q, 7);
    QueueByTwoStackPush(&q, 8);
    QueueByTwoStackPush(&q, 2);
    QueueByTwoStackPush(&q, 6);
    while (QueueByTwoStackEmpty(&q))
    {
        printf("%d ", QueueByTwoStackFront(&q));
        QueueByTwoStackPop(&q);
    }
    printf("\n");
    QueueByTwoStackDestory(&q);

}

使用两个队列实现一个栈

思路：
    创建两个队列q1，q2，在创建两个队列进行操作Empty、NotEmpty。首先让q1指向NotEmpty，q2指向Empty。指定开始时NotEmpty进行压栈，Empty进行出栈。如果不满足此情况时，将Empty、NotEmpty交换，始终保证NotEmpty不为空栈进行压栈，Empty为空栈。
    那么考虑怎么出栈呢？
    首先让NotEmpty将（个数-1）个数据倒到Empty，出栈时将NotEmpty最后一个数据弹出。此时空栈易位，需要进行交换。如果此时需要入栈，则直接在NotEmpty压栈，若出栈继续将数据倒出来。。。如此反复

函数声明（ StackByTwoQueue.h）

#include "Queue.h"

typedef struct StackByTwoQueue
{
    Queue q1;
    Queue q2;
}StackByTwoQueue, *pStackByTwoQueue;

void StackByTwoQueueInit(pStackByTwoQueue s);
void StackByTwoQueuePush(pStackByTwoQueue s, DataType x);
void StackByTwoQueuekPop(pStackByTwoQueue s);
DataType StackByTwoQueueFront(pStackByTwoQueue s);
int StackByTwoQueueEmpty(pStackByTwoQueue s);
void  StackByTwoQueueDestory(pStackByTwoQueue s);

函数声明（ StackByTwoQueue.c）

#include "StackByTwoQueue.h"

void StackByTwoQueueInit(pStackByTwoQueue s)
{
    assert(s);
    QueueInit(&(s->q1));
    QueueInit(&(s->q2));
}
void StackByTwoQueuePush(pStackByTwoQueue s, DataType x)
{
    assert(s);
    pQueue NotEmpty = &(s->q1);
    pQueue Empty = &(s->q2);
    if (!QueueEmpty(&(s->q2)))
    {
        NotEmpty = &(s->q2);
        Empty = &(s->q1);
    }
    QueuePush(NotEmpty, x);
}
void StackByTwoQueuekPop(pStackByTwoQueue s)
{
    assert(s);
    pQueue NotEmpty = &(s->q1);
    pQueue Empty = &(s->q2);
    if (!QueueEmpty(&(s->q2)))
    {
        NotEmpty = &(s->q2);
        Empty = &(s->q1);
    }
    while ((QueueSize(NotEmpty)) > 1)
    {
        QueuePush((Empty), QueueFront(NotEmpty));
        QueuePop(NotEmpty);
    }
    QueuePop(NotEmpty);
}
DataType StackByTwoQueueFront(pStackByTwoQueue s)
{
    assert(s);
    pQueue NotEmpty = &(s->q1);
    pQueue Empty = &(s->q2);
    DataType x = 0;
    if (!QueueEmpty(&(s->q2)))
    {
        NotEmpty = &(s->q2);
        Empty = &(s->q1);
    }
    while ((QueueSize(NotEmpty)) > 1)
    {
        QueuePush((Empty), QueueFront(NotEmpty));
        QueuePop(NotEmpty);
    }
    x = QueueFront(NotEmpty);
    QueuePop(NotEmpty);
    QueuePush(Empty, x);
    return x;
}
int StackByTwoQueueEmpty(pStackByTwoQueue s)
{
    return QueueEmpty(&(s->q1)) && QueueEmpty(&(s->q2));
 }
void  StackByTwoQueueDestory(pStackByTwoQueue s)
{
    assert(s);
    QueueDestory(&(s->q1));
    QueueDestory(&(s->q2));
}

测试代码

void  TestStackByTwoQueue()
{
    StackByTwoQueue s;
    StackByTwoQueueInit(&s);

    StackByTwoQueuePush(&s, 1);
    StackByTwoQueuePush(&s, 3);
    StackByTwoQueuePush(&s, 6);
    StackByTwoQueuePush(&s, 9);
    while (!StackByTwoQueueEmpty(&s))
    {
        printf("%d ", StackByTwoQueueFront(&s));
        StackByTwoQueuekPop(&s);
    }
    printf("\n");
    StackByTwoQueueDestory(&s);
}

元素出栈、入栈顺序的合法性。如入栈的序列（1，2，3，4，5），出栈序列为（4，5，3，2，1）

思路：
    1.入栈和出栈不相等，入栈元素入栈
    2.相等，同时走（数据入了又出来）
    3.当入栈系列到尾，判定

函数声明（IsOrderValib.h）

#pragma once
#include "Stack.h"

int IsOrderValib(int in[], int size_in, int out[], int size_out);

函数实现（IsOrderValib.c）

#include "IsOrderValib.h"
//1.入栈和出栈不相等，入栈元素入栈
//2.相等，同时走（数据入了又出来）
//3.当入栈系列到尾，判定
int IsOrderValib(int in[], int size_in, int out[], int size_out)
{
    Stack s;
    StackInit(&s, 10);
    int inIndex = 0, outIndex = 0;
    if (size_in != size_out)
        return -1;//非法
    while (inIndex < size_in)
    {
        if (in[inIndex] != out[outIndex])
        {
            StackPush(&s, in[inIndex]);
            inIndex++;
        }
        else
        {
            inIndex++;
            outIndex++;
        }
        while (StackEmpty(&s) != 0 && StackTop(&s) == out[outIndex])
        {
            outIndex++;
            StackPop(&s);
        }
    }
    while (outIndex < size_out)
    {
        if (out[outIndex] != StackTop(&s))
            return -1;
        else
        {
            outIndex++;
            StackPop(&s);
        }
    }
    return 0;
}

测试代码

void TestIsOrderValib()
{
    int in[5] = { 1, 2, 3, 4, 5 };
    int out[5] = { 5, 4, 3, 2, 1 };
    printf("%s\n", IsOrderValib(in, 5, out, 5) == 0 ? "合法" : "不合法");
}

一个数组实现两个栈

思路：
    建立一个动态数组，规定偶数位（从0开始）放s1，奇数位（从1开始）放s2。每次方数前进行容量判断，数组不够时进行动态开辟。由于是奇偶放置，所以每放一个数后，下标要向后走两位。

函数声明（TwoStack.h）

#pragma once
#include "Stack.h"

typedef struct TwoStack
{
    DataType *a;
    size_t top1;
    size_t top2;
    size_t capacity;
}TwoStack, *pTwoStack;

void TwoStackInit(pTwoStack s, size_t capacity);
void TwoStackPush(pTwoStack s, DataType x, int which);
void TwoStackPop(pTwoStack s,int which);
int TwoStackSize(pTwoStack s, int which);
int TwoStackEmpty(pTwoStack s, int which);
DataType TwoStackTop(pTwoStack s, int which);
void TwoStackDestory(pTwoStack s);

函数声明（TwoStack.c）

#include "TwoStack.h"

//奇偶数组
void TwoStackInit(pTwoStack s, size_t capacity)
{
    assert(s && capacity > 0);
    s->a = (DataType *)malloc(sizeof(DataType)*capacity);
    assert(s->a);
    s->capacity = capacity;
    s->top1 = 0;
    s->top2 = 1;
}
void TwoStackPush(pTwoStack s, DataType x, int which)
{
    assert(s && (which==1 || which ==2));
    if ((s->top1 == s->capacity ) || (s->top2 == s->capacity +1))
    {
        s->capacity *= 2;
        s->a = (DataType *)realloc(s->a, s->capacity * sizeof(DataType));
        assert(s->a);
    }
    if (which == 1)
    {
        s->a[s->top1] = x;
        s->top1 += 2;
    }
    else
    {
        s->a[s->top2] = x;
        s->top2 += 2;
    }
}
void TwoStackPop(pTwoStack s, int which)
{
    assert(s && (which == 1 || which == 2));
    if (which == 1)
        s->top1 -= 2;
    else
        s->top2 -= 2;
}
int TwoStackSize(pTwoStack s, int which)
{
    assert(s && (which == 1 || which == 2));
    if (which == 1)
        return s->top1 / 2;
    else
        return s->top2 / 2;
}
int TwoStackEmpty(pTwoStack s, int which)
{
    assert(s && (which == 1 || which == 2));
    if (which == 1)
        return s->top1 / 2 == 0 ? 1 : 0;
    else
        return s->top2 / 2 == 0 ? 1 : 0;
}
DataType TwoStackTop(pTwoStack s, int which)
{
    assert(s && (which == 1 || which == 2));
    if (which == 1)
        return s->a[s->top1 - 2];
    else
        return s->a[s->top2 - 2];
}
void TwoStackDestory(pTwoStack s)
{
    assert(s);
    free(s->a);
    s->a = NULL;
    s->top1 = s->top2 = s->capacity = 0;
}

测试代码

void TestTwoStack()
{
    TwoStack s;
    TwoStackInit(&s, 4);
    TwoStackPush(&s, 1, 1);
    TwoStackPush(&s, 3, 2);
    TwoStackPush(&s, 2, 1);
    TwoStackPush(&s, 4, 2);
    TwoStackPush(&s, 5, 1);
    TwoStackPush(&s, 6, 2);
    TwoStackPush(&s, 7, 1);
    TwoStackPush(&s, 4, 2);
    TwoStackPush(&s, 9, 2);
    TwoStackPush(&s, 5, 1);
    printf("容量capacity= %d\n", s.capacity);
    while (!TwoStackEmpty(&s, 1))
    {
        printf("%d ", TwoStackTop(&s, 1));
        TwoStackPop(&s, 1);
    }
    printf("\n");
    while (!TwoStackEmpty(&s, 2))
    {
        printf("%d ", TwoStackTop(&s, 2));
        TwoStackPop(&s, 2);
    }
    printf("\n");
}