文章来自解学武学习网站的免费章节

目录
什么是栈
进栈和出栈
栈的应用
什么是队列
队列的出队和入队
队列的实现

什么是栈
同顺序表和链表一样，栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构，如图 1 所示。



从图 1 我们看到，栈存储结构与之前所学的线性存储结构有所差异，这缘于栈对数据 “存” 和 “取” 的过程有特殊的要求：

栈只能从表的一端存取数据，另一端是封闭的，如图 1 所示；

在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。
因此，我们可以给栈下一个定义，即栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿图 2 来说，栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，图 2 中的栈底元素为元素 1。


进栈和出栈
基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：

向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；

从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

栈的具体实现

栈是一种 “特殊” 的线性存储结构，因此栈的具体实现有以下两种方式：

顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；

链栈：采用链式存储结构实现栈结构；

两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表。有关顺序栈和链栈的具体实现会在后续章节中作详细讲解。
栈的应用
基于栈结构对数据存取采用 “先进后出” 原则的特点，它可以用于实现很多功能。
例如，我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A，然后关闭了页面 A 跳转到页面 B，随后又关闭页面 B 跳转到了页面 C。而此时，我们如果想重新回到页面 A，有两个选择：

重新搜索找到页面 A；

使用浏览器的"回退"功能。浏览器会先回退到页面 B，而后再回退到页面 A。
浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。
不仅如此，栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。
同时，栈结构还可以实现数值的进制转换功能。例如，编写程序实现从十进制数自动转换成二进制数，就可以使用栈存储结构来实现。
什么是队列
队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。
与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出，如图 1 所示：


队列的出队和入队
通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。
不仅如此，队列中数据的进出要遵循 “先进先出” 的原则，即最先进队列的数据元素，同样要最先出队列。拿图 1 中的队列来说，从数据在队列中的存储状态可以分析出，元素 1 最先进队，其次是元素 2，最后是元素 3。此时如果将元素 3 出队，根据队列 “先进先出” 的特点，元素 1 要先出队列，元素 2 再出队列，最后才轮到元素 3 出队列。

栈和队列不要混淆，栈结构是一端封口，特点是"先进后出"；而队列的两端全是开口，特点是"先进先出"。
因此，数据从表的一端进，从另一端出，且遵循 “先进先出” 原则的线性存储结构就是队列。
队列的实现
队列存储结构的实现有以下两种方式：

顺序队列：在顺序表的基础上实现的队列结构；

链队列：在链表的基础上实现的队列结构；
两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。

队列的实际应用

实际生活中，队列的应用随处可见，比如排队买 XXX、医院的挂号系统等，采用的都是队列的结构。
拿排队买票来说，所有的人排成一队，先到者排的就靠前，后到者只能从队尾排队等待，队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后，才轮到自己买票。这就不是典型的队列结构吗？

一、栈
1、描叙
栈和队列是计算机中基本的两个数据结构，栈可以达到后进先出，队列可以先进先出。在实际应用上，我们可以使用栈进行逆序遍历链表，非递归中序遍历二叉树，括号匹配，函数调用等等；可以使用队列对二叉树进行层次遍历，打印机的打印服务，通信中的消息队列等等。
栈的储存规则:

1，栈只能从表的一端存取数据，另一端是封闭的

2，在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
栈的使用案例1:

浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。

当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。
栈的使用案例2:

栈存储结构还可以帮我们检测代码中的括号匹配问题。

多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。
2、图文示例
先进后出


3、代码示例
package stackAndQueue;

/**
 * TODO 栈，先进后出
 */
public class Stack {

    // 底层基于数组
    private int[] arr;
    // 数据长度, 最后一个数据的索引=数据长度-1
    private int size;

    // 容量设置
    public Stack() {
        arr = new int[16];
    }

    public Stack(int length) {
        arr = new int[length];
    }

    /**
     * 添加
     */
    public void plus(int val) {
        arr[size++] = val;
    }

    /**
     * 获取并弹出元素, 最后一个数据的索引=size-1
     */
    public int pop() {
        return arr[--size];
    }


