栈(stack)

栈(stack)是限制插入和删除操作只能在末尾位置上进行的表,该末尾成为栈的顶(top)。是一种后进先出的表(LIFO,Last In First Out)。

栈

栈的实现

  • 链表实现:使用单向链表实现
  • 数组实现:使用数组实现,是更加常用的方式。由C++中的vector中的back、push_back和pop_back可以很简单地实现一个栈。每个栈需要一个用于存储栈数据的数组(stackArray)和一个记录栈顶索引的值(topOfStack)(当空栈时索引为-1)

常用操作

  • push:入栈操作,将topOfStack+1,然后令stackArray[topOfStack]=newElement;
  • pop:出栈操作,outElement=stackArray[topOfStack],然后将topOfStack-1
  • top:返回栈顶元素,返回stackArray[topOfStack]

所有操作均为常数时间O(1)运行

队列(Queue)

队列也是表,是一种先进先出(First In First Out,FIFO)的数据结构,入队列的一端成为队尾,出队列的一端成为队头。

队列
队列

队列的实现

队列也可以使用链表来实现,但通常使用循环数组来实现。

一个队列需要一个用于存储队列中数据的数组queueArray和两个位置front、back,用于记录队列的两端。为了判定队列是否空还是满,通常还增设一个元素currentSize来记录队列中现有的元素个数。

常用操作

  • enqueue:入队列

    1
    2
    3
    back = (back+1)%queueArray.size();
    queueArray[back]=newElement;
    currentSize++;
  • dequeue:出队列

    1
    2
    3
    outElement = queueArray[front];
    fornt = (front+1)%queueArray.size();
    currentSize--;
  • back:返回队尾元素,直接返回queueArray[back]

  • front:返回队头元素,直接返回queueArray[front]

以上操作均以常数时间O(1)运行