队列和栈

从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集

栈和队列的比较

	栈	队列
逻辑结构	和线性表一样，数据元素之间存在一对一的关系	和线性表一样，数据元素之间存在一对一的关系
存储结构	顺序存储: 存储空间预先分配，可能会导致空间闲置或者栈满溢出现现象 数据元素个数不能自由扩充	顺序存储（常设计成循环队列）： 存储空间预先分配，可能会导致空间闲置或者队列溢出现象 数据元素个数不能自由扩充
	链式存储： 动态分配，不会出现闲置或者栈满溢出现象 数据元素个数可以自由扩充	链式存储： 动态分配，不会出现闲置或者队列溢出现象 数据元素个数可以自由扩充
运算规则	插入和删除在表的一端（栈顶）完成，后进先出	插入运算在表的一端（队尾）进行，删除在表的另一端（队头），先进先出

栈

限定仅在表尾进行插入或者删除操作的线性表，栈的修改按照先进后出的原则

顺序栈

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100
typedef struct SqStack
{
    int *data;
    int top;  // 栈顶指针
}SqStack;

// InitStack 初始化顺序栈
int InitStack(SqStack *s) {
    s->top = -1;
    s->data =  (int *)malloc(sizeof(int)*MAXSIZE);;
    return 0;
}

// Push 入栈
// 1. 判断栈是否满,若满则返回-1
// 2. 将新元素压入栈顶,栈顶指针加1
int Push(SqStack *s, int e) {
    // 栈满
    if (s->top == MAXSIZE-1) {
        return -1;
    }
    s->data[++s->top] = e;
    return 0;
}

// Pop 出栈
// 1. 判断栈是否为空,若空则返回-1
// 2. 栈顶指针减1,栈顶元素出栈
int Pop(SqStack *s, int *e) {
    if (s->top == -1) {
        return -1;
    }
    e = &s->data[s->top--];
    return 0;
}

// GetTop 取栈顶元素
int GetTop(SqStack *s) {
    if (s->top !=-1) {
        return s->data[s->top];
    }
    return 0;
}

链栈

#include<stdio.h>
#include<stdlib.h>

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

// InitStack 初始化链栈
int InitStack(LinkStack s) {
    s = NULL;
    return 0;
}

// Push 入栈
// 1. 为入栈元素分配空间,用指针p指向
// 2. 将新节点数据域置为e
// 3. 将新节点插入栈顶
// 4. 修改栈顶指针为p
LinkStack Push(LinkStack s, int e) {
    LinkStack p = (LinkStack)malloc(sizeof(StackNode));
    p->data = e;
    p->next = s;
    s = p;
    return s;
}

// Pop 出栈
// 1. 判断栈是否为空,若空则返回-1
// 2. 将栈顶元素赋给e
// 3. 临时保存栈顶元素的地址,以备释放
// 4. 修改栈顶指针,指向新的栈顶元素
// 5. 释放原栈顶元素的地址
LinkStack Pop(LinkStack s, int *e) {
    if (s == NULL) {
        return s;
    }
    *e = s->data;
    LinkStack p = s;
    s = s->next;
    free(p);
    return s;
}

// GetTop 取栈顶元素
int GetTop(LinkStack s) {
    if (s != NULL) {
        return s->data;
    }
    return 0;
}

队列

一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素

循环队列

#include<stdio.h>
#include<stdlib.h>

#define MaxQSize 100
typedef struct {
    int *base; // 存储空间基地址
    int front; // 头结点
    int rear;  // 尾结点
}SqQueue;

// InitQueue 初始化循环队列
void InitQueue(SqQueue *q)
{
    q->base = (int *)malloc(sizeof(int)*MaxQSize);
    q->front = q->rear = 0;
}

// QueueLenth 队列长度
int QueueLenth(SqQueue q) {
    return (q.rear - q.front + MaxQSize) % MaxQSize;
}

// Push 入队
// 1、判断队列是否满
// 2、将新元素插入队尾
// 3、队尾指针加1
int Push(SqQueue *q, int e)
{
    // 队满
    if ((q->rear+1)%MaxQSize == q->front) {
        return -1;
    }

    q->base[q->rear] = e;
    q->rear = (q->rear + 1) % MaxQSize;
    return 0;
}

