【算法】实现栈和队列

小说:怎样用电脑在家赚钱作者:宗纯更新时间:2019-02-22字数:50655

【算法】实现栈和队列


栈(stack)

栈(stack)是一种后进先出(LIFO)的集合类型, 即后来添加的数据会先被删除
 

 

可以将其类比于下面文件的取放操作:新到的文件会被先取走,这使得每次取走的文件都是最新的。

 

 
栈可以用数组或者队列去实现
下面要实现的栈的API如下图所示:
 

 

 

用数组实现栈

下面我们通过数组实现一个指定了初始容量,但随着元素的增加能够动态地扩张容量的栈。注意: 因为数组指定大小后不可改变, 所以我们要定义自动扩大栈容量的操作
public class ArrayStack<Item> {
  // 栈元素的总数
  private int N = 0;
  // 存放栈元素的数组
  private Item [] items;
  public ArrayStack (int M) {
    items = (Item[]) new Object[M];
  }
  /**
   * @description: 调整栈的大小
   */
  private void resize (int max) {
    Item [] temp = (Item [])new Object[max];
    for (int i =0;i<items.length;i++) {
      temp[i] = items[i];
    }
    items = temp;
  }
  /**
   * @description: 向栈顶插入元素
   */
  public void push (Item item) {
    // 当栈满了的时候, 将栈的数组大小扩大为原来两倍
    if (N==items.length) resize(2*N);
    items[N++] = item;
  }
  /**
   * @description: 从栈顶删除元素,并将删除的元素返回
   */
  public Item pop () {
    // 当栈还是空的时候, 不删除并且返回空
    if(isEmpty()) return null;
    // 保存将要被删除的元素
    Item i = items[N-1];
    // 将该元素删除
    items[N-1] = null;
    // 栈的长度减1
    N--;
    return i;
  }
 
  /**
   * @description: 判断栈是否为空
   */
  public boolean isEmpty () {
    return N == 0;
  }
  /**
   * @description: 返回栈的大小
   */
  public int size () {
    return N;
  }
 
  public static void main (String args []) {
    // 开始时指定栈的容量为2
    ArrayStack<Integer> stack = new ArrayStack<>(2);
    // 向栈顶依次添加3个元素
    stack.push(1);
    stack.push(2);
    stack.push(3);
    // 添加3后栈的容量自动扩大了
    // 依次从栈顶删除3个元素
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
  }
}

 

输出:
3
2
1

 

用链表实现栈

下面展示用链表实现的栈的代码, 注意: 添加和删除操作都是在链表的头部进行的
public class LinkedListStack<Item> {
  // 栈中元素的总数
  private int N = 0;
  // 链表头元素
  private Node front;
  // 内部结点类
  private class Node {
    Item item;
    Node next;
  }
  /**
   * @description: 向栈顶插入元素
   */
  public void push (Item item) {
    Node oldFront = front;
    // 向链表头部插入新的结点
    front = new Node();
    front.item = item;
    // 将新头结点的next指针指向旧的头结点
    front.next = oldFront;
    // 栈的长度加1
    N++;
  }
  /**
   * @description: 向栈顶删除元素,并将删除的元素返回
   */
  public Item pop () {
    // 当栈还是空的时候, 不删除并且返回空
    if(isEmpty()) return null;
    // 保存待删除的项以便返回
    Item item = front.item;
    // 删除原头结点
    front = front.next;
    // 栈的长度减1
    N--;
    return item;
  }
  /**
   * @description: 判断栈是否为空
   */
  public boolean isEmpty () {
    return N == 0;
  }
  /**
   * @description: 返回栈的大小
   */
  public int size () {
    return N;
  }
 
  public static void main (String args []) {
    // 创建栈
    LinkedListStack<Integer> stack = new LinkedListStack<>();
    // 向栈顶依次添加3个元素
    stack.push(1);
    stack.push(2);
    stack.push(3);
    // 依次从栈顶删除3个元素
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
  }
}

 

输出:
3
2
1

 

队列(queue)

队列属于一种遵循先进先出(FIFO)原则的集合类型,可以将其类比为生活中一些以公平性为原则的服务场景: 排成一排的客户等待服务,等待最久即最先入列的客户应该最先提供服务(出列)

 

 
 
