栈和队列面试题

港控/mmm° 2022-05-09 12:36 174阅读 0赞

## **栈和队列面试题：** ##

**Qands.h：**

#pragma once
    #include<stdio.h>
    #include<assert.h>
    #include<malloc.h>
    #include<stdlib.h>
    #define N 5
    ///
    // 栈的实现
    ///
    typedef int DataType;
    typedef struct Stack
    {
        DataType* _array;
        DataType _top; //栈顶
        int _capacity;
    }Stack;
     栈的实现接口
    void StackInit(Stack* ps);
    void StackPush(Stack* ps, DataType x);
    void StackPop(Stack* ps);
    void StackPrint(Stack s);
    DataType StackTop(Stack* ps);
    int StackSize(Stack* ps);
    int StackEmpty(Stack* ps);
    void StackDestory(Stack *s);
    
    //队列的实现
    
    typedef struct QueueNode
    {
        DataType _data;
        struct QueueNode* _next;
    }QueueNode;
    typedef struct Queue
    {
        QueueNode* _head;
        QueueNode* _tail;
    }Queue;
    队列的实现接口
    void QueueInit(Queue* q);
    void QueuePush(Queue* q, DataType x);
    void QueuePop(Queue* q);
    DataType QueueFront(Queue* q);
    DataType QueueBack(Queue* q);
    int QueueSize(Queue* q);
    int QueueEmpty(Queue* q);
    void QueueDestory(Queue *q);
    void QueuePrint(Queue *q);
    
    //两个栈实现一个队列
    
    typedef struct QueueByTwoStack
    {
        Stack s1;
        Stack s2;
    }QueueByTwoStack;
    两个栈实现一个队列的接口
    void QueueByTwoStackInit(QueueByTwoStack *qts);
    void QueueByTwoStackDestory(QueueByTwoStack *qts);
    void QueueByTwoStackPush(QueueByTwoStack *qts, DataType x);
    void QueueByTwoStackPop(QueueByTwoStack *qts);
    DataType QueueByTwoStackFront(QueueByTwoStack *qts);
    int QueueByTwoStackSize(QueueByTwoStack *qts);
    int QueueByTwoStackEmpty(QueueByTwoStack *qts);
    ///
    //两个队列实现一个栈
    ///
    typedef struct StackByTwoQueue
    {
        Queue q1;
        Queue q2;
    }StackByTwoQueue;
    两个队列实现一个栈的接口
    void StackByTwoQueueInit(StackByTwoQueue *stq);
    void StackByTwoQueueDestory(StackByTwoQueue *stq);
    void StackByTwoQueuePush(StackByTwoQueue *stq, DataType x);
    void StackByTwoQueuePop(StackByTwoQueue *stq);
    DataType StackByTwoQueueTop(StackByTwoQueue *stq);
    int StackByTwoQueueSize(StackByTwoQueue *stq);
    int StackByTwoQueueEmpty(StackByTwoQueue *stq);
    ///
    //实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1)
    ///
    typedef struct MinStack
    {
        Stack st;
        Stack minst;
    }MinStack;
    MinStack的实现接口
    void MinStackInit(MinStack *pms);
    void MinStackDestory(MinStack *pms);
    void MinStackPush(MinStack *pms, DataType x);
    void MinStackPop(MinStack *pms);
    int MinStackMin(MinStack *pms);
    //
    //元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5)，出栈序列为(4, 5, 3, 2, 1)
    //元素出栈、入栈顺序的合法性的实现接口
    //
    int IsLegalStackOrder(int *in, int insize, int *out, int outsize);
    /
    //一个数组实现两个栈(共享栈)
    /
    #define M 100
    typedef struct ShareStack
    {
        DataType a[M];
        int top1;
        int top2;
    }ShareStack;
    一个数组实现两个栈(共享栈)的实现接口
    void ShareStackInit(ShareStack *pms);
    void ShareStackDestory(ShareStack *pms);
    void ShareStackPush(ShareStack *pms, int x, int which);
    void ShareStackPop(ShareStack *pms, int which);
    void ShareStackPrint(ShareStack *pms);

实现一个栈：

///
    // 栈的实现
    void StackInit(Stack * ps)
    {
        assert(ps);
        (DataType *)ps->_array = (DataType *)malloc(sizeof(DataType)* 5);
        if (ps->_array == NULL)
        {
            perror("malloc error:");
            exit(0);
        }
        ps->_top = 0;
        ps->_capacity = 5;
    }
    
    void StackDestory(Stack * ps)
    {
        assert(ps);
        ps->_capacity = 0;
        ps->_top = 0;
        free(ps->_array);
        ps->_array = NULL;
    }
    
    void StackPush(Stack* ps, DataType x)
    {
        assert(ps);
        if ((ps->_top) == ps->_capacity)
        {
            ps->_array = (DataType*)realloc(ps->_array, sizeof(DataType)* 5 * 2);
            if (ps->_array == NULL)
            {
                perror("malloc error:");
                exit(0);
            }
            ps->_top = ps->_capacity;
            ps->_capacity += 5;
        }
        ps->_array[(DataType)ps->_top] = x;
        ps->_top++;
    }
    
    void StackPop(Stack* ps)
    {
        assert(ps&&ps->_array);
        if (ps->_top == 0)
        {
            return;
        }
        ps->_array[ps->_top] = NULL;
        ps->_top--;
    }
    
    DataType StackTop(Stack* ps)
    {
        assert(ps);
        return ps->_array[ps->_top - 1];
    }
    
    int StackSize(Stack* ps)
    {
        assert(ps);
        return ps->_top;
    }
    
    int StackEmpty(Stack* ps)
    {
        assert(ps);
        int flag = 0;
        if (ps->_top == 0)
            flag = 0;
        else flag = 1;
        return flag;
    }
    
    void StackPrint(Stack s)
    {
        int i = 0;
        for (i = 0; i < s._top; i++)
        {
            printf("%d ", s._array[i]);
        }
        printf("\n");
    }

