栈和队列
作者:
admin
2019-12-05 23:45:29
阅读(48)
评论(0)
二. 栈和队列
1. 栈
(1) 概念
栈只能在一端进行插入或者删除操作，插入元素称为入栈，删除元素称为出栈。
在存储结构上分为顺序栈和链栈。主要特点是先进后出（FILO）。
n个元素入栈（满足先进后出原则），所获得的元素排列数目 N 为：
$ N = \frac{1}{n+1}C_{2n}^{n} $
(2) 数据结构
/*顺序栈*/ //top == -1表示栈空，top == maxSize - 1 表示栈满。 typedef struct { int data[maxSize]; // 栈中元素 int top; // 栈顶指针 }SqStack; // 类型定义 //考试中定义顺序栈并初始化一般这样写 int stack[maxSize]; int top = -1; //考试中写元素 x 入栈 /*注意 ++top 和 top++ 的区别，两者都能实现自增的效果，但 ++top 的值为自增后的值，而 top++ 的值仍等于自增前的值。--top 和 top--类似。*/ stack[++top] = x; //考试中写出栈 x = stack[top--];
/*链栈*/ //链栈默认情况下不存在栈满情况，栈空即为栈顶指针的 next 指针域为 NULL //链栈的入栈相当于单链表头插法，出栈相当于删除单链表元素 typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域 }LNode; // 类型定义
2. 队列
(1) 概念
队列只允许在一端（队尾 rear）插入数据（入队），另一端（队头 front）删除数据（出队）。特点是先进先出，类似于隧道。可分为顺序队和链队。
(2) 数据结构
顺序队：
/*顺序队列*/ typedef struct { int data[maxSize]; int front; int rear; }SqQueue;
链队：
/*队结点*/ typedef struct QNode { int data; struct QNode *next; }QNode; /*链队*/ typedef struct { QNode *front; QNode *rear; }LiQueue;