数据结构:Stack and Queue

Stack and Queue

对应官方的java.util.stack

stack的实现:使用线性表或者链表

而stack最长涉及到的操作是:push and pop

stack涉及到的算法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
     /**
    * 元素入栈 只能从栈顶出栈
    * @param element
    */
   public void push(E element);

   /**
    *元素出栈 只能从栈顶出栈
    * @return
    */
   public E pop();

   /**
    * 获取栈顶元素
    * @return
    */
   public E peek();

/***********下面这些算法可以复用线性表的算法**************/

   /**
    * 查看stack内元素数量 
    * @return
    */
   public int size();

   /**
    * 判断stack内是否为空
    * @return
    */
   public boolean isEmpty();

   /**
    * 清空栈内元素
    * @return
    */
   public void clear();

实现功能:可以从front入队和rear出对 对应官方的LinkedList

实现方式:使用链表或者double stack

Time Complexity:在front进行出对和在rear进行入队的Time Complexity都是O(1);如果使用SequenceList在front进行出对的Time Complexity是O(n),在rear进行入队的Time Complexity是O(1).

但是在CircleQueue中我们将使用动态数组实现循环队列并且将各个函数都优化到O(1)的time complexity

Queue涉及到的算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    /**
     * 元素数量
     * @return
     */
    public int size()

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty()

    /**
     * 入队
     */
    public void enQueue(E element)
    {
        //从对尾rear入队
        list.add(list.size(),element);
    }

    /**
     * 出对 只能从front出对
     */
    public E deQueue()

    /**
     * 获取对头元素
     * @return
     */
    public E front()

    /**
     * 清空queue
     */
    public void clear()    

使用双向链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 private LinkList<E> list = new LinkList<>();

    /**
     * 元素数量
     * @return
     */
    public int size()
    {
    return list.size();
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty()
    {
        return list.isEmpty();
    }

    /**
     * 入队
     */
    public void enQueue(E element)
    {
        //从对尾入队
        list.add(list.size(),element);
    }

    /**
     * 出对
     */
    public E deQueue()
    {
        //从对头出对
        return list.remove(0);
    }

    /**
     * 获取对头元素
     * @return
     */
    public E front()
    {
        return list.get(0);
    }

    /**
     * 清空queue
     */
    public void clear()
    {
        list.clear();
    }

使用double stack实现

截屏2022-01-09 上午12.05.28
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 private Stack<E> inStack = new Stack<>();
    private Stack<E> outStack = new Stack<>();


    /**
     * 元素数量
     *
     * @return
     */
    public int size()
    {
        return inStack.size()+outStack.size();
    }

    /**
     * 是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return inStack.isEmpty()&&outStack.isEmpty();
    }

    /**
     * 入队
     */
    public void enQueue(E element) {
        //push到inStack中
        inStack.push(element);
    }

    /**
     * 出对
     */
    public E deQueue() {
        //如果outStack为空
        if(outStack.isEmpty()) {
            //将inStack所有元素pop到outStack 再弹出栈顶元素
            while (!inStack.isEmpty()) {
                E e = inStack.pop();
                outStack.push(e);
            }
        }
            //如果outstack不为空 就直接弹出栈顶元素
            return outStack.pop();

    }

        /**
         * 获取对头元素
         * @return
         */
        public E front() {
            if (outStack.isEmpty()) {
                //将inStack所有元素pop到outStack 再弹出栈顶元素
                while (!inStack.isEmpty()) {
                    E e = inStack.pop();
                    outStack.push(e);
                }
            }
            //如果outstack不为空 就直接弹出栈顶元素
            return outStack.pop();
        }



            /**
             * 清空queue
             */
            public void clear()
            {
                inStack.clear();
                outStack.clear();
            }

实现功能:可以从front入队和rear出对的循环队列

实现方式:使用动态数组实现(需要一个索引front指明对头的位置还需要一个数组字段和查看目前数组内元素数量的size字段)

循环的含义:接下来不会直接扩容 会将0和1位置填满后再进行扩容

截屏2022-01-09 上午11.14.24

CircleQueue涉及到的算法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
    /**
     * 元素数量
     * @return
     */
    public int size()

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty()

    /**
     * 入队
     */
    public void enQueue(E element)

    /**
     * 出对 只能从front出对
     */
    public E deQueue()

    /**
     * 获取对头元素
     * @return
     */
    public E front()

    /**
     * 清空queue
     */
    public void clear()    
      
    /**
     * 扩容
     */
     private void ensureCapacity(int capacity)

考虑普通情况下的入队算法

1
2
        elements[front + size] = element;
                //2 + 3
截屏2022-01-09 上午11.13.28

如果顺序已经存满,考虑循环存储

1
2
        elements[(front + size) % elements.length] = element;
                2 + 5 % 7
截屏2022-01-09 上午11.14.24
1
2
3
因此将将真实索引(i)转化为循环队列上的索引(index)的公式为:
                                                    index = (front + i) % elements.length
真实的索引:数组上的顺序索引 按照正常情况来说 元素应该在第i位置上 front的真实索引就是0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    /**
     * 算法描述:
       1.判断容量是否足够
       2.使用入队算法(只能从尾部入队)
       3.size++;
     */
    public void enQueue(E element)
    {
        ensureCapacity(size+1);
        elements[(front + size) % elements.length] = element;
        size++;
    }    
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    /**
     * 算法描述:
       1.保存要出对的元素
       2.将front索引所指位置内容null
       2.size--;
       3.front索引向前移动
     */
    public E deQueue()
    {
        E e = elements[front];
        elements[front]=null;
        size--;
        front = (front + 1) % elements.length;
        return e;
    }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    /**
     * 算法分析:因为清空算法要保证清空的效率,所以只用清空有存储的数组位置,null的                 位置不用清空
          1.直接使用清空算法
     */
    public void clear()
    {
        for (int i = 0; i < size; i++) {
            elements[(front + i) % elements.length] = null;
        }
        this.size = 0 ;

    }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 算法分析
      1.判断容量是否满足
      2.创建新的数组
      3.挪动
      4.将老数组指向新数组并将起始位置指针指向索引0处
 */
private void ensureCapacity(int capacity)
{
    int oldCapacity = elements.length;
    if (capacity<=oldCapacity) return;
    System.out.println(oldCapacity);
    int newCapacity =oldCapacity + (oldCapacity>>1);
    E[] newElements = (E[]) new Object[newCapacity];

    //将老数组挪动到新到数组
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[(front + i) % elements.length];
    }
    elements = newElements;
    //挪动结束后 要把front索引清0
    front = 0;

}