实现队列也有两种方式,一种是链表, 另一种是循环数组
队列和栈在实现上的不同
  • 栈遵循后进先出的原则,所以要在数组或链表同一端做添加和删除操作
  • 队列遵循先进先出的原则, 所以要在数组或链表的两端分别做插入和删除的操作
 
我们要实现的队列API如下图所示:

 

 

通过链表实现队列

public class LinkedListQueue<Item> {
  // 链表中的结点数目
  private int N = 0;
  // 链表头结点
  private Node front = null;
  // 链表尾结点
  private Node rear = null;
  // 结点内部类
  private class Node {
    Item item;
    Node next;
  }
  /**
   * @description: 元素入列(在链表尾部添加)
   */
  public void enqueue (Item item) {
    Node oldRear = rear;
    rear = new Node();
    rear.item = item;
    if (isEmpty()) front = rear;
    else           oldRear.next = rear;
    N++;
  }
  /**
   * @description: 元素出列(在链表头部删除)
   */
  public Item dequeue () {
    if(isEmpty()) return null;
    Item item = front.item;
    front = front.next;
    N--;
    if(isEmpty()) rear = null;
    return item;
  }
  /**
   * @description: 判断队列是否为空
   */
  public boolean isEmpty () {
    return N == 0;
  }
  /**
   * @description: 返回队列长度
   */
  public int size () {
    return N;
  }
 
  public static void main (String args []) {
    LinkedListQueue<String> queue = new LinkedListQueue<>();
    queue.enqueue("A");
    queue.enqueue("B");
    queue.enqueue("C");
    queue.enqueue("D");
    System.out.println(queue.dequeue());
    System.out.println(queue.dequeue());
    System.out.println(queue.dequeue());
    System.out.println(queue.dequeue());
  }
}

 

输出:
A
B
C
D

 

头部删除-尾部添加 OR 头部添加-尾部删除?
在上面的代码中,我们是通过在链表尾部添加结点,在链表头部删除结点的操作实现队列, 那能不能通过在链表头部添加结点,在链表尾部删除结点的方式实现队列呢? 这是可以的,但并不是一个合适的做法,因为如果这样操作,在单向链表的条件下,需要将链表从头到尾迭代一遍才能实现删除操作,而我们通过上面的“头部删除-尾部添加”就能避免这种开销。
 
通过在链表头部添加结点,在链表尾部删除结点实现队列(不推荐)
  /**
   * @description: 元素入列(在链表头部添加)
   */
  public void enqueue (Item item) {
    Node oldFront = front;
    front = new Node();
    front.item = item;
    front.next = oldFront;
    if (isEmpty()) rear = front;
    N++;
  }
  /**
   * @description: 元素出列(在链表尾部删除)
   */
  public Item dequeue () {
    if (isEmpty()) return null;
    if (size()==1) {
      Item item = rear.item;
      front = null;
      rear = null;
      N--;
      return item;
    }
    Node x = front;
    while (!x.next.equals(rear)) {
      x=x.next;
    }
    Item item = x.next.item;
    x.next = null;
    rear = x;
    N--;
    return item;
  }

 

 

通过循环数组实现队列

除了链表之外, 另外一种实现队列的方式是循环数组。
为什么需要循环数组?
因为仅靠普通的数组实现队列可能会导致一个问题: 数组大量空位元素得不到利用。
例如下图所示, 在数组的实现方式中,我们会使用front和rear两个指针跟踪队列头部元素和尾部元素的位置,在动态的出列和入列操作中它们的位置会不断发生变化,随着出列操作fron指针t会不断后移(a->b->c->d), 当front和rear到达图d的状态时,我们发现:front前面的元素有一大段因为出列而腾出的空的元素没有得到利用,而此时又无法继续入列了(rear指针到达数组尾部,再次入列将导致数组越界的错误)

 

现在我们有一个方式可以解决这个问题: 将数组的头部和尾部连在一起,构成一个循环数组:

 

 
代码如下图所示, 可以看到,实现循环的关键是使用的一个取余数的操作,使得指针在移动到数组尾部的时候,能够重新移动到数组的头部:
 
