学习数据结构（9）栈和队列上

1.栈的概念

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作 的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出（先进先出）的原则

栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶，栈的删除操作叫做出栈，出数据也在栈顶

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小

2.栈的实现

（1）初始化栈

（2）销毁栈

（3）判空

（4）入栈

（5）出栈

（6）取栈顶元素

 

（7）获取栈中有效元素个数

3.关于栈的算法题

解法一（参考解法）：遍历字符串，遇到左括号则入栈，遇到右括号时，判断栈是否为空，是则，销毁栈，直接返回false，不是则取栈顶数据，判断栈顶数据是否与右括号相对应，是则将栈顶数据出栈，不是则销毁栈，直接返回false，循环结束，判断栈是否为空，为空则说明括号全部配对，返回true，不为空则只有一种可能：栈中有未配对的左括号，返回false

4.队列的概念

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点，进行插入操作的一端称为队尾，进行删除操作的一端称为队头

队列也可以用数组和链表的结构实现，使用链表的结构实现更优，因为如果使用数组的结构，出队列就在数组头上出数据，效率会比较低

5.队列的实现

（1）初始化队列

（2）队列判空

（3）入队列

（4）出队列

 （5）销毁队列

（6）取队头元素

       

（7）取队尾元素

       

（8）队列有效元素个数