数据结构--栈和队列学习小结

学习内容

栈 (Stack)

栈（stack）又名

堆栈

，它是一种

运算受限

的

线性表

。限定仅在

表尾进行插入

和

删除

操作的线性表。这一端被称为

栈顶

，相对地，把另一端称为

栈底

。向一个栈插入新元素又称作

进栈、入栈或压栈

，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作

出栈或退栈

，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

稍微介绍一下关键名词：

运算受限：也就是这个表你不能随便的删除插入。只能按照它的规则进行插入删除。比如栈就只能在一端就行插入和删除。同样，队列也是运算受限，只能在两天操作。

线性表：栈也是一种线性表，前面详细介绍过线性表，它表达的是一种数据的逻辑关系。也就是在栈内各个元素是相邻的。当然在具体实现上也分

数组和链表实现

，他们的物理存储结构不同。但是逻辑结构(

实现的目的

)相同。

栈顶栈底： 这个描述是偏向于逻辑上的内容，因为大家知道

数组在末尾插入删除

更容易，而

单链表通常在头插入删除

更容易。所以数组可以用末尾做栈顶，而链表可以头做栈顶。

Stack这种数据结构应用很广泛，比如你的程序执行查看调用堆栈、加减运算、甚至在搜索算法中dfs，替代递归等等。 在计算机的使用中，大量的运用了栈，比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作（Undo）、浏览器中的回退操作，编译器中的函数调用实现等等。

栈的实现

接口	说明	复杂度
void push(E e)	向栈中加入元素	O(1) 均摊
E pop()	弹出栈顶元素	O(1) 均摊
E peek()	查看栈顶元素	O(1)
int getSize()	获取栈中元素个数	O(1)
boolean isEmpty()	判断栈是否为空	O(1)

说明：push和pop操作在最后面进行，有可能触发resize，但均摊来算是O(1)的。

栈的实现可以通过 数组 或者 链表 实现，在这里我们使用 数组来实现上述接口。

/**
  * 基于动态数组的栈
  *
  * @param <E>
  */
 public class ArrayStack<E> extends Array<E> implements Stack<E> {
 
    private Array<E> array;
 
    public ArrayStack(int capacity) {
        this.array = new Array<>(capacity);
    }

    public ArrayStack() {
        this.array = new Array<>();
    }

    @Override
    public void push(E e) {//O(1)
        array.addLast(e);
    }

    @Override
    public E pop() {//O(1)
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    @Override
    public int size() {
        return array.getSize();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack:");
        res.append("[");
        for (int i = 0; i < size(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(", ");
            }
        }
        res.append("] top");
        return res.toString();
    }
}
           

队列 Queue

队列是一种特殊的

线性表

，特殊之处在于它只允许在表的

前端（front）

进行删除操作，而在表的

后端（rear）

进行插入操作，和栈一样，队列是一种

操作受限制

的线性表。进行插入操作的端称为

队尾

，进行删除操作的端称为

队头

。

队头front： 删除数据的一端。对于数组，

从后面插入更容易，前面插入较困难

，所以一般用数组实现的队列队头在前面。(删除直接index游标前进，不超过队尾即可)。而对于链表。插入删除在

两头分别进行

那么

头部(前面)删除尾部插入

是最方便的选择。

队尾rear： 插入数据的一端，同上，在数组和链表中

通常均在尾部位置

。当然，其实数组和链表的front和rear还有点小区别，后面会具体介绍。

enQueue(入队)： 在

队尾

rear插入元素

deQueue(出队)： 在

对头

front删除元素

队列的应用可以在播放器上的播放列表，数据流对象，异步的数据传输结构(文件IO，管道通讯，套接字等)上体现，当然最直观的的就是排队了。

队列的实现

接口	说明	复杂度
void enqueue(E e)	入队	O(1) 均摊
E dequeue()	出队	O(n)
E getFront()	获取队首元素	O(1)
int getSize()	获取队列元素个数	O(1)
boolean isEmpty()	判断队列是否为空	O(1)

入队是从队尾开始，有可能触发resize，因此均摊下来是O(1)。出队是在队首，数组实现每次都要挪动所有元素,O(n)。

import datastructure.array.Array;
 /**
  * 动态队列结构
  *
  * @param <E>
  */
 public class ArrayQueue<E> implements Queue<E> {
     private Array<E> array;

    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayQueue() {
       this(10);
   }

    @Override
   public void enqueue(E e) {
        array.addLast(e);
    }

    /**
    * 每次移除的是数组的第一个，会导致所有数据的移动 性能低效
     */
    @Override
    public E dequeue() {
        if (isEmpty()) return null;
        return array.removeFirst();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

   @Override
    public int size() {
        return array.getSize();
    }

    @Override
    public E getTopQueue() {
        return array.get(0);
    }

    @Override
    public String toString() {
       StringBuilder res = new StringBuilder();
        res.append("Queue: \n");
       res.append("top: ");
        for (int i = 0; i < size(); i++) {
            res.append(array.get(i));
            if (i < size() - 1) {
                res.append(", ");
            }
        }
        return res.toString();
    }

    public static void main(String[] args) {
//        ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
       System.out.println("求余："+1%2);
   }
}
           

学习小结

栈和队列的比较：

相同点：从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。

不同点：栈是限定只能在表的一端进行插入和删除操作的线性表。 队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"限定"。

最后一点点感悟就是不要为了使用数据结构而使用数据结构。举个例子，之前看到过一个数组反转的问题，刚学过Stack可能会想，这个简单啊，直接将字符串挨个的Push进去，然后Pop出来就可以了，完美的解决方案。但是，这是不是最有效地呢，其实有更有效地方法，那就是以中间为对折，然后左右两边替换