嵌入式

【嵌入式Linux C编程】数据结构---栈和队列

2019-07-13 00:32发布

站内文章 / 嵌入式Linux
10212 0 1503
栈stack栈是一个特殊的线性表，只能在一端操作；性质：后进先出（FLIFO）栈顶（top）：允许操作 的一端；栈底（bottom）：不允许操作的一端；若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。
若栈存在一个元素，top=0； 空栈的条件：top=-1；栈的结构typedef struct sqStack{ int data[MAXSIZE]; int top; }STACK;进栈int Push(STACK *S, int e) { if(S->top == MAXSIZE -1) return error; S->top++; S->data[S->top]=e; return OK; }出栈 int Pop(STACK *S, int *e) { if(S->top == -1) return ERROR; *e=S->data[S->top]; S->top--; return OK; } 栈的链式存储结构，简称为链栈；栈顶放在单链表的头部；链栈是不需要头结点的；链栈不存在栈满的情况。空栈的时候，链表原定义是头指针指向空。即top=NULL
链栈的定义typedef struct StackNode { int data; struct StackNode *next; }StackNode, *LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack;进栈操作进栈操作：元素值为e的新节点s，top为栈顶指针； int Push(LinkStack *S, int e) { LinkStackPtr p= (LinkStackPtr) malloc (sizeof(StackNode)); p->data=e; p->next=S->top; S->top=p; S->count++; return OK; }
出链栈操作pop操作：用变量p用来存储要删除的栈顶结点，将栈顶指针向下移动一位，最后释放p即可。 int Pop(LinkStack *S, int *e) { LinkStackPtr p; if(StackEmpty(*S)) return ERROR; *e=S->top->data; p=S->top; S->top=S->top->next; free(p); S->count--; reuturn OK; }

队列queue队列是特殊的线性表；队列仅在线性表两端进行操作；队头（Front）：取出数据的一端；队尾（Rear）：放入数据的一端。性质：先进先出（FIFO）判断队列满的条件：
(rear+1)%QueueSize==front;通用的计算队列长度公式为： (rear-front+QueueSize)%QueueSize;初始化链式队列初始化一个空队列Q： int InitQueue(SqQueue *Q) { Q->front = 0; Q->rear = 0; return OK; }在插入队列时，移动指向rear节点的指针进行操作，而front是不变的；离开队列时，移动指向front节点的指针，当front与rear指向同一个节点时，此时队列为空。

热门文章