关于算法:Algorithms-普林斯顿知识点熟记-Stacks-and-Queues

Stacks and Queue

一、基本概念

• 堆栈：检测最初退出的对象。后进先出，插入元素又叫入栈（push），去掉最近退出的元素又叫出栈（pop）。
• 队列：检测最先退出的对象。先进先出，插入元素又叫入队（enqueue），去掉最近退出的元素又叫出队（dequeue）。

二、stacks：基于链表实现

指针始终指向链表的第一个节点，在最后方进行插入和删除操作

以字符串为存储对象的 stacks 举例

stack 须要实现的 API

外部类

private class Node 
{ 
    String item;
    Node next;
}

pop 出栈操作
1、保留头节点中存储的对象

String item = first.item;

2、扭转指针指向下一个节点（本来的头结点会被垃圾回收器回收）

first = first.next;

3、返回 1 中保留下来的对象

return item;

push 入栈操作

1、创立一个新指针指向以后的头结点

Node oldfirst = first

2、创立一个新的头节点，并将 first 指针指向该节点

first = new Node();

3、给新节点设置实例变量

first.item = "not"
first.next = oldfirst

三、stacks：基于链表实现的性能体现

1. 工夫：因为没有 for 循环，每个办法都只有个别指令，因而是常数项的复杂度
2. 空间：节点数为 N，则内存占用 ~40N 字节：

四、stacks：基于数组实现

基于数组实现的缺点
数组是有容量的，存储的数量可能超过容量，须要对其进行解决。

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) 
    // 应用以后索引插入数组，而后递增 N
    {s[N++] = item; } 
    public String pop() 
    // 递加 N，而后应用索引拜访数组元素
    {return s[--N]; } }

五、对于 stacks 数组实现更多的思考

数组的上溢和下溢
下溢 (Underflow)：从空堆栈中进行 pop 操作会抛出异样
上溢(Overflow)：扩容数组容量（resizing array）

空值: 容许空值插入

对象游离(loitering)