数据结构简单入门/复习(三)-栈与队列(C语言)

这里的栈用的是顺序栈(数组),队列用的是链表队列(链表)。

定义与结构

栈是一种限定在表尾进行插入/删除的线性表,表尾,被称作栈顶,表头,被称作栈底,薯片桶就是一种栈。

栈是一种后进先出的线性表。举个例子,有三个元素1、2、3,其中,1是第一个进的,2是第二个进的,3是第三个进的,那么在栈底的元素是1,栈顶的元素是3,若进行删除操作,出来的是栈顶的3。

#define SElemType int    //设置栈中元素的类型为int
typedef struct{
    SElemType *base;     //栈底
    SElemType *top;      //栈顶
    int stacksize;       //注意,这里的栈的大小是指总大小,而不是指用了几个,只在重新分配空间时会变化。
}SqStack;

栈的使用

SqStack S;

//初始化栈
S.base = (SElemType*)malloc(100*sizeof(SElemType));  //为栈分配空间,大小为100.
S.top = S.base;      //栈顶位置设置,因为此时栈是空栈。
S.stacksize = 100;   //将栈的大小设置为100,及最开始分配空间的大小。

//插入
if(S.top-S.base >= S.stacksize){    //这部分的判断是为了解决栈空间不足。
    S.base = (SElemType*)realloc(S.base, S.stacksize+10)*sizeof(SElemType));  //realloc是一个重新分配内存空间的函数,这里用来给栈增加10个空间。
    S.top = S.base + S.stacksize;  //栈底的地址因为realloc函数改变了,因此栈顶要重新设置。
    S.stacksize += 10;             //将栈的大小记录值增加。
}
*S.top++ = 123;

//删除
if(S.top == S.base) print("已空");  //栈顶和栈底指针相同,意味着是空栈。
else --S.top;                       //栈直接退后即可,不用释放内存。

//获得栈顶数据
printf("%d", *(S.top-1));           //top位置是用来存储新数据的,栈顶位置是在top-1的地方。

队列

定义与结构

队列是一种先进先出的线性表,元素从表头插入,从表尾退出。

队列的形式与日常的排队相似,但是没有插队这个说法。

//队列元素:
#define QElemType int
typedef struct QNode{
    QElemType data;      //元素数据
    struct QNode *next;  //后排元素
}QNode;
//队列存储:
typedef struct{
    QNode *front;    //队头指针
    QNode *rear;     //队尾指针
}LinkQueue;

队列的使用

//创建
LinkQueue Q;
Q.front = Q.rear = (QNode*)malloc(sizeof(QNode));   //队头不放元素,仅作指示

//插入
QNode *p = (QNode*)malloc(sizeof(QNode)); //分配新元素内存空间
p->data = 123;       //设置新元素值
p->next = NULL;      //新元素后没有元素
Q.rear->next = p;    //将队尾的下一个元素设置成新元素
Q.rear = p;          //将新元素设置为新的队尾

//删除
if(Q.front == Q.rear) print("队列已空");
else {
    QNode *temp = Q.front->next;           //创建临时指针指向队头
    Q.front->next = temp->next;            //将队头设置成第二位的元素
    if(Q.rear == temp) Q.rear = Q.front;   //如果队头是最后一个元素,将队尾的指针调整为队头指针,此时为空队列
    free(temp);                            //释放退出的队头
}

//获得队头值
if(Q.front == Q.rear) printf("队列已空");
else print("%d", Q.front->next->data);

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注