    /**
     * 判断是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 容量是否满了，添加可先判断容量,进行扩容操作
     */
    public boolean isFull() {
        return size == arr.length;
    }
}




测试代码
// 测试
class Test {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.plus(1);
        stack.plus(2);
        stack.plus(3);
        stack.plus(4);
        stack.plus(5);
        System.out.println("容量是否满了-->" + stack.isFull());
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}


// 输出
容量是否满了-->true
5
4
3
2
1

二、队列
1、描叙
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。 [1]
队列的实现

队列存储结构的实现有以下两种方式：

顺序队列：在顺序表的基础上实现的队列结构；

链队列：在链表的基础上实现的队列结构；
两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
队列的实际应用

实际生活中，队列的应用随处可见，比如排队买 XXX、医院的挂号系统等，采用的都是队列的结构。
拿排队买票来说，所有的人排成一队，先到者排的就靠前，后到者只能从队尾排队等待，队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后，才轮到自己买票。这就不是典型的队列结构吗？
2、图文示例
普通队列
先进先出



循环队列
先进先出


3、代码示例
package stackAndQueue;


/**
 * TODO 队列，先进先出
 */
public class Queue {

    // 底层基于数组
    private int[] arr;
    // 数据长度
    private int size;
    // 开头元素索引 (每获取一次数据 front+1)
    private int front;
    // 结尾元素索引（每添加一次数据rear+1，每获取一次数据rear-1 ）--> 数据长度=rear+1
    private int rear;

    // 容量设置
    public Queue() {
        arr = new int[16];
        front = -1;
        rear = -1;
    }

    public Queue(int length) {
        arr = new int[length];
        front = -1;
        rear = -1;
    }

    /**
     * 获取当前数据长度
     */
    public int size() {
        return this.size;
    }

    /**
     * 插入元素
     */

    public void plus(int val) {
        // 判断数组是否满了
        if (isFull()) {
            System.out.println("插入["+val+"]失败,数组容量已满");
        } else {
            // 循环插入,--元素尾添加
            if (rear == arr.length - 1) {
                rear = -1;
            }
            size++;
            arr[++rear] = val;
        }
    }


    /**
     * 获取并弹出元素
     */
    public int pop() {
        // 循环读取--元素头开始读取
        if (front == arr.length - 1) {
            front = -1;
        }
        size--;
        return arr[++front];
    }

    /**
     * 判断元素是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 容量是否满了，添加可先判断容量,进行扩容操作
     */
    public boolean isFull() {
        return size == arr.length;
    }
}


测试代码
// 测试
class Test1 {
    public static void main(String[] args) {
        Queue queue = new Queue(5);
        queue.plus(1);
        queue.plus(2);
        queue.plus(3);
        queue.plus(4);
        queue.plus(5);
        System.out.println("容量是否满了-->" + queue.isFull() + "  当前数据长度:" + queue.size());
        //消费--> size=0
        while (!queue.isEmpty()) {
            System.out.println(queue.pop());
        }
        // 添加数据,size=0
        queue.plus(6);
        queue.plus(7);
        queue.plus(8);
        queue.plus(9);
        queue.plus(10);
        System.out.println("弹出--> " + queue.pop());
        queue.plus(11);
        //
        queue.plus(12);
        queue.plus(13);
        queue.plus(14);
        while (!queue.isEmpty()) {
            System.out.println(queue.pop());
        }
    }
}

// 打印
容量是否满了-->true  当前数据长度:5
1
2
3
4
5
弹出--> 6
插入[12]失败,数组容量已满
插入[13]失败,数组容量已满
插入[14]失败,数组容量已满
7
8
9
10
11

本文到此结束，如果觉得有用，劳烦各位点赞关注一下呗，将不定时持续更新更多的内容…，感谢大家的观看！

文章目录
栈(Stack)和队列(Queue)
栈(Stack)
进栈和出栈
栈的实现方式
顺序栈
初始化顺序栈
入栈
出栈
链栈
初始化链栈
入栈
出栈
队列(Queue)
队列实现方式
顺序队列
顺序队列的实现
循环队列的实现
链式队列
链式队列的实现
入队
出队

