前言
本章节开始数据结构第二篇，栈和队列：
栈：- 栈的存储结构
- 栈的基本操作
队列：
- 队列的存储结构
- 队列的基本操作
栈
我们把类似于弹夹那种先进后出的数据结构称为栈，栈是限定仅在表尾进行插入和删除操作的线性表，我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈，栈又称后进后出的线性表，简称LIFO结构。
栈首先是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系，只不过它是一种特殊的线性表而已。
栈的特殊之处在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫做进栈；栈的删除操作叫做出栈。
1.栈的存储结构
用来存放栈的数据元素对应的数据存储结构称为栈的存储结构。
1.1栈的顺序存储结构
栈是线性表的特例，所以栈的顺序存储结构其实就是线性表顺序存储结构的简称，我们简称为顺序栈。线性表是用数组来实现的，对于栈这种只能一头插入删除的线性表来说，用数组下标为0（栈底不变，只需要跟踪栈顶的变化即可）的一端作为栈底比较合适。
顺序栈定义如下：
typedef struct { int data[maxsize]; //定义一个数组大小为maxsize的数组，用来存放栈中数据元素 int top; //栈顶指针 }SqStack; //顺序栈定义 复制代码 1.2栈的链式存储结构
把栈顶放在单链表的头部，用链表来存储栈的的数据结构称为链栈。
链栈结点定义如下：
typedef struct LNode { int data; //数据域 struct LNode *next; //指针域 }LNode; //链栈结点 复制代码 2.栈的操作
2.1顺序栈的操作
对于顺序栈，一共有4个要素，包括两个特殊状态和两个操作。
特殊状态：
1）栈空状态：st.top == -1,也有的用st.top = 0表示栈空，这个时候栈顶位置为0。2）栈满状态：st.top == maxsize-1表示栈满。maxsize为栈中最大元素个数，maxsize-1为栈满时栈顶元素在数组中的位置，因数组位置是从0开始的。 操作：
顺序栈的进栈和出栈操作都是在栈顶进行的，所以只需要更改栈顶位置即可达到进栈和出栈的目的。1)初始化栈：
void initStack(SqStack &st) //初始化栈 { st.top = -1; //栈顶指针设置为-1 } 复制代码 2)进栈操作：
int push(SqStack &st,int x) { if(st.top == maxsize-1) //判断栈是否满，如果满，则不能进栈 return 0; ++(st.top); //栈顶指针位置加1 st.data[st.top] = x //x进栈，放在st.top位置 return 1; } 复制代码 3)出栈操作：
出栈与进栈是相对应的操作int push(SqStack &st,int x) { if(st.top == -1) //判断栈是否为空，如果空，则不能进行出栈 return 0; x = st.data[st.top] //先把栈顶元素取出来 --(st.top); //栈顶指针位置减1 return 1; } 复制代码 4)简化版的操作：
/*初始化栈*/ int stack[maxsize]; int top = -1; /*元素x进栈*/ stack[++top] = x /*元素x出栈*/ x = stack[top--] /*注意++top和top++的区别*/ top = 1 a = ++top b = top++ a = 2 b = 1 复制代码
2.2链栈的操作
与顺序栈对应，链栈也有4个元素，包括两个状态和两个操作。
状态：
1）栈空：lst -> next == NULL,即栈没有后继结点时，栈为空。2）栈满：如果存储空间无限大的话，不会存在栈满的情况。 操作：
链栈的进栈就是头插法建立链表的插入操作；出栈就是单链表的删除操作。void initStack(LNode *&lst) { lst = (LNode*)malloc(sizeof(LNode)); //制造一个头结点 lst -> next = NULL; //初始头结点指向为NULL } 复制代码 2)进栈：
void push(LNode *lst,int x) { LNode *p; p = (LNode*)malloc(sizeof(LNode)); //为进栈元素申请结点空间 p -> next =NULL; //初始化结点不指向任何元素 /*进栈,相当于链表的头插法*/ p -> data = x; //将x赋值给p结点的值域 p -> next = lst -> next; //p指针指向原lst指向的结点 lst -> next = p; //lst指向结点p } 复制代码 3)出栈：
int pop(LNode *lst,int &x) { LNode *p; if(lst -> next == NULL) //栈空则不能出栈，返回0；而栈不会满，所以在进栈的时候未作判断 return 0; /*出栈，相当于链表的删除结点*/ p = lst -> next; x = p -> data; lst -> next = p -> next; free(p); return 1; } 复制代码 4)简化版操作：
/*元素（指针p所指）进栈操作*/ /*类似于头插法建立链表*/ p -> next = lst -> next; //将空栈的头结点指向p lst -> next = p; //将指针p指向空栈头结点 /*出栈操作（出栈元素保存在x中）*/ /*类似于单链表的删除操作*/ p = lst -> next; x = p -> data; lst -> next = p -> next; free(p); 复制代码
队列：
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，队列是一种先进先出的线性表，简称FIFO，允许插入的一端称为队尾（Rear），允许删除的一端称为队头(Front)。向队中插入元素称为进队，新元素进队后成为新的队尾元素；向队中删除元素称为出队，元素出队后，其后继元素就成为新的队头元素。
1.队列的存储结构
用来存储队列数据元素的数据结构。
1.1队列的顺序存储结构：
使用顺序表存储队列时，队列元素的出队是在队头，即下标为0的地方，当有元素出队时，出队元素后面的所有元素都需要向前移动，保证队列的队头始终处在下标为0的位置，此时会大大增加时间复杂度。
typedef struct { int data[maxsize]; //定义数组 int front; //队首指针 int rear; //队尾指针 }SqQuene; //顺序队列定义 复制代码 1.2队列的链式存储结构：
用链表来存储队列元素的数据结构称为队列的链式存储结构，定义如下：
typedef struct QNode { int data; //数据域 struct QNode *next; //指针域 }QNode; //队结点类型定义 复制代码 链队类型定义：
typedef struct { QNode *front; //队头指针 QNode *rear; //队尾指针 }LiQuene; //链队类型定义 复制代码 2.队列操作
2.1循环队列
因为顺序队列出队时时间复杂度较高，有问题总是要解决的，为什么一定要让队头出现在下标为0的位置呢？所以有人提出了不去限制队列元素必须存储在数组的前n个单元这一条件，这样队头元素就不需要一定在下标为0的位置。但是随着队列元素的出队，队头指针在向后移动，假设队尾指针已经在maxsize-1的位置，这个时候虽然队列还有存储空间，但是队尾已经无法进队了，比如下图这样：
循环队列的要素：
两个状态：
队空状态：qu.rear = qu.front 复制代码
（qu.rear+1）%maxsize == qu.front 复制代码
两个操作：
元素x进队操作（移动队尾指针）qu.rear = (qu.rear+1)%maxSize; qu.data[qu.rear] = x; 复制代码
元素x出队操作（移动队头指针）
qu.front = (qu.front+1)%maxSize; x = qu.data[qu.front]; 复制代码
初始化队列算法：
void initQueue(SqQueue &qu) { qu.front = qu.rear = 0;队首和队尾指针重合，并且指向0 } 复制代码 进队算法：
int enQueue(SqQueue &qu,int x) { if ((qu.rear + 1) % maxSize == qu.front) //队满的判断条件，如果队满则不能进队，返回0 return 0; qu.rear = (qu.reat+1)%maxSize; //若队不满，先移动队尾指针 qu.data[qu.rear] = x; //元素x进队 return 1; } 复制代码 出队算法：
int enQueue(SqQueue &qu,int &x) { if (qu.rear == qu.front) //队空的判断条件，如果队空则不能出队，返回0 return 0; qu.front = (qu.front+1)%maxSize; //若队不空，先移动队首指针 x = qu.data[qu.front] ; //元素x出队 return 1; } 复制代码 2.2链队：
链队就是采用链式存储结构存储队列。链队的四个要素：队空和队满，元素进队和出队操作。
lqu -> rear == NULL; or lqu -> front == NULL 复制代码
队满状态：
一般来说不存在队满的情况，只要内存足够大。元素进队操作(指针p指向进队元素)
lqu -> rear -> next = p; lqu -> rear = p; 复制代码
元素出队操作（x存储出队元素）
p = lqu -> front; lqu -> front = p -> next; x = p -> data; free(p); 复制代码
初始化链队算法
void initQueue(LiQuene *&lqu) { lqu = (LiQueue*)malloc(sizeof(LiQueue)); lqu -> front = lqu -> rear = NULL; } 复制代码 判断队空算法
int isQueueEmpty(LiQueue *lqu) { if(lqu -> rear == NULL || lqu -> front == NULL) return 1; else return 0; } 复制代码 入队算法
void enQueue(LiQueue *lqu,int x) { QNode *p; p = (QNode*)malloc(sizeof(QNode)); p -> data = x; p -> next =NULL; if(lqu -> rear == NULL) lqu -> front = lqu -> rear = p; //如果队列为空，则新结点既是队尾结点也是队首结点 else { lqu -> rear -> next = p; //将新结点链接到队尾，rear指向该结点 lqu -> rear = p; } } 复制代码 出队算法
int deQueue(LiQueue *lqu,int &x) { QNode *p; if(lqu -> rear == NULL) //判断队空，如果为空，则不能出队 return 0; else p = lqu -> front; if(lqu -> front == lqu -> rear) //队列中只有一个结点时的出队操作 lqu -> front = lqu -> rear =NULL else lqu -> front = lqu -> front -> next; x = p -> data; free(q); return 1; } 复制代码