您的位置: 首页  >  文章  >  栈和队列面试题

栈和队列面试题

分类: 文章 • 2024-06-09 12:44:46

栈和队列面试题：

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");
}

两个栈实现一个队列：

栈和队列面试题

/////////////////////////////////////////////////////////////////////////////////
//两个栈实现一个队列
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);
}

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

栈和队列面试题

////////////////////////////////////////////////////////////////////////////////
//两个队列实现一个栈
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)：

栈和队列面试题

/////////////////////////////////////////////////////////////////////////////////
//实现一个栈，要求实现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");
    }
}

 

相关推荐