跳转至

栈和队列

栈和队列的定义和特点

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含元素的空表称为空栈。栈又称为后进先出（Last In First Out，LIFO）的线性表。

队列是一种先进先出（First In First Out，FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一段称为队尾（rear），允许删除的一端则称为队头（front）。

栈的表示和操作的实现

顺序栈的表示和实现

算法示例

  • 顺序栈的初始化 

    #define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 1000

typedef int Status;

typedef struct stack
{
    int* bottom;
    int* top;
    int stack_size;
}Sqstack;

/* 顺序栈初始化 */
Status InitStack(Sqstack* stack)
{
    stack->bottom = malloc(sizeof(int) * MAXSIZE);
    if (stack->bottom == NULL)
    {
        return ERROR;
    }
    stack->top = stack->bottom;
    stack->stack_size = MAXSIZE;
    return OK;
}

  • 顺序栈的入栈 

    /* 顺序栈入栈 */
Status Push(Sqstack* stack, int e)
{
    if (stack->top - stack->bottom == stack->stack_size)
    {
        return ERROR;
    }

    *(stack->top) = e; // 先赋值
    stack->top += 1; // 再++

    return OK;
}

  • 顺序栈的出栈 

    /* 顺序栈出栈 */
Status Pop(Sqstack* stack, int* e)
{
    if (stack->top == stack->bottom)
    {
        return ERROR;
    }

    stack->top -= 1; // 先--
    *e = *(stack->top); // 再赋值

    return OK;
}

链栈的表示和实现

算法示例

  • 链栈的初始化 

    #define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;

typedef struct StackNode
{
    int data;
    struct StackNode* next;
}StackNode, * LinkStack;

/* 链栈初始化 */
Status InitStack(LinkStack* stack)
{
    *stack = NULL;
    return OK;
}

  • 链栈的入栈 

    /* 链栈的入栈 */
Status Push(LinkStack* stack, int e)
{
    StackNode* node = malloc(sizeof(StackNode));
    node->data = e;
    node->next = (*stack);

    *stack = node;

    return OK;
}

  • 链栈的出栈 

    /* 链栈的出栈 */
Status Pop(LinkStack* stack, int* e)
{
    if ((*stack) == NULL)
    {
        return ERROR;
    }

    StackNode* node = *stack;
    *e = node->data;

    *stack = node->next;
    free(node);

    return OK;
}

栈与递归

算法示例

  • 遍历输出链表中各个节点的递归算法 

    void TraverseList(LinkList p)
{
    if (p == NULL)
    {
        return;
    }
    printf("%d\n", p->data);
    TraverseList(p->next);
}

  • Hanoi塔问题的递归算法 

    /* A -> C, 经过B */
void Hanoi(int n, char A, char B, char C)
{
    if (n == 1)
    {
        printf("%c -> %c\n", A, C);
        return;
    }

    Hanoi(n - 1, A, C, B);
    printf("%c -> %c\n", A, C);
    Hanoi(n - 1, B, A, C);
}

递归算法的效率分析

  • 时间复杂度分析
  • 空间复杂度分析

队列的表示和操作实现

队列的类型定义

循环队列 - 队列的顺序表示和实现

循环队列实现时：

  • 队空条件：q->front == q->rear
  • 队满条件：(q->rear + 1) % MAXQSIZE == q.front

算法示例

  • 循环队列的初始化 
    /* 状态 */
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXQSIZE 100

typedef int Status;

typedef struct
{
    int* base;
    int front;
    int rear;

}SqQueue;

/* 循环队列的初始化 */
Status InitQueue(SqQueue* q)
{
    q->base = malloc(sizeof(int) * MAXQSIZE);
    if (q->base == NULL)
    {
        return OVERFLOW;
    }
    q->front = 0;
    q->rear = 0;
    return OK;
}

  • 求循环队列的长度 

    /* 求队列长度 */
int QueueLength(SqQueue* q)
{
    return (q->rear - q->front + MAXQSIZE) % MAXQSIZE;
}

  • 循环队列的入队 

    /* 循环队列入队 */
Status EnQueue(SqQueue* q, int e)
{
    if ((q->rear + 1) % MAXQSIZE == q->front)
    {
        return ERROR;
    }
    *(q->base + q->rear) = e;
    q->rear = (q->rear + 1) % MAXQSIZE;
    return OK;
}

  • 循环队列的出队 

    /* 循环队列出队 */
Status DeQueue(SqQueue* q, int* e)
{
    if (q->front == q->rear)
    {
        return ERROR;
    }

    *e = *(q->base + q->front);
    q->front = (q->front + 1) % MAXQSIZE;
    return OK;
}

链队 - 队列的链式表示和实现

  • 当前为带头结点的链队。当最后一个结点出队时，要将q->rear指回头结点，头结点next重新修改为NULL。