// Pop 出队
// 1、判断队列是否为空
// 2、保存队头元素
// 3、队头指针加1
int Pop(SqQueue *q, int *e)
{
    // 队空
    if (q->rear == q->front) {
        return -1;
    }
    *e = q->base[q->front];
    q->front = (q->front + 1) % MaxQSize;
    return 0;
}

// GetTop 取队头元素
int GetTop(SqQueue *q, int *e)
{
    if (q->front == q->rear) {
        return -1;
    }
    *e = q->base[q->front];
    return 0;
}

链队

链队是指采用链式存储结构实现的队列。通常链队用单链表表示。一个链队显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。

#include<stdio.h>
#include<stdlib.h>

typedef struct QNode QNode;
typedef struct QNode* QPtr;

struct QNode
{
    int data;
    struct QNode* next;
};

typedef struct LinkQueue LinkQueue;
struct LinkQueue
{
    QPtr front; // 队头指针
    QPtr rear;  // 队尾指针
};

// InitQueue 链队初始化
// 1、生成新结点，队头和队尾都指向此结点
// 2、头结点的指针域置为空
void InitQueue(LinkQueue *q)
{
    QPtr node = (QPtr)malloc(sizeof(QNode));
    node->next = NULL;
    q->front = node;
    q->rear = node;
}

// EnQueue 元素入队
// 1、为入队元素分配结点空间，用指针p指向
// 2、将新结点数据域置为e
// 3、将新结点插入到队尾
// 4、修改队尾指针为p
void EnQueue(LinkQueue *q, int e)
{
    QPtr p = (QPtr)malloc(sizeof(QNode));
    p->data = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

// DeQueue 元素出队
// 1、判断队列是否为空，若空则返回-1
// 2、临时保存队头元素的空间，以备释放
// 3、修改头结点的指针域，指向下一个结点
// 4、判断出队是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点
// 5、释放原队头元素的空间
void DeQueue(LinkQueue *q, int *e)
{
    if (q->rear == q->front)
    {
        return;
    }
    QPtr p = q->front->next;
    *e = p->data;
    q->front->next = p->next;
    if (q->rear == p)
    {
        q->rear = q->front;
    }
    free(p);
}

// GetTop 取队头元素
void GetTop(LinkQueue *q, int *e)
{
    if (q->front != q->rear) {
        *e = q->front->next->data;
    }
}

应用

n阶汉诺塔

#include<stdio.h>

void move(char A, char B) {
    printf("%c ---> %c\n", A, B);
}

void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        move(A, C);
        return;
    }

    // 将A上编号为1至n-1的圆盘移动到B,C做辅助塔
    hanoi(n-1, A, C, B);
    // 将编号为n的圆盘从A移动到C
    move(A, C);
    // 将B上编号为1至n-1的圆盘移动到C,A做辅助塔
    hanoi(n-1, B, A, C);
}

表达式求值

// 表达式求值
// 1、初始化栈OPTR和OPND
// 2、扫描表达式，读入第一个字符ch，如果表达式没有扫描完成
//     a、若ch不是运算符，则压入OPND栈，读入下一个字符ch;
//     b、若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同的处理：
//         1、若是小于，则ch压入OPTR栈，读入下一个字符ch
//         2、若是大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈
//         3、若是等于，则OPTR的栈顶元素是"("且ch是")"，这是弹出OPTR栈顶的"("，相当于括号匹配成功，然后读入下一个字符ch
// 3、OPEN栈顶元素即为表达式求值结果，返回此元素
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100

// 运算符栈
typedef struct OPTRStack OPTRStack;
struct OPTRStack {
    char data;
    OPTRStack* next;
};

// 操作数栈
typedef struct OPNDStack OPNDStack;
struct OPNDStack
{
    double data;
    OPNDStack* next;
};

char getOptr(OPTRStack *optr)
{
    char ch = '-';
    if (optr == NULL)
    {
        return ch;
    }
    return optr->data;
}