栈(Stack)和队列(Queue)
栈和队列，也属于线性表，都用于存储逻辑关系为 “一对一” 的数据。

栈也可分为顺序栈和链表，队列也分为顺序队列和链队列。
栈(Stack)
栈同顺序表和链表一样，栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构，且遵循"先进后出(FILO)"原则。
栈的开口端被称为栈顶，封口端被称为栈底。栈顶元素指的就是距离栈顶最近的元素，栈底元素指的是位于栈最底部的元素。
如下图所示：



栈只能从表的一端存取数据，另一端是封闭的。
在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。从图中可看出数据的存储状态，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。

进栈和出栈

向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

栈的实现方式

顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
链栈：采用链式存储结构实现栈结构；

顺序栈
顺序栈是利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的元素数据。分别使用top指针和base指针指向栈顶和栈底。
初始化顺序栈

分配存储空间。
置栈为空栈，即栈顶指针和栈底指针都指向栈底。

int InitStack(SqStack &S){
	S.base=new int[MAX];
	if(!S.base){
		return 0;
	}
	S.top=S.base; 
	S.stacksize=MAX;
	return 1;
}

入栈

将入栈元素压入栈顶。
然后栈顶指针加1。

int Push_S(SqStack &S,int e){
	//将元素e入栈 
	if(S.top-S.base==S.stacksize){//判断栈是否满 
		return 0;
	}
	*S.top++=e;
	return 1;
}

出栈

首先判断栈是否为空，若空返回ERROR,若不空，执行下一句。
栈顶指针减1，然后栈顶元素出栈。

int Pop_S(SqStack &S,int &e){
	//用e返回出栈的元素
	if(S.top==S.base){//栈空 
		return 0;
	} 
	e=*--S.top;
	return 1;
}

链栈
链栈的存储结构与单链表的存储结构相同。

由于栈是在栈顶进行删除和添加元素的，因此，将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。
链表的头部作为栈顶，意味着：

在实现数据"入栈"操作时，需要将数据从链表的头部插入；
在实现数据"出栈"操作时，需要删除链表头部的首元节点；

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。
初始化链栈
typedef struct StackNode{
	int data;
	struct StackNode *next;
}StackNode,*LinkStack;
 
int InitStack(LinkStack &S){
	S=NULL;//将栈顶指针置空
	return 1; 
}

入栈
int Push(LinkStack &S,int e){
	//元素e入栈
    //链栈要注意指针的方向是从栈顶指向栈底的 
	struct StackNode *p;
	p=new StackNode;
	p->data=e;
	p->next=S;
	S=p;	
}

出栈
int Pop(LinkStack &S,int &e){
	if(S==NULL){
		return 0;
	}
	e=S->data;
	struct StackNode *q;
	q=new StackNode;
	q=S;
	S=S->next;
	delete q;
	return 1;
}

队列(Queue)
队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出，遵循 "先进先出"（FIFO）的原则。
通常，称进数据的一端为 “队尾（rear）”，出数据的一端为 “队头（front）”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。

队列实现方式

顺序队列：在顺序表的基础上实现的队列结构；
链队列：在链表的基础上实现的队列结构；

两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
顺序队列
顺序队列，即采用顺序表模拟实现的队列结构，底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。
顺序队列的实现
#include <stdio.h>
int enQueue(int *a,int rear,int data){
    a[rear]=data;
    rear++;
    return rear;
}
void deQueue(int *a,int front,int rear){
    //如果 front==rear，表示队列为空
    while (front!=rear) {
        printf("出队元素：%d\n",a[front]);
        front++;
    }
}
int main() {
    int a[100];
    int front,rear;
    //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址
    front=rear=0;
    //入队
    rear=enQueue(a, rear, 1);
    rear=enQueue(a, rear, 2);
    rear=enQueue(a, rear, 3);
    rear=enQueue(a, rear, 4);
    //出队
    deQueue(a, front, rear);
    return 0;
}