实现一个队列：

//
    //队列的实现
    void QueueInit(Queue* q)
    {
        assert(q);
        q->_head = NULL;
        q->_tail = NULL;
    }
    
    void QueuePush(Queue* q, DataType x)
    {
        assert(q);
        QueueNode *qNode = NULL;
        qNode = (QueueNode*)malloc(sizeof(QueueNode));
        assert(qNode);
        qNode->_data = x;
        qNode->_next = NULL;
        if (q->_head == NULL)//栈为空
        {
            q->_head = qNode;
            q->_tail = qNode;
        }
        else//栈不为空
        {
            q->_tail->_next = qNode;
            q->_tail = qNode;
        }
    }
    
    void QueuePop(Queue* q)
    {
        assert(q);
        if (q->_head == NULL)
        {
            return;
        }
        q->_head = q->_head->_next;
    }
    
    DataType QueueFront(Queue* q)
    {
        assert(q && q->_head);
        return q->_head->_data;
    }
    
    DataType QueueBack(Queue* q)
    {
        assert(q);
        return q->_tail->_data;
    }
    
    int QueueSize(Queue* q)
    {
        assert(q);
        QueueNode *tmp = q->_head;
        DataType i = 0;
        while (tmp)
        {
            i++;
            tmp = tmp->_next;
        }
        return i;
    }
    
    int QueueEmpty(Queue* q)
    {
        assert(q);
        return q->_head == NULL ? 0 : 1;
    }
    
    void QueueDestory(Queue *q)
    {
        assert(q);
        QueueNode *tmp = q->_head;
        while (q->_head)
        {
            tmp = q->_head;
            q->_head = q->_head->_next;
            free(tmp);
            tmp = NULL;
        }
    }
    
    void QueuePrint(Queue *q)
    {
        QueueNode *tmp = q->_head;
        while (tmp)
        {
            printf("%d ", tmp->_data);
            tmp = tmp->_next;
        }
        printf("\n");
    }

两个栈实现一个队列：

![70][]

/
    //两个栈实现一个队列
    void QueueByTwoStackInit(QueueByTwoStack *qts)
    {
        assert(qts);
        StackInit(&qts->s1);
        StackInit(&qts->s2);
    }
    
    void QueueByTwoStackDestory(QueueByTwoStack *qts)
    {
        assert(qts);
        StackDestory(&qts->s1);
        StackDestory(&qts->s2);
    }
    
    void QueueByTwoStackPush(QueueByTwoStack *qts, DataType x)
    {
        assert(qts);
        StackPush(&qts->s1, x);
    }
    
    void QueueByTwoStackPop(QueueByTwoStack *qts)
    {
        assert(qts);
        if (StackEmpty(&qts->s2) == 0)
        {
            while (StackEmpty(&qts->s1))
            {
                StackPush(&qts->s2, StackTop(&qts->s1));
                StackPop(&qts->s1);
            }
        }
        StackPop(&qts->s2);
    }
    
    DataType QueueByTwoStackFront(QueueByTwoStack *qts)
    {
        assert(qts);
        if (StackEmpty(&qts->s2) == 0)
        {
            while (StackEmpty(&qts->s1))
            {
                StackPush(&qts->s2, StackTop(&qts->s1));
                StackPop(&qts->s1);
            }
        }
        return StackTop(&qts->s2);
    }
    
    int QueueByTwoStackSize(QueueByTwoStack *qts)
    {
        assert(qts);
        return StackSize(&qts->s1) + StackSize(&qts->s2);
    }
    
    int QueueByTwoStackEmpty(QueueByTwoStack *qts)
    {
        assert(qts);
        return StackSize(&qts->s1) | StackSize(&qts->s2);
    }

使用两个队列实现一个栈：

![70 1][]