Circle Queue可以优化的地方主要是

1
2
3
4
    private int getIndex(int index)
    {
      return (front + index) % elements.length;
    }
1
2
3
//要求m<2n n>0
m%n
(m>=n) ? m-n:n

实现功能:能够在双端(front&rear)进行删除和添加操作,对应LinkedList

实现方法:使用链表实现time complexity为O(1)

Queue涉及到的算法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
    /**
     * 元素数量
     * @return
     */
    public int size()

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty()

    /**
     *从front入队
     */
    public void enQueueFront(E element)
       
    /**
     *从rear入队
     */
    public void enQueueRear(E element)

    /**
     * 出对 从front出对
     */
    public E deQueueFront()    
    
    /**
     * 出对 从rear出对
     */
    public E deQueueRear()

    /**
     * 获取对头元素
     * @return
     */
    public E getFront()
      
    /**
     * 获取队尾元素
     * @return
     */
    public E getRear()

    /**
     * 清空queue
     */
    public void clear()    

实现功能:可以从front入队和出对和rear入队和出对的循环队列

实现方式:使用动态数组实现(需要一个索引front指明对头的位置还需要一个数组字段)

循环的含义:接下来不会直接扩容 会将0和1位置填满后再进行扩容

双端循环队列和循环队列的不同点在于:双端循环队列在front可以插入元素,这就导致了插入算法的设计要添加

CircleQueue涉及到的算法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
    /**
     * 元素数量
     * @return
     */
    public int size()

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty()

    /**
     *从front入队
     */
    public void enQueueFront(E element)
       
    /**
     *从rear入队
     */
    public void enQueueRear(E element)

    /**
     * 出对 从front出对
     */
    public E deQueueFront()    
    
    /**
     * 出对 从rear出对
     */
    public E deQueueRear()

    /**
     * 获取对头元素
     * @return
     */
    public E getFront()
      
    /**
     * 获取队尾元素
     * @return
     */
    public E getRear()

    /**
     * 清空queue
     */
    public void clear()
      
     /**
     * 扩容
     */
     private void ensureCapacity(int capacity)
       

(同循环队列)

考虑普通rear入对

1
2
3
4
        elements[(front-1)%elements.length] = element;

                front--;
                size++;

假设front == 0;

1
2
3
        elements[(front-1)+elements.length] = element;
                front--;
                size++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
算法分析:
1.索引合法性检查
2.在真实索引-1(如果用SequenceList来看就是-1位置)插入(这里将索引转化公式封装)
3.将front索引指向第一个元素
4.size++
*/
    public void enQueueFront(E element)
    {
        //索引合法性检查
        ensureCapacity(size+1);
        //使用索引转化公式得到-1处的索引位置
        elements[getIndex(-1)] = element;
        //将front索引指向第一个元素
        front = getIndex(-1);
        size++;
    }

截屏2022-01-09 下午8.00.18
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
算法分析:
1.如果index<0直接用front + index +elements.length即可
2.否则使用普通的索引转化公式
@param index表示以0作为开头时插入位置
@return 返回的是以front作为开头时的插入位置
*/
private int getIndex(int index)
    {
        index+=front;
        //如果front在0位置
        if (index<0)
        {
            return index + elements.length;
        }
        return index%elements.length;
    }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    /**
     * 算法分析:
     1.保留要删除的元素
     2.将其要删除位置置为空
     3.将front遇到
     4.size--
     5.返回删除的元素
     */
    public E deQueueFront()
    {
        E e = elements[getIndex(0)];
        elements[getIndex(0)] = null;
        front = getIndex(1);
        size--;
        return e;
    }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/**
 * 算法分析:
     1.保留要删除的元素
     2.将其要删除位置置为空
     3.size--
     4.返回删除的元素
 */
public E deQueueRear()
{
    E e = elements[getIndex(size-1)];
    elements[getIndex(size-1)] = null;
    size--;
    return e;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    /**
     * 扩容算法和circle queue的扩容算法一样
     */
    private void ensureCapacity(int capacity)
    {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        int newCapacity = oldCapacity +(oldCapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[getIndex(i)];
        }
        elements = newElements;
        front =0;
    }