程序员必看:实现栈有这两种策略,有完整分析和代码实现|C#教程

金沙澳门官网网址:www.js333com

VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > c#教程 >
  • 程序员必看:实现栈有这两种策略,有完整分析和代码实现

本站最新发布   C#从入门到精通
试听地址  
/eschool/CSharp奥门金沙网址/

程序员必看

1
回顾

普林斯顿大学的程序员必知的算法和数据结构已经推送两篇:

1. 程序员必知的算法和数据结构:2500字性能总结

2. 1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

 

这两篇中分别总结了程序的时间性能度量指标,典型的时间复杂度类型,Java中类型的空间消耗的量化情况。后一篇考虑计算机中最重要的基础算法查找和排序算法,这篇可以说是浓缩篇,虽只有1800字,但是绝对的精华。

 

2
栈的核心问题

今天来认识一对非常重要的数据结构:栈(stack)和队列(queue),分为两篇,接下来另一篇推送队列。

 

相比大家对栈(stack)的基本知识都已经了解了,我们在此直接进入核心问题:栈这个数据结构和行为是怎么实现的?

 

首先认识一下,栈的基本行为,基本包括如下四个方法:

 

 

3
栈的数组实现

用数组表示栈结构是最简单的主意,维护一个实例变量 n, 表示栈中元素的个数;维护一个数组 items[] 存储 n 个元素,栈顶元素存储在 items[n-1] , 栈底元素存储在 items[0]. 这种存储策略方便地实现了栈的后进先出性质。

 

 

4
代码实现

ArrayStackOfStrings 的代码实现包括继承可迭代接口,编写4个基本方法,都很简洁,内部借助数组和个数,内部类 ReverseArrayIterator 实现可迭代接口。

 1import java.util.Iterator;
 2import java.util.NoSuchElementException;
 3   //继承可迭代接口
 4public class ArrayStackOfStrings implements Iterable<String{
 5    private String[] items;  // 内部存储数组
 6    private int n;           // 栈内元素个数
 7
 8    public ArrayStackOfStrings(int capacity) {
 9        items = new String[capacity];
10    }
11
12    public boolean isEmpty() {
13        return n == 014    }
15
16    public boolean isFull() {
17        return n == items.length; 
18    }
19
20    public void push(String item) {
21        items[n++] = item; //直接在数组最后添加元素
22    }
23
24    public String pop() {
25        return items[--n]; //直接在数组最后移除元素
26    }
27
28    public Iterator<String> iterator() {
29        return new ReverseArrayIterator();
30    }
31
32    // 自定义的迭代器,不实现Remove接口
33    private class ReverseArrayIterator implements Iterator<String{
34        private int i = n-1;
35        public boolean hasNext()  return i >= 0; }
36        public void remove()      throw new UnsupportedOperationException();  }
37           //可以看出栈的遍历是从索引n-1开始
38        public String next() {
39            if (!hasNext()) throw new NoSuchElementException();
40            return items[i--];
41        }
42    }
43
44       //测试
45    public static void main(String[] args) {
46        int capacity = Integer.parseInt(args[0]);
47        ArrayStackOfStrings stack = new ArrayStackOfStrings(capacity);
48        while (!StdIn.isEmpty()) {
49            String item = StdIn.readString();
50            if (!item.equals("-")) {
51                stack.push(item); 
52            }
53            else {
54                StdOut.print(stack.pop() + " ");
55            }
56        }
57        StdOut.println();
58    } 
59

 

5
能动态扩容的栈的实现方法

 

上面实现方法数组个数,即容量写死了,所以一旦数组个数超过容量,将会抛出异常。

 

为了实现数组元素个数的动态扩容,本方法实现的功能即可做到。

 

相比上面方法,此方法在 push 时候,考虑是否容积足够,如果不够,则开辟元素个数加倍的空间。相似的,如果 pop 时候,如果容积够大,对容积减半。

 

 

6
代码实现

 

重点理解 resize()函数,做的事情不仅个数加倍,还要copy原来的元素到新的内存区域,因此此处效率不高。

 1import java.util.Iterator;
 2import java.util.NoSuchElementException;
 3
 4public class ResizingArrayStackOfStrings implements Iterable<String{
 5    private String[] items;     // 同上
 6    private int n = 0;          // 同上
 7
 8    // create an empty stack
 9    public ResizingArrayStackOfStrings() {
10        items = new String[2]; //开始初始容积为2
11    }
12
13    public boolean isEmpty() {
14        return n == 0;
15    }
16
17    public int size() {
18        return n;
19    }
20
21
22    // resize the underlying array holding the elements
23    private void resize(int capacity) {
24        assert capacity >= n;
25        String[] temp = new String[capacity];
26        for (int i = 0; i < n; i++)
27            temp[i] = items[i];
28        items = temp;
29    }
30
31    // push a new item onto the stack
32    public void push(String item) {
33        if (n == items.length) resize(2*items.length);  // double array length if necessary
34        items[n++] = item;                              // add item
35    }
36
37    // delete and return the item most recently added
38    public String pop() {
39        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
40        String item = items[n-1];
41        items[n-1] = null;        // to avoid loitering
42        n--;
43        // shrink size of array if necessary
44        if (n > 0 && n == items.length/4) resize(items.length/2);
45        return item;
46    }
47
48
49    public Iterator<String> iterator() {
50
  
相关教程
        
Baidu
sogou