数据结构(栈和队列)

xhao 2020-05-04

  定义:栈是一个先进后出的线性表,要求只在表尾进行删除和插入操作

  注:对于栈来说,表尾成为栈的栈顶(top),相应的表头称为栈低(bottom)。

  因为栈的本质是线性表,所以栈也分为顺序存储结构和链式存储结构;(一般用顺序存储实现)

栈的顺序存储:

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define initSize 10
#define sup 2
typedef int ElemType;

typedef struct{
    int stackSize;//栈当前可用最大容量
    ElemType *base;//栈低
    ElemType *top;//栈顶
}sqStack;

void initStack(sqStack *);
void Push(sqStack *,ElemType);
void pop(sqStack *,ElemType *);

void pop(sqStack *s,ElemType *val){
    if(s->base==s->top){
        return ;
    }
    *val=*(--s->top);
}

void Push(sqStack *s,ElemType val){
    if(s->top-s->base>=s->stackSize){//判断栈是否存满,并追加空间
        s->base=(ElemType *)realloc(s->base,(s->stackSize+sup) * sizeof(ElemType));
        if(!s->base)
            exit(0);
        s->top=s->base+s->stackSize;
        s->stackSize+=sup;
    }
    *(s->top)=val;//栈顶压栈数据
    s->top++;
}

void initStack(sqStack *s){
    s->base=(ElemType *)malloc(initSize * sizeof(ElemType));
    if(!s->base)
        exit(0);
    s->top=s->base;
    s->stackSize=initSize;
}

void main(){
    int val;
    sqStack s;
    initStack(&s);
    printf("请输入压栈(-1退出):");
    scanf("%d",&val);
    while(val != -1){
        Push(&s,val);
        printf("请输入压栈(-1退出):");
        scanf("%d",&val);
    }
    printf("开始弹栈:\n");
    while(s.top!=s.base){
        pop(&s,&val);
        printf("%d  ",val);
    }
}

后缀表达式

  利用栈的方式:遍历中缀表达式;为数字压栈,为符号时弹栈;

  方法:从左到右遍历中缀表达式,若为数字时直接输出;若为符号,则判断其与栈顶符号的优先级:是‘)’的话则栈中符号依次出栈,直到遇到‘(’【括号不会输出在后缀表达式中】;其他符号:如果该符号优先级小于等于栈顶优先级,则栈中符号依次弹栈输出,直到栈顶符号优先级小于带压栈符号优先级或者栈顶为‘(’;如果遍历结束,再将栈中符号依次出栈输出;

例如:5+2*(3*(3-1*2+1))  =>  523312*-1+**+

后缀表达式的计算:1、按次序读取后缀表达式的每个字符。2、读取到操作数时,把操作数压入栈中。3、读取到操作符时,对栈顶的2个操作数做相应运算,要注意操作数的前后顺序。结果压入栈中。4、读取完所有字符后,弹出栈。得到的值就是所求结果。


队列

定义:只允许在一端进行插入操作,另一端进行删除操作的线性表

  与栈相反,队列是一种先进后出的线性表。

  队列既可以用链表实现,也可以用顺序存储实现,(一般用链表实现)

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode,* QueuePrt;

typedef struct{
    QueuePrt head;//队头
    QueuePrt rear;//队尾
}LinkQueue;

void init(LinkQueue *);
void Insedt(LinkQueue *,ElemType);
void pop(LinkQueue *,ElemType *);

void init(LinkQueue *q){
    q->head=q->rear=(QueuePrt)malloc(sizeof(QNode));
    if(!q->head)
        exit(0);
    q->head->next=NULL;
}

void Insedt(LinkQueue *q,ElemType e){
    QueuePrt p=(QueuePrt)malloc(sizeof(QNode));
    if(p==NULL)
        exit(0);
    p->data=e;
    p->next=NULL;
    q->rear->next=p;//用队尾链接
    q->rear=p;//更新队尾
}

void pop(LinkQueue *q,ElemType *e){
    QueuePrt p=q->head->next;//得到队列中头结点指向的结点()队列中第一个值
    q->head->next=p->next;//更新头结点指向的结点(在队列中删除原先第一个有值结点)
    if(q->rear==p){//判断删除结点是否为队列中最后一个结点
        q->rear=q->head;//队列将要成为空队列,将指向尾结点的指针指向头结点
    }
    *e=p->data;
    free(p);
}

void main(){
    ElemType val;
    LinkQueue s;
    init(&s);
    printf("%d\n",s.head->data);
    printf("请输入进入队列的数(-1退出):");
    scanf("%d",&val);
    while(val != -1){
        Insedt(&s,val);
        printf("请输入进入队列的数(-1退出):");
        scanf("%d",&val);
    }
    printf("开始出队列:\n");
    while(s.head!=s.rear){
        pop(&s,&val);
        printf("%d  ",val);
    }
    printf("\n");
}

相关推荐