OPTRStack* popOptr(OPTRStack *optr, char *ch)
{
    if (optr == NULL)
    {
        return optr;
    }
    *ch = optr->data;
    OPTRStack *p = optr;
    optr = optr->next;
    free(p);
    return optr;
}

OPNDStack* popOpnd(OPNDStack *opnd, double *data)
{
    if (opnd == NULL)
    {
        return opnd;
    }
    *data = opnd->data;
    OPNDStack *p = opnd;
    opnd = opnd->next;
    free(p);
    return opnd;
}

OPNDStack* pushOpnd(OPNDStack *opnd, double data)
{
    OPNDStack *p = (OPNDStack*)malloc(sizeof(OPNDStack));
    p->data = data;
    p->next = opnd;
    opnd = p;
    return opnd;
}

int isOPTR(char ch)
{
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#')
    {
        return 1;
    }
    return 0;
}

char precede(char a, char b)
{
    if (a == '+')
    {
        if (b == '*' || b == '/' || b == '(')
        {
            return '<';
        }
        return '>';
    }
    else if (a == '-')
    {
        if (b == '*' || b == '/' || b == '(')
        {
            return '<';
        }
        return '>';
    }
    else if (a == '*')
    {
        if (b == '(')
        {
            return '<';
        }
        return '>';
    }
    else if (a == '/')
    {
        if (b == '(')
        {
            return '<';
        }
        return '>';
    }
    else if (a == '(')
    {
        if (b == ')')
        {
            return '=';
        }
        else if (b == '#')
        {
            return '!';
        }
        return '<';
    }
    else if (a == ')')
    {
        if (b == '(')
        {
            return '!';
        }
        return '>';
    }
    else if (a == '#')
    {
        if (b == ')')
        {
            return '!';
        }
        else if (b == '#')
        {
            return '=';
        }
        return '<';
    }
    else
    {
        return '!';
    }
}

double operate(double left, double right, char operaor)
{
    double result;
    switch (operaor)
    {
    case '+':
        result = left + right;
        break;
    case '-':
        result = left - right;
        break;
    case '*':
        result = left * right;
        break;
    case '/':
        result = left / right;
        break;
    default:
        result = 0.0;
        break;
    }
    return result;
}

void EvaluateExpression() {
    // 初始化栈
    OPTRStack *optr = (OPTRStack*)malloc(sizeof(OPTRStack));
    optr->data = '#';
    optr->next = NULL;
    OPNDStack *opnd = NULL;

    char *str = (char *)malloc(sizeof(char)*MAXSIZE);
    // scanf("%s", str);
    str = "3*(7-2)#";
    int index = 0;
    char operator;
    int error = 0;
    while(str[index] != '\0')
    {
        char ch = str[index];
        if (error == 1) {
            break;
        }
        if (isOPTR(ch) != 1)
        {
            // 操作数入栈
            OPNDStack *opndNode = (OPNDStack*)malloc(sizeof(OPNDStack));
            opndNode->data = ch - '0';
            opndNode->next = opnd;
            opnd = opndNode;
            index++;
            continue;
        }

        char cede = precede(getOptr(optr), ch);
        switch (cede)
        {
        case '<':
            {
                OPTRStack *optrNode = (OPTRStack*)malloc(sizeof(OPTRStack));
                optrNode->data = ch;
                optrNode->next = optr;
                optr = optrNode;
                index++;
                break;
            }
        case '>':
            {
                optr = popOptr(optr, &operator);
                double left, right;
                opnd = popOpnd(opnd, &right);
                opnd = popOpnd(opnd, &left);
                opnd = pushOpnd(opnd, operate(left, right, operator));
                break;
            }
        case '=':
            {
                optr = popOptr(optr, &operator);
                index++;
                break;
            }
        default:
            {
                printf("Syntax Error!");
                error = 1;
                break;
            }
        }
    }
    if (error != 1)
    {
        printf("结果为:%lf\n", opnd->data);
    } else {
        printf("表达式错误!!!\n");
    }
}