程序输出结果:
出队元素：1
出队元素：2
出队元素：3
出队元素：4

此实现方式出现问题，随着入队出队的进行，会使整个队列整体向后移动，这样就出现了队尾指针已经移到了最后，再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”，这种现象为“假溢出”，这是由于队尾入，队头出的受限操作，以及为避免数据元素移动，队头队尾不固定造成的。
解决假溢出的方法有：


固定队头，出队后，队列中的所有元素向前移动。


固定队尾，入队时，队列中的所有元素向前移动。


将队列的数据区看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”。


循环队列的实现
#include <stdio.h>
#define max 5//表示顺序表申请的空间大小
int enQueue(int *a,int front,int rear,int data){
    //添加判断语句，如果rear超过max，则直接将其从a[0]重新开始存储，如果rear+1和front重合，则表示数组已满
    if ((rear+1)%max==front) {
        printf("空间已满");
        return rear;
    }
    a[rear%max]=data;
    rear++;
    return rear;
}
int  deQueue(int *a,int front,int rear){
    //如果front==rear，表示队列为空
    if(front==rear%max) {
        printf("队列为空");
        return front;
    }
    printf("%d ",a[front]);
    //front不再直接 +1，而是+1后同max进行比较，如果=max，则直接跳转到 a[0]
    front=(front+1)%max;
    return front;
}
int main() {
    int a[max];
    int front,rear;
    //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址
    front=rear=0;
    //入队
    rear=enQueue(a,front,rear, 1);
    rear=enQueue(a,front,rear, 2);
    rear=enQueue(a,front,rear, 3);
    rear=enQueue(a,front,rear, 4);
    //出队
    front=deQueue(a, front, rear);
    //再入队
    rear=enQueue(a,front,rear, 5);
    //再出队
    front=deQueue(a, front, rear);
    //再入队
    rear=enQueue(a,front,rear, 6);
    //再出队
    front=deQueue(a, front, rear);
    front=deQueue(a, front, rear);
    front=deQueue(a, front, rear);
    front=deQueue(a, front, rear);
    return 0;
}

程序输出结果:
1 2 3 4 5 6

使用此方法需要注意的是，顺序队列在判断数组是否已满时，出现下面情况：

当队列为空时，队列的头指针等于队列的尾指针；
当数组满员时，队列的头指针等于队列的尾指针；

链式队列
链式队列，简称"链队列"，即使用链表实现的队列存储结构。

链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 front 和 rear）分别指向链表中队列的队头元素和队尾元素。
链式队列的实现
//链表中的节点结构
typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
//创建链式队列的函数
QNode * initQueue(){
    //创建一个头节点
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next=NULL;
    return queue;
}

入队
新的数据元素入队，只需进行以下 3 步操作：

将该数据元素用节点包裹，例如新节点名称为 elem；
与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
最后移动 rear 指针指向该新节点，即 rear=elem

QNode* enQueue(QNode * rear,int data){
    //1、用节点包裹入队元素
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next=enElem;
    //3、rear指向新节点
    rear=enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}

出队
元素出队，需要做以下 3 步操作：

通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
将 p 节点（即要出队的队头节点）从链表中摘除；
释放节点 p，回收其所占的内存空间；

void DeQueue(QNode * top,QNode * rear){
    if (top->next==NULL) {
        printf("队列为空");
        return ;
    }
    // 1、
    QNode * p=top->next;
    printf("%d",p->data);
    top->next=p->next;
    if (rear==p) {
        rear=top;
    }
    free(p);
}


本篇完！！！

栈和队列
1）概述
和顺序表和链表一样，栈也是用来存储逻辑关系为“一对一”数据的线性存储结构

栈对数据存和去的过程有特殊的要求：

栈只能从表的一端存取数据，另一端是封闭的
在栈中，无论是存数据还是取数据，都必须遵循先进后出的原则，即最先进栈的元素最后出栈。

