数据结构与算法(3)----->队列和栈

时间:2020-12-05 14:40:35

1. 栈和队列的基本性质

  1. 栈是先进后出;(像是子弹夹,后进先打出)
  2. 队列是先进先出;(像是平时排队买冰淇淋,按顺序轮流)
  3. 栈和队列在实现的结构上可以有数组和链表两种形式;

    (1)数组结构实现容易;

    (2)用链表结构较为复杂,因为牵扯很多的指针操作;

1.1  栈结构的基本操作

(1)pop操作;(弹出)

(2)top或peek操作;

(3)push操作;(压栈)

(4)size操作;

1.2  队列的基本操作

(1)队列的基本操作与栈操作不同的是,push操作作为在队头加入元素;而pop操作是从队列尾部弹出一个元素;

(2)队列和栈的基本操作,都是时间复杂度为O(1)的操作;

  特殊:

  1. 双端队列结构:为首尾都可以压入和弹出元素;
  2. 优先级队列结构:会根据元素的优先级值,决定元素的弹出顺序;其本质是一个堆结构,并不是线性结构;