《数据结构》_3堆栈和队列

时间:2022-03-04 10:34:09

堆栈

堆栈是限定插入和删除操作都在表的同一端进行的线性表。 特点为LIFO(后进先出)

堆栈的顺序表示.c

#include<stdio.h>
typedef struct//堆栈结构体定义
{
    int top;//当前栈顶位置的下标
    int maxSize;;//maxSize-1是堆栈最大位置的下标
    ElemType *element;//自定义类型,可根据实际情况设定int、float等等
}
void Create(Stack *S,int mSize)//创建一个能容纳mSize个单元的空堆栈
{
    S->maxSize=mSize-1;
    S->element=(ElemType*)malloc(sizeof(ElemType)*mSize);
    s->top=-1;
}
void Destroy(Stack *S)//销毁已存在的堆栈,释放数组空间
{
    S->maxSize=-1;
    free(S->element);
    S->top=-1;
}
BOOL IsEmpty(Stack
*S)//空就返回TRUE,否则FALSE { return S->top==-1; }
BOOL IsFull(Stack
*s) { return S->top==S->maxSize; }
BOOL Top(Stack
*S,ElemType *x)//获得栈顶元素 { if(IsEmpty(S)) return FALSE; x=S->element[S->top]; return TURE; }
BOOL Push(Stack
*S,ElemType x)//在栈顶插入元素(入栈) { if(IsFull(S)) return FALSE; S->top++; S->element[S->top]=x; return TURE; }
BOOL Pop(Stack
*S)//删除栈顶元素(出栈) { if(IsEmpty(S))return FALSE; S->top--;return TRUE; } void Clear(Stack *S)//清除全部的元素,但并不释放空间 { S->top=-1; } void main(){ printf("我不知道输些什么哈···"); }

队列

队列是限定在表的一端插入,在另一端输出的线性表。FIFO(先进先出)

在队列的使用中,设定了循环队列,以防止假“溢出”现象。但是循环队列永远要保持至少一个空位。

队列的顺序表示.c

#include<stdio.h>
typedef struct
{
    int front;
    int rear;
    int maxSize;
    ElemType *element;
}Queue;

void create(Queue *Q,int mSize)
{
    Q->maxSize=mSize;
    Q->element=(Element*)malloc(sizeof(ElemType)*mSize;
    Q->front=Q->rear=0;
}

void Destroy(Queue *Q)
{
    Q->maxSize=-1;
    free(Q->element);
    Q->front=Q->rear=-1;
}

BOOL IsEmpty(Queue *Q)
{
    return Q->front=Q->rear;
}

BOOL IsFULL(Queue *Q)
{
    return Q->front==(Q->rear+1)%Q->maxSize;
}

BOOL Front(Queue *Q,ElemType *x)//获取队头元素,并通过x返回。操作成功就返回TURE,否则返回FALSE
{
    if(IsEmpty(Q)) return FALSE;//空队列处理
    x=Q->element[(Q->front+1)%Q->maxSize];
    return TRUE;
}

BOOL EnQueue(Queue *Q,ElemType *x)//在队列Q的队尾插入元素x(入队),操作成功则返回TURE,否则FALSE
{
    if(IsFULL(Q)) return FALSE;//溢出处理
    Q->rear=(Q->rear+1)%Q->maxSize;
    Q->element[Q->rear]=x;
    return TRUE;
}

BOOL DeQueue(Q)//删除头元素(出队)
{
    if(ISEmpty(Q)) return FALSE;
    Q->front=(Q->front+1)%Q->maxSize;
    return TURE;
}

void Clear(Queue *Q)//清空队列元素,但并不释放空间
{
    Q->front=Q->rear=0;
}

表达式计算

重点为中缀表达式和后缀表达式的相互转化。

代码和原理可以参考:https://blog.csdn.net/huangchijun11/article/details/60963444

在这里做两个题

  • (a+b)/(c+d)    ->              ab+cd+/
  • a*c-b/c^2       ->               ac*bcc*/-
  • a*b/c              ->               ab*c/
  • a+(b*c+d)/e  ->                abc*d+e/+
  • a/(b-c)+d*e    ->               abc-/de*+
  • a*((b+c)/(d-e)-f)  ->         abc+de-/f-*
  • (a+b)*(c*d+e)-a*c   ->    ab+cd*e+*ac*-