简单来说：栈是一种只能从表的一端存取数据且遵循“先进后出”原则的线性存储结构
栈顶：栈的开口端
栈底：栈的封口端
栈顶元素指的是距离栈顶最近的元素，而栈底元素指的是，位于栈最底部的元素
进栈和出栈：
基于栈结构的特点，在实际的应用中通常会对栈执行下面的两种操作：

向栈中添加元素，此过程被称为“进栈”（入栈或压栈）
从栈中提取出指定元素，此过程中被称为出栈（或弹栈）

栈的具体实现：
栈是一种特殊的线性存储结构，因此栈的具体实现有以下两种方式：

顺序栈：采用顺序存储结构，可以模拟栈存储数据的特点，从而实现栈存储结构
莲栈：采用链式存储结构实现栈

2）顺序栈
顺序栈，也就是用顺序表来实现栈存储结构（就是说用数组来实现）。
如果仔细观察顺序表和栈结构就会发现，他们存储数据的方式高度相似，只不过栈对数据的存取过程有特殊的限制，而顺序表没有。
在使用顺序表模拟栈存储结构常用的实现思路，就是在顺序表中设定一个实时指向栈顶元素的**变量(**top)，top的初值为-1，表示栈中没有存储任何数据元素，也就是说栈是空栈，一旦数据元素进栈，top就 +1，如果元素出栈 top 就-1

理解：
top代表栈顶元素的索引值

元素“入栈”
最初的时候栈是空栈，即数组是空的，top的初始值为-1。
向栈中添加元素1，则top = 0然后依次存储
typedef struct SortStack{
    int* array;
    int top ;
}*sortStack;



int push(sortStack stack,int elem){
    stack->array[++(stack->top)]=elem;
    return stack->top;
}


分析：
从代码中定义了一个SortStack的数据结构，这个数据结构中一个属性用于存储一个数组，另一个用于存储top指针。
push方法用于向数组中添加一个数据。
这样的行为称之为“入栈”

元素“出栈”
top变量其实对模拟数据入栈的操作没有什么实际的帮助，但是它是为了实现数据出栈而准备的。
出栈时需要把数据一个个的扔出栈，直到取到对应位置的元素，而这里的对应的位置索引就是通过top来完成指向的。
/**
 * 弹出栈的最后一个元素
 * @param array
 * @return
 */
int pop(sortStack stack){
    if (stack->top == -1){
        INFO_LOG("This stack is a empty stack");
        return -1;
    }
    int tempData = stack->array[stack->top];
    printf("The last elem is : %d",tempData);
    stack->top--;
    return tempData;
}


分析：
由于top总是指向栈顶元素，所以每次都会把栈定的元素弹出来。
如果top的值为-1则说明这个栈是一个空栈

3）链栈
链栈就是用链表实现栈存储结构
顺序栈是将顺序表的一端作为栈底，另一端作为栈顶，而链栈也是这样的，通常我们将链表的头部作为栈顶，尾部作为栈底。

对于这个也很显而易见，对于栈来说，我们无法随机存取，这和链表的顺序存取结构也是十分契合的。
这里以头为顶更便于栈的理解。
元素“入栈”

linkStackNode push(linkStackNode head,int element){
    linkStackNode newNode = (linkStackNode)malloc(sizeof (struct LinkStackNode));
    //让新结点的next指向head
    newNode->next = head;
    newNode->data = element;
    head = newNode;
    //把新结点作为head返回
    return head;
}

元素“出栈”
linkStackNode pop(linkStackNode head){
    if (head){
        //保证栈内是有元素的
        linkStackNode temp = head;
        //然后把栈顶元素进行更新
        head = head->next;
        printf("出栈元素 ：%d",temp->data);
        if (head){
            printf("新栈顶元素 %d\n",head->data);
        } else{
            printf("栈已空");
        }
        free(temp);
    } else{
        printf("栈内已无元素");
        return head;
    }
    return head;
}


出栈的思想也很简单，就是把栈顶元素弹出，然后更新栈顶元素即可。
注意整个过程中避免栈内无数据还要做数据出栈的错误操作

