# Queue_Stack

**Repository Path**: sophiea/Queue_Stack

## Basic Information

- **Project Name**: Queue_Stack
- **Description**: 依赖数组实现栈，实现链式队列，实现循环队列，两个栈实现一个队列，两个队列实现一个栈，实现最小栈，栈的练习之括号匹配
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2019-07-27
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

* 1、实现链式队列
    * 特点：先进先出
    * 定义Node类，存放队列的data，next
    * 定义Node类的front（头结点），rear（尾结点），int类型的usesize（队列的大小）
    * 定义front和rear的原因：
        * 采用头插的话，队列的插入的时间复杂度是O(1)，删除的时间复杂度是O（N）;
    采用尾插的话，队列的插入的时间复杂度是O(N),删除的时间复杂度是O(1)，所以为了不去找头和尾，
    我们就定义一个可以很方便的进行插入删除
 * 2、实现栈
    * 依赖数组实现栈
    * 定义一个数组，int型的top表示栈顶（表示当前可以插入元素的位置），usesize表示使用的栈的大小
    * 栈的push和pop要注意top的移动，usesize的增加减小
 * 3、栈的练习题之括号匹配
    * 可以在leetcode上找到
    * 明确，括号的几种情况
        * 1、左右括号匹配
        * 2、左括号多
        * 3、右括号多
        * 4、括号次序不匹配
    * 步骤：
        * 0、遍历给定字符串的每个元素
        * 1、判断元素是否是左括号，若是左括号，则加入到栈中，若不是，执行第二步
        * 2、元素是右括号，判断栈是否为空，若为空，则表示右括号多，否则，执行第三步
        * 3、栈不为空，则将栈顶元素与当前元素进行匹配，若不匹配，则表示括号次序不匹配，否则，执行第四步
        * 4、栈顶元素和当前元素匹配，则将栈顶元素出栈
        * 5、重复上诉步骤，直到遍历结束
        * 6、遍历结束，判断栈是否为空，若栈不为空，则表示左括号多，否则括号匹配；
 * 4、两个队列实现一个栈
    * 明确队列的特点：先进先出；栈的特点：先进后出
    * 1、我们利用两个队列去实现一个栈，
    * 2、模拟入栈，若两个队列全为空，则选queue1插入元素；否则，将元素插入不为空的队列中
    * 3、模拟出栈，判断队列是否为空，若不为空，则将该队列的前i-1个元素出队，然后入队到另一个空对列中
    ，然后将最后一个元素出队，就达到了后进先出的栈的模样
    * 4、模拟取得栈顶元素，类似于出栈，只不过只是取出来值，然后返回，最后将最后一个元素再出队入队到另一个队列中
    * 5、模拟栈是否为空，若两个队列都为空，则栈为空
    * 6、模拟得出栈的size，也就是不为空的队列的size
 * 5、两个栈实现一个队列
    * 明确特点
    * 1、模拟队列入队，若两个栈都为空，则任意选一个stack1入栈，否则，元素插入不为空的栈
    * 2、模拟队列出队，判断哪个栈不为空，将不为空的栈的i-1个元素出栈入栈到另一个栈中，
    然后将该栈的元素pop出，然后再将另一个栈的元素出栈入栈到该栈中，否则会改变元素的次序
    * 3、模拟获得队头元素，大致步骤同队列出队一样，只不过不弹出去，只是拿到值即可，然后再将另一个栈中的元素出栈入栈到该栈中
    * 4、模拟队列是否为空，若两个栈全为空，则队列为空
    * 5、模拟得到队列的size，即不为空的栈的size
 * 6、最小栈
    * 什么是最小栈：即任何时候可以从该栈的栈顶拿到栈的最小元素
    * 1、准备两个栈，stack和minstack
    * 2、入栈，stack直接入栈，minstack要进行栈顶元素的比较，若栈顶元素大于当前元素，则入栈，否则，不入栈
    * 3、出栈，若stack的栈顶元素与minstack的栈顶元素相同，则同时出栈，否则，只是stack出栈
    * 4、获得栈顶元素，直接返回stack的栈顶元素
    * 5、获得最小元素，返回minstack的栈顶元素
 * 7、循环队列
    * 什么是循环队列？顺序队列，收尾相连,用数组实现
    * 当front==rear时，说明队列为空；当 front=（rear+1）%elem.length时，说明队列已满
    * 这里采用浪费一个空间来判断队列是否满不满
    * 入队时，要注意判断队列是否已满，以及rear指针的位置，若elem.length=5,front=2,rear=4
    ，则再入队时，rear=0，而不是5，也及时rear=(rear+1)%elem.length;
    * 出队时，front=(front+1)%elem.length，也是同样要注意的
    * 返回队尾元素，由于rear表示的可以可以存放数据元素的位置，若rear=0时，队尾元素应该是在this.elem.length-1的位置，不为0时，是在rear-1的位置，需要注意,
    即 int index=  this.rear==0? this.elem.length-1:this.rear-1;   return elem[index];