public class CircleArrayQueue<Item> {
  // 队列元素总数
  private int N = 0;
  // 数组长度
  private int M;
  // 队列头部元素指针
  private int front = 0;
  // 队列尾部元素指针
  private int rear = 0;
  private Item [] items;
  public CircleArrayQueue (int M) {
    this.M = M;
    items = (Item [])new Object[M];
  }
  /**
   * @description: 入列操作
   */
  public void enqueue (Item item) {
    // 当队列为空时, 不能进行入列操作
    if (isFull()) return;
    // 向队列尾部插入元素
    items[rear] = item;
    // 用数组长度M取余, 使得rear到达数组尾部时能返回数组头部
    rear = (rear + 1) % M;
    // 增加队列长度
    N++;
  }
  /**
   * @description: 出列,并返回被删除项
   */
  public Item dequeue () {
    // 当队列为满时, 不能进行出列操作
    if (isEmpty()) return null;
    // 保存待删除元素, 以待返回
    Item item = items[front];
    // 删除队列头部元素
    items[front] = null;
    // 用数组长度M取余, 使得front到达数组尾部时能返回数组头部
    front = (front + 1) % M;
    // 减少队列长度
    N--;
    // 返回删除元素
    return item;
  }
  /**
   * @description: 判断队列是否满了
   */
  public boolean isFull () {
    return N == M;
  }
  /**
   * @description: 判断队列是否为空
   */
  public boolean isEmpty () {
    return N == 0;
  }
  /**
   * @description: 返回队列元素总数
   */
  public int size () {
    return N;
  }

  public static void main (String args []) {
    CircleArrayQueue<Integer> queue = new CircleArrayQueue<>(3);
    // 依次入列三个元素
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    // 依次出列三个元素
    System.out.println(queue.dequeue());
    System.out.println(queue.dequeue());
    System.out.println(queue.dequeue());
  }
}

 

 

输出:
1
2
3

 

判断循环数组的满状态和空状态

在循环数组的实现中,一个非常重要的操作就是区分数组是处在"满"状态还是“空”状态,因为当front和rear指向同一个元素位置时,既可能处在满状态也可能处在空状态。上面的代码里我们是通过一个表示队列元素总数的变量N去判断的,除此之外,我们也可以通过另外一种不依赖于变量N的方式去判断数组的满和空的状态, 但代价是少用一个元素空间,例如:
(下面的代码除了isEmpty和isFull外都和上面相同)
public class CircleArrayQueue2<Item> {
  private int M;
  private int front = 0;
  private int rear = 0;
  private Item [] items;
  public CircleArrayQueue2 (int M) {
    this.M = M;
    items = (Item [])new Object[M];
  }
 
  public void enqueue (Item item) {
    if (isFull()) return;
    items[rear] = item;
    rear = (rear + 1) % M;
  }
 
  public Item dequeue () {
    if (isEmpty()) return null;
    Item item = items[front];
    items[front] = null;
    front = (front + 1) % M;
    return item;
  }
 
  public boolean isFull () {
    return (rear + 1) % M == front;
  }
 
  public boolean isEmpty () {
    return rear == front;
  }
 
  public static void main (String args []) {
    CircleArrayQueue2<Integer> queue = new CircleArrayQueue2<>(3);
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    System.out.println(queue.dequeue());
    System.out.println(queue.dequeue());
    System.out.println(queue.dequeue());
  }
}

 

输出:
1
2
null

 

由输出可看出, 在数组长度为3时, 我们实际上只能有2个元素位置去存储队列元素
 
【完】
 
 

当前文章:http://ayzwzx.cn/77357.html

发布时间:2019-02-22 00:05:33

致富网赚论坛 传奇手游赚钱是真的吗 真实的网络赚钱方法 淘宝返利购买什么意思 淘宝客佣金90%产品 联联周边游挣钱吗 梦幻手游大熊猫2018 快手西瓜是多少钱 智能cpa自动赚钱系统 卖家中心在淘宝哪里

47167 32177 31659 98742 45646 3954269058 51187 35578

我要说两句: (0人参与)

发布