4）用栈结构求表达式的值
如何用栈结构求一个表达式的值？
所谓表达式，就是由变量、常量以及运算符组合而成的式子，常用的运算符有(!,^,+,-,*,/,())这几种
用栈结构去求一个表达式的值，已经设计好了全新的表示表达式方法，称为后缀表达式或者逆波兰表达式。和普通表达式不同，后缀表达式习惯把运算符写在它的运算项之后，而且整个表达式的过程中不用() 表明运算的优先级关系
比如说：表达式-> !3 + 4*2/(1-5)^2
就可以转换为后缀表达式：
3 !  4 2 * 1 5 - 2 ^ / +

虽然后缀表达式相比于普通的表达式来说，能轻松的借助栈存储结构求得值，但是却完全舍弃了表达式该有的可读性。
具体求值的过程：当用户给定一个后缀表达式时，按照从左到右的顺序依次扫描表达式中的各个运算项和运算符

遇到运算项时，直接入栈
遇到运算符时，将位于栈顶的运算项出栈，对于单目运算符去一个运算项，对于双目运算符去两个运算项，第一个取出来的运算向作为右运算项，另一个作为左运算项，求得表达式的值后将其入栈
直到栈中存在一个运算项为止，此运算项即为整个表达式的值

5）队列
队列和栈一样也是一种对数据的存取由严格要求的“线性存储结构”
和栈结构不同的是，队列的两端都开口，，要求数据只能从一端进，从另一端出

进数据的一端叫做队尾，出数据的一段叫做队头，数据元素进队列的过程叫做入队，出队列的过程叫做出队。

队列中数据的进出要求遵循，先进先出的原则，最先进队列的数据元素最先出队列，最后进队列的元素，最后出队列
区分：
对于栈来说是先进后出，而对于队列来说是先进先出。栈是一端开口，队列是两端开口

根据存储结构的实现可分为：

顺序队列：在顺序表的基础上实现的队列结构
链队列：在链表的基础上实现的队列结构

两者的区别仅是顺序表和链表的去呗，即在实际的物理空间中，如果数据几种存储就是用的顺序队列，如果数据分散存储就是用的链队列。
6）顺序队列
顺序队列使用的是数组，因此需要提前申请一块足够大的内存空间初始化顺序队列，初次之外，满足顺序队列中数据从队尾进，队头出且先进先出的要求，需要定义两个指针(top 和 rear) 分别指向队列的队头元素和队尾元素。

当数据元素进队列时，对应的操作应该是将其存储在rear指向的数组的位置，然后rear + 1，当需要出队列的时候，就需要做 top +1 的操作


方法一：
#include <stdio.h>
#define DEBUG_LOG
#define INFO
#include "log.h"
#include "malloc.h"

typedef struct SortQueue{
    int* array;
    int top;
    int rear;
}*sortQueue;

/**
 * 初始化具有阿巴个元素的队列
 * @param n
 * @return
 */
sortQueue init(){
    sortQueue queue = (sortQueue)malloc(sizeof (struct SortQueue));
    int array[] = {1,2,3,4};
    queue->array = array;
    queue->rear = 4;
    queue->top = 0;
}

/**
 * 进队列的方法
 * @param queue
 * @return
 * 把data放到queue 里面
 */
sortQueue inQueue(sortQueue queue,int data){
    int rearIndex = queue->rear;
    queue->array[rearIndex] = data;
    queue->rear += 1;

    return queue;
}

/**
 * 出队列的方法
 * @param queue 
 * @return 
 */
sortQueue outQueue(sortQueue queue){
    int topIndex = queue->top;
    int rearIndex = queue->rear;
    if (topIndex == rearIndex){
        INFO_LOG("There is not element!Can't out queue");
    } else{
        printf("The top element is >>>%d",queue->array[queue->top]);
    }
    queue->top+=1;
    return queue;
}

这种方法穿在一个问题：
当数据全部出队后，top和rear的重合指向了a[4]而不是a[0]，也就是说，整个顺序队列在数据的不断进队出队的过程中，在顺序表中的位置不断的后移
影响：