//两个队列实现一个栈
    void StackByTwoQueueInit(StackByTwoQueue *stq)
    {
        assert(stq);
        QueueInit(&stq->q1);
        QueueInit(&stq->q2);
    }
    
    void StackByTwoQueueDestory(StackByTwoQueue *stq)
    {
        assert(stq);
        QueueDestory(&stq->q1);
        QueueDestory(&stq->q2);
    }
    
    void StackByTwoQueuePush(StackByTwoQueue *stq, DataType x)
    {
        assert(stq);
        if (QueueEmpty(&stq->q1))
            QueuePush(&stq->q1, x);
        else QueuePush(&stq->q2, x);
    }
    
    void StackByTwoQueuePop(StackByTwoQueue *stq)
    {
        assert(stq);
        Queue *empty = &stq->q1;
        Queue *nonempty = &stq->q2;
        if (QueueEmpty(&stq->q1))
        {
            empty = &stq->q2;
            nonempty = &stq->q1;
        }
        while (QueueSize(nonempty) > 1)
        {
            QueuePush(empty, QueueFront(nonempty));
            QueuePop(nonempty);
        }
        QueuePop(nonempty);
    }
    
    DataType StackByTwoQueueTop(StackByTwoQueue *stq)
    {
        assert(stq);
        if (QueueEmpty(&stq->q1))
            QueueBack(&stq->q1);
        else QueueBack(&stq->q2);
    }
    
    int StackByTwoQueueSize(StackByTwoQueue *stq)
    {
        assert(stq);
        return QueueSize(&stq->q1) + QueueSize(&stq->q2);
    }
    
    int StackByTwoQueueEmpty(StackByTwoQueue *stq)
    {
        assert(stq);
        return QueueSize(&stq->q1) | QueueSize(&stq->q2);
    }

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

![70 2][]

/
    //实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1)
    void MinStackInit(MinStack *pms)
    {
        assert(pms);
        StackInit(&pms->st);
        StackInit(&pms->minst);
    }
    
    void MinStackDestory(MinStack *pms)
    {
        assert(pms);
        StackDestory(&pms->st);
        StackDestory(&pms->minst);
    }
    
    void MinStackPush(MinStack *pms, DataType x)
    {
        assert(pms);
        StackPush(&pms->st, x);
        if (StackEmpty(&pms->minst) == 0 || StackTop(&pms->minst) >= x)
            StackPush(&pms->minst, x);
    }
    
    void MinStackPop(MinStack *pms)
    {
        assert(pms);
        if (StackTop(&pms->st) == StackTop(&pms->minst))
            StackPop(&pms->minst);
        StackPop(&pms->st);
    }
    
    int MinStackMin(MinStack *pms)
    {
        assert(pms);
        return StackTop(&pms->minst);
    }

元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5)，出栈序列为 (4,5,3,2,1)：

/
    //元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5)，出栈序列为(4, 5, 3, 2, 1)
    int IsLegalStackOrder(int *in, int insize, int *out, int outsize)
    {
        assert(in&&out);
        Stack st;
        StackInit(&st);
        int inindex = 0;
        int outindex = 0;
        while (inindex<outindex)
        {
            StackPush(&st, in[inindex]);
            ++inindex;
            while (StackEmpty(&st)){
                if (StackTop(&st) == out[outindex])
                {
                    StackPop(&st);
                    ++outindex;
                }
            }
        }
        if (StackEmpty(&st) == 0)
        {
            StackDestory(&st);
            return 1;
        }
        else if (StackEmpty(&st) != 0)
        {
            StackDestory(&st);
            return 0;
        }
    }

一个数组实现两个栈(共享栈)：

/
    //一个数组实现两个栈(共享栈)
    void ShareStackInit(ShareStack *pms)
    {
        assert(pms);
        pms->top1 = 0;
        pms->top2 = 1;
    }
    
    void ShareStackDestory(ShareStack *pms)
    {
        assert(pms);
        pms->top1 = 0;
        pms->top2 = 0;
    }
    
    void ShareStackPush(ShareStack *pms,int x,int which)
    {
        assert(pms);
        if (which==1)
        {
            if (pms->top1 >= M)
            {
                printf("stack1已满！\n");
                return;
            }
            pms->a[pms->top1] = x;
            pms->top1 += 2;
        }
        else if (which == 2)
        {
            if (pms->top2 >= M)
            {
                printf("stack2已满！\n");
                return;
            }
            pms->a[pms->top2] = x;
            pms->top2 += 2;
        }
    }
    
    void ShareStackPop(ShareStack *pms,int which)
    {
        assert(pms&&pms->top1>0&&pms->top2>1);
        if (which == 1)
        {
            pms->top1 = pms->top1 - 2;
        }
        else if (which == 2)
        {
            pms->top2 = pms->top2 - 2;
        }
    }
    
    void ShareStackPrint(ShareStack *pms)
    {
        assert(pms);
        int i = 0;
        if (pms->top1 > pms->top2)
        {
            for (i = 0; i < pms->top1-1; i++)
            {
                printf("%d ", pms->a[i]);
            }
            printf("\n");
        }
        else if (pms->top1 < pms->top2)
        {
            for (i = 0; i < pms->top2-1; i++)
            {
                printf("%d ", pms->a[i]);
            }
            printf("\n");
        }
    }

[70]: /images/20220509/98396a87b20b49ffa4101898acb1b777.png
[70 1]: /images/20220509/b6f79f37c2c147cabfaf239a34d01367.png
[70 2]: /images/20220509/d00a813c1ddb4d529026c0a73505cbe5.png