算法示例

  • 链队的初始化 

    /* 状态 */
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;

typedef struct QNode
{
    int data;
    struct QNode* next;
}QNode, *QNodeLink;

typedef struct
{
    QNodeLink front;
    QNodeLink rear;
}LinkQueue;

/* 创建带头结点的链队 */
Status InitQueue(LinkQueue* q)
{
    /* 此node为头结点 */
    QNodeLink node = malloc(sizeof(QNode));
    if (node == NULL)
    {
        return ERROR;
    }
    node->next = NULL;

    q->front = node;
    q->rear = node;

    return OK;
}

  • 链队的入队 

    /* 入队 */
Status EnQueue(LinkQueue* q, int e)
{
    QNodeLink node = malloc(sizeof(QNode));
    node->data = e;
    node->next = NULL;

    q->rear->next = node;
    q->rear = node;

    return OK;
}

  • 链队的出队 

    /* 出队 */
Status DeQueue(LinkQueue* q, int* e)
{
    QNodeLink node = NULL;

    if (q->front == q->rear)
    {
        return ERROR;
    }

    node = q->front->next;
    *e = node->data;

    q->front->next = node->next;

    if (node == q->rear)
    {
        q->rear = q->front;
        q->rear->next = NULL;
    }
    free(node);

    return OK;
}

案例分析与实现

算法示例

  • 数制的转换 

    /* 利用栈进行十进制转八进制 */
void conversion(int n)
{
    Sqstack s;
    int e = 0;

    InitStack(&s);

    while (n != 0)
    {
        Push(&s, n % 8);
        n /= 8;
    }

    while (Pop(&s, &e))
    {
        printf("%d", e);
    }
    return;
}

  • 括号的匹配 

    /* 括号匹配。全部匹配返回true，否则返回false */
/*
    [  (  [  ]  [  ]  )  ]
    1  2  3  4  5  6  7  8
*/
bool Matching(char* str, int size)
{
    Sqstack s;
    int c = 0, i = 0;
    bool flag = false;

    InitStack(&s);

    for (i = 0; i < size; i += 1)
    {
        if (str[i] == '[' || str[i] == '(')
        {
            Push(&s, str[i]);
        }
        else
        {
            GetTop(&s, &c);
            if (str[i] == ']' && c == '[')
            {
                Pop(&s, &c);
            }
            else if (str[i] == ')' || c == '(')
            {
                Pop(&s, &c);
            }
            else
            {
                Push(&s, str[i]);
            }
            c = 0;
        }
    }

    if (s.top == s.bottom)
    {
        flag = true;
    }

    free(s.bottom);

    return flag;
}

  • 表达式求值 

    /* 计算包含数字、操作符（+、-、*、/、括号）的数学表达式。利用顺序栈实现。 */

/* 合并数字 */
int GetNumber(int* num, int size)
{
    int number = 0;
    int i = 0;

    number = 0;
    for (i = 0; i < size; i += 1)
    {
        number += num[i] * pow(10, size - i - 1);
    }
    return number;
}

/* 计算 */
int Calculate(int a, int b, char optr)
{
    if (optr == '+')
    {
        return a + b;
    }
    if (optr == '-')
    {
        return a - b;
    }
    if (optr == '*')
    {
        return a * b;
    }
    if (optr == '/')
    {
        return a / b;
    }
}

/* 获取操作符下标 */
int GetOperatorIndex(char c)
{
    char opt[8] = { '+', '-', ',', '*', '/', ',', '(', ')' };
    int i = 0;

    for (i = 0; i < 8; i += 1)
    {
        if (opt[i] == c)
        {
            return i;
        }
    }

    return -1;
}

/* 比较优先级 */
char Precode(char left, char right)
{
    int a = GetOperatorIndex(left);
    int b = GetOperatorIndex(right);

    if (left == '(' && right == ')')
    {
        return '=';
    }

    if (left == '(' && right != ')')
    {
        return '<';
    }

    if (left != '(' && right == ')')
    {
        return '>';
    }

    if (abs(a - b) == 1 || a == b)
    {
        return '>';
    }

    if (a > b)
    {
        return '>';
    }

    return '<';
}

/* 数字检查 */
void CheckNumberAndPush(Sqstack* OPTR, Sqstack* OPND, int n)
{
    int optr = '\0';

    if (IsEmpty(OPTR))
    {
        Push(OPND, n);
        return;
    }

    /* 将左侧为负号的数字转为正号以及相反数 */
    GetTop(OPTR, &optr);
    if (n < 0 && optr == '-')
    {
        Pop(OPTR, &optr);
        Push(OPTR, '+');
        n *= -1;
    }
    else if (n > 0 && optr == '-')
    {
        Pop(OPTR, &optr);
        Push(OPTR, '+');
        n *= -1;
    }
    Push(OPND, n);
    return;
}


