week2——Stacks and Queues

声明

本文是博主在Coursera学习时所写的学习笔记，如有错误疏漏还望各位指正。

欢迎交流讨论

如果大家转载，请注明本文地址！

Stacks

• 简介

  • 栈是限定仅在表头进行插入和删除操作的线性表。其限制是仅允许在表的一端进行插入和删除运算。
  • 课程中以存储String的栈为例

• 属性

  public StackOfStrings

  函数	功能
  StackOfStrings()	构造函数
  void push(String item)	向栈中添加一个元素
  String pop()	删除并返回栈顶元素
  boolean isEmpty()	返回栈是否为空
  int size()	栈里有多少元素

  最后一个属性可有可无，其余属性是栈必需的

• 实现方法

  • 用链表表示

    • 原理 :

      • 始终保持指向链表的第一个节点。对第一个节点进行删除/插入
      • push(): 创建一个新节点，使之指向原来的栈顶，并使之成为栈顶
      • pop(): 删除栈顶节点，使其相邻节点成为栈顶节点
        

    • 代码实现

    • 分析

      • 时间复杂度：每个操作的时间复杂度是常数

      • 内存: 含N个元素的栈占用内存约 $40N$bytes(栈所占用的内存，不包括字符串的内存)

        

  • 数组表示

    • 原理

      • 使用数组s[]来存储元素
      • push(): 给s[N]赋值
      • pop(): 删除s[N-1]

    • 代码实现

  • 可变长的数组表示

    • 原理

      • push()：数组长度 +1
      • pop() ：数组长度 -1

    • 实现

      每次创建一个新数组，长度加/减一，并将原来数组拷贝到新数组
      这样时间复杂度为$1 + 2 + 3 +...+N$ ~ $\dfrac{N^2}{2}$
      我们可以试着改进：
      每次数组满的时候，创建一个大小为原来两倍的数组并拷贝，
      这样时间复杂度为：$N + 2+4+...+N$ ~$3N$
      其中第一个N是每次操作都需要访问数组一次

    • 代码实现

示例代码一

public class LinkedStackOfStrings
{private Node first = null;//私有内部类private class Node{String item;Node next;}public boolean isEmpty(){ return first == null; }public void push(String item){Node oldfirst = first;first = new Node();first.item = item;first.next = oldfirst;}public String pop(){String item = first.item;first = first.next;return item;}
}

示例代码三

public class FixedCapacityStackOfStrings {
    private String[] s;private int N = 0;public FixedCapacityStackOfStrings(int capacity){ s = new String[capacity]; }public boolean isEmpty(){return N == 0;}public void push(String item){ s[N++] = item; }public String pop(){s[--N]; }
}

示例代码三

public class ResizingArrayStackOfStrings {
    private String[] s;private int N = 0;public ResizingArrayStackOfStrings(){ s = new String[1]; }public boolean isEmpty(){return N == 0;}public void push(String item){if (N == s.length) resize(2 * s.length);s[N++] = item;}   public String pop(){s[--N]; }private void resize(int capacity){String[] copy = new String[capacity];for (int i = 0; i < N; i++)copy[i] = s[i];s = copy;}}

Queue

• 简介

  在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。

• 属性

  public class QueueOfStrings

  函数	功能
  QueueOfStrings()	创建一个新队列
  void enqueue(String item)	向队列中插入一个新元素
  String dequeue()	删除并返回队列中最先插入的元素
  boolean isEmpty()	判断队列是否为空
  int size()	返回队列中元素的个数 *

  除最后一个其余的属性都是队列所必需的

• 代码实现

public class LinkedQueueOfStrings
{private Node first, last;private class Node{ String item;Node next; }public boolean isEmpty(){return first == null; }public void enqueue(String item){Node oldlast = last;last = new Node();last.item = item;last.next = null;if (isEmpty()) first = last;else oldlast.next = last;}public String dequeue(){String item = first.item;first = first.next;if (isEmpty()) last = null;return item;}
}

删除和插入函数与栈有些不同，需要对队列为空的情况进行特殊处理

应用

栈和队列在计算机中有许多的应用，栈可以用计算算术表达式，队列和与用于广度优先遍历二叉树，有兴趣的朋友可以试一下。