顺序队列之前的数组存储空间将无法再被使用，造成空间浪费
如果顺序表申请的空间不够大，就容易造成溢出，产生溢出错误

所以就有了方法二
方法二：
将顺序表打造成一个环状

代码修改：
/**
 * 进队列的方法
 * @param queue
 * @return
 * 把data放到queue 里面
 */
sortQueue inQueue(sortQueue queue,int data){
    /*
     * 新增判断语句，如果再增加的一个元素的下一个元素大于max，则从a[0]重新开始存储
     * 如果rear +1 和 front 重合，则表明数组已满
     *
     */
    if (((queue->rear)+1)%sizeMax == queue->top){
        /**
         * 这里就表示空间已满，rear队尾指针和头指针重合
         */
        printf("The space if full");
        return queue;
    }
    int rearIndex = queue->rear;
    queue->array[rearIndex % sizeMax] = data;
    queue->rear = (rearIndex % sizeMax) + 1;

    return queue;
}

/**
 * 出队列的方法
 * @param queue
 * @return
 */
sortQueue outQueue(sortQueue queue){
    int topIndex = queue->top;
    int rearIndex = queue->rear;
    //如果front == rear 表示队列为空
    if (topIndex == rearIndex){
        INFO_LOG("There is not element!Can't out queue");
    } else{
        printf("The top element is >>>%d",queue->array[queue->top]);
    }
    queue->top = (queue->top+1)%sizeMax;
    return queue;
}


通过取余的方式来实现最后可以接到表头，这样其实是一种很巧妙的方式实现顺序队列的头尾相接，且不用再本身的物理结构上进行修改，因为对于这个顺序队列还是线性的，但是在逻辑上已经是环状的了。

注意：

当队列为空的时候，队列的头指针会等于队列的尾指针
当队列满员的时候，队列的头指针会等于队列的尾指针

7）链式队列
链式队列，通过链表实现队列的存储结构
通过链表实现队列的方式和顺序队列是一样的，都需要借助一个top指针和一个rear指针，一个指向队列头，一个指向队列尾。
#include <stdio.h>
#include"log.h"
#include <malloc.h>

/*
 *定义链式队列的结点
 */
typedef struct LinkQueueNode{
	struct LinkQueueNode * next;
	int data;
}*linkQueueNode;

/*
 * 向队列中插入数据应该向队尾插入
 * 对于链式队列来说就不存在会有空间满了的情况了
 * 传入链表的最后一个结点，直接把结点添加最后即可
 */
linkQueueNode inQueue(linkQueueNode rear,int newData){
	linkQueueNode newNode = (linkQueueNode)malloc(sizeof(struct LinkQueueNode));
	newNode->next = NULL;
	newNode->data = newData;
	rear->next = newNode;
	rear = newNode;
	return newNode;
}

/*
 * 向队列中退出一个元素，将top指针所指向的首元素出队
 *	出队之后要根据对列的长度保证 top 指针和 rear 指针指向正确	
 *  如果队列出队后的长度大于等于1，则rear 指针不用管
 * 但是如果队列出队后的长度为0，这个时候就意味着rear指针的之前指向已经出队的node 这个时候就需要更新指针的指向了 
 */
linkQueueNode outQueue(linkQueueNode top,linkQueueNode rear){
	if (top == NULL || top->next == NULL)
	{
		printf("There is a empty queue");
	}

	linkQueueNode outNode = top;
	printf("出栈元素是>>>>%d\n",outNode->data);
	top = top->next;
	/*
	 * 如果尾指针指向一开始的首元素，且队列的长度为1，那么让他指向新的空结点
	 */
	if (rear == outNode)
	{
		rear = top;
	}
	free(outNode);
}


在出队元素的时候一定要提前判断队列中是否还有元素，要提示用户无法做出出队操作，保证程序的健壮性
8）小结
首先：虽然栈和队列存储结构不同，但是两者都是线性结构
线性结构：用于存储逻辑关系为”一对一“数据的存储结构，比如说顺序存储结构和链式存储结构