/* 计算表达式的值 */
/*
    6-10+8*12-100+2                     -6
    1996/2*3+5-27                       2972
    (2+3)*5                             25
    3+5*2-(5+1-10)*7-((4-2)+3)          36
    3+2+(5-3)*6-12*5+(5+(4+3))          -31
    1+2-3-100*2+36-(4+2)-9*9            -251
    (1+(2-3)-100)*2+36-(4+2)-9*9        -251
*/
int EvaluateExpression(char* str, int size)
{
    Sqstack OPND, OPTR;
    int i = 0;
    int optr = '\0';
    char res = '\0';
    int a = 0, b = 0;
    int ans = 0;

    int num[100] = { 0 };
    int num_cnt = 0;
    int number = 0;

    InitStack(&OPND);
    InitStack(&OPTR);

    for (i = 0; i < size; i += 1)
    {
        /* 数字 */
        if (GetOperatorIndex(str[i]) == -1)
        {
            num[num_cnt] = str[i] - '0';
            num_cnt += 1;
            continue;
        }

        /* 数字合并 */
        if (num_cnt != 0)
        {
            number = GetNumber(num, num_cnt);
            CheckNumberAndPush(&OPTR, &OPND, number);
            num_cnt = 0;
        }

        /* 第一个操作符 */
        if (IsEmpty(&OPTR))
        {
            Push(&OPTR, str[i]);
            continue;
        }

        GetTop(&OPTR, &optr);
        res = Precode(optr, str[i]);

        if (res == '<')
        {
            Push(&OPTR, str[i]);
            continue;
        }

        if (res == '>')
        {
            Pop(&OPND, &b);
            Pop(&OPND, &a);
            Pop(&OPTR, &optr);
            CheckNumberAndPush(&OPTR, &OPND, Calculate(a, b, optr));
        }

        GetTop(&OPTR, &optr);
        res = Precode(optr, str[i]);
        if (res == '=')
        {
            Pop(&OPTR, &optr);
            continue;
        }
        Push(&OPTR, str[i]);
    }

    /* 最后一个数字 */
    if (num_cnt != 0)
    {
        number = GetNumber(num, num_cnt);
        CheckNumberAndPush(&OPTR, &OPND, number);
        num_cnt = 0;
    }

    /* 弹栈计算 */
    while (IsEmpty(&OPTR) == false)
    {
        Pop(&OPND, &b);
        Pop(&OPND, &a);
        Pop(&OPTR, &optr);

        CheckNumberAndPush(&OPTR, &OPND, Calculate(a, b, optr));
    }

    Pop(&OPND, &ans);

    return ans;
}

int main(void)
{
    //char str[] = "6-10+8*12-100+2";
    //char str[] = "1996/2*3+5-27";
    //char str[] = "(2+3)*5";
    //char str[] = "3+5*2-(5+1-10)*7-((4-2)+3)";
    //char str[] = "3+2+(5-3)*6-12*5+(5+(4+3))";
    char str[] = "(1+(2-3)-100)*2+36-(4+2)-9*9";

    int ans = 0;

    ans = EvaluateExpression(str, sizeof(str) - 1);
    printf("%s = %d\n", str, ans);

    return 0;
}

  • 舞伴问题 

    /* 用循环队列简单实现 */

/* 状态 */
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXQSIZE 100
#define SIZE 50
typedef int Status;

typedef struct data
{
    char name[SIZE];
} DataType;

typedef struct
{
    DataType* base;
    int front;
    int rear;

}SqQueue;

/* 循环队列的初始化 */
Status InitQueue(SqQueue* q)
{
    q->base = malloc(sizeof(DataType) * MAXQSIZE);
    if (q->base == NULL)
    {
        return OVERFLOW;
    }
    q->front = 0;
    q->rear = 0;
    return OK;
}

/* 循环队列入队 */
Status EnQueue(SqQueue* q, DataType e)
{
    if ((q->rear + 1) % MAXQSIZE == q->front)
    {
        return ERROR;
    }
    *(q->base + q->rear) = e;
    q->rear = (q->rear + 1) % MAXQSIZE;
    return OK;
}

/* 循环队列出队 */
Status DeQueue(SqQueue* q, DataType* e)
{
    if (q->front == q->rear)
    {
        return ERROR;
    }

    *e = *(q->base + q->front);
    q->front = (q->front + 1) % MAXQSIZE;
    return OK;
}

void DancePartner(SqQueue* Mdancers, SqQueue* Fdancers)
{
    DataType Mda, Fda;
    for (int i = 0; i < 30; i += 1)
    {
        DeQueue(Mdancers, &Mda);
        DeQueue(Fdancers, &Fda);
        printf("第%d组：%s 和 %s.\t", i + 1, Mda.name, Fda.name);
        EnQueue(Mdancers, Mda);
        EnQueue(Fdancers, Fda);
    }
}