找到
3
篇与
数据结构
相关的结果
-
我是一棵“树” 我是一颗树，之前我们数据结构家族中的一个小朋友——“栈” 已经给你们介绍过的我们这个家族了（我是一个“栈”）。之所以叫栈为小朋友，是因为我和他的爸爸——数组是平辈的。 之所以存在我们这样一个家庭，最主要的原因是数组他们家庭虽然很强大，但是有一定的局限性。大家都知道，无论是数组、链表以及他们家的那几个小娃娃（栈、队列）等，存储的数据之间都只有简单的前后顺序关系。 既然说到这了，那就在给你们科普一下整个数据结构大家族吧。毕竟你们认识的那个“栈”只是个小晚辈，对我们家族的历史什么的都不是很了解。 数据结构，主要有两个作用，第一个是存储数据，第二个是可以反应所存储的数据之间的逻辑关系，注意，逻辑关系并不是他们在计算机中存储的物理位置关系哦。所以，根据大家存储的数据的逻辑结构的不同，主要可以分为这个几个大的分支： 集合 他们家帮别人存储的数据之间什么关系都没有，唯一的关系可能就是同处于同一个集合了。 线性结构 他们家呢，帮别人存储的数据之间是有顺序的，数据之间在逻辑上是首尾相接的连续保存的。所以，元素之间存在着一对一的关系。比如你们认识的数组家族，就是线性结构的。 树形结构 嘿，这就是我们的家族啦，我们存储元素存在着一对多的相互关系。 图形结构 图形结构分支是一种复杂的数据结构。数据元素间的关系是任意的。任意两个数据元素间均可相关联。 大家了解的数组、队列、栈、链表他们都属于线性结构的分支的。今天的主角，也就是我和我的“树”家族是树形结构这个大的分支中的。 也许你已经猜到了，我是整个数据结构大家族的树形结构这一分支的族长。作为一个庞大的家族分支，我们当然具备整个数据结构家族的基本功能——数据存储。另外，整个树形分支主要用来保存具有树形结构的数据集合。说的白一点，就是我们帮别人存储的数据是有层次关系的。就像自然界中的一颗倒置的树一样。 先来说下找我们保存数据的一些限制和要求吧。我们帮别人保存的每个元素我们称之为节点，而我们一般有一个特定的结点被称为根节点，其余的结点都叫非根节点。下面给你看一颗标准的树，然后通过这张图，再来介绍下什么是叶节点、父节点等概念。 H节点是O和L的父节点，O和L是H节点的子节点。 H节点是根节点，因为他没有父节点。 I、S和L节点是叶结点，因为他们没有子节点。 I和S是兄弟节点，因为他们的父节点都是O节点。 好了，说好了这些了，该带你见一见我的家族成员了。作为数据结构的树家族的大家族，我有很多后代。先来给你看下我的家谱： 我有两个儿子：小儿子有序树、大儿子无序树。大儿子是家族的顶梁柱，承担起了家族的很多工作。而我的小儿子，就是一个比较自由的孩子，无忧无虑的什么也不管，所以大家有时候也叫他自由树。 先来说说这个我十分宠爱的小儿子——无序树。 无序树 无序树，他也是个树形结构，除了树中的父子节点之间有关系以外，同一个父节点的所有子节点之间是没关系的，在树中，这种关系就是顺序，比如谁在前谁在后。所以，他叫无序树。另外，我的这个小儿子由于太过自由，至今都没给我生出个娃娃来。所以，我的小儿子是个孤家寡人。 再来详细说说他的数据存储方面的事情，前面说了，他存储的数据之间只有父子节点间有关系。如果你让他帮你存储A、B、C三个数据的话，1个父节点，2个子结点的情况有 3 种。 无论两个子节点位置关系如何，都是同一棵树。即A-B-C和A-C-B被认为是同一棵树。 有序树 再来介绍一下我的大儿子，整个树家的顺位继承人。他真的做到了一个长子应该做的所有事情，他和他的孩子们几乎包揽了树家族的所有工作内容。 他和无序树的区别比较明显，就是在有序数中，子节点之间是有顺序关系的。如果你让我的大儿子帮你存储A、B、C三个数据的话，1个父节点，2个子结点的情况有 6 种。 只要两个节点的顺序掉换一下，又是一个新的树。A-B-C和A-C-B被认为是两棵不同的树。 从上面的家族图谱中可以发现，我的大儿子有序树也有很多孩子的。其中我比较出名的三个孙子分别是二叉树、霍夫曼树和B树等。 现在的年轻人，都很有个性的，帮别人存储数据的时候都有很多要求呢，不过也好，年轻人嘛，就应该有点性格。也得益于他们的各自的特性，树家族才能如此强大。 关于有序树的几个晚辈的介绍，后面让他们自己来吧，我这把老骨头说了这么多也累了。
-
我是一个栈 我是一个栈，先来跟你介绍一下我的家族，我的家族是一个很古老的家族，家族成员很多，外界称呼我们这个家族为数据结构。我们是计算机世界中存储和组织数据的。数据结构家族在计算机世界中是至关重要的，因为我们家族功能的强大，现代编程语言及其API中都有我们家族成员的身影。 我的家族是一个庞大的家族。家族中也有几大分支，比如说树、图、堆、散列表等。各个分支都有不同的能力，所以很多人选择适当的数据结构是一项很重要的工作。我们家族和算法家族是世交，基本上所有重要场合两家都会一起出现。 我叫栈，我的爸爸叫数组，我的妈妈叫链表，我的双胞胎弟弟叫队列。我们这个家庭是整个数据结构家族中比较重要的家庭。 和你说过了，我们数据结构家族是计算机世界中储存和组织数据的。我的家族之所以这么强大，就是因为我们要应付各种需求，提供不同的数据存储方式。我的四个家庭成员分别可以解决不同的数据存取需求。 数组 说起我的爸爸——数组，他是数据结构家族的族长，人们都说他是数据结构大家族的根基。很多编程语言都内置数组。爸爸是个很富有的人，他有很多土地。每当有人找他来存储数据的时候，他都会预先划分出一块连续的土地（连续的内存），然后把别人交给他的数据按顺序存储在这些连续的土地中，当别人来取这些数据的时候，需要提供给数组要取哪块土地中的数据（数组的位置索引），然后数组就可以直接去那块土地中把数据取出来，交给需要读取这个数据的人。并不是所有数据数组都能帮忙存储的，父亲只会帮别人存储相同类型的数据。 我的家族的所有人都支持几个基本的操作：插入、删除、读取。 因为数组爸爸在存储数据的时候，是按照顺序保存的，他保存数据的土地是一块一块相连的。那么，他的特点就是寻址读取数据比较容易，但是插入和删除比较困难。这个其实比较好理解。读取容易的原因是只要你告诉数组你要从哪块土地读取数据，他就会直接去那块土地中把数据取出来给你。插入和删除比较麻烦，主要是因为这些存储数据的空间都是连着的，比如编号为0-1-2-3-4这五块土地中都保存了数据，但是现在你要往1中插入一块数据，那就意味着从1开始，后面的所有土地中的数据都要往后移一个位置。这是很大的工作量啊。 链表 人们都说，男女搭配，干活不累。由于数组爸爸有寻址容易，插入和删除困难的问题，他在找老婆的时候特意找了一个和自己互补的姑娘——链表。链表妈妈的特点正好是寻址困难，插入和删除容易。 在帮助别人存储数据这件事上，链表的方式和数组有很大不同。数组是提前划分了一大片连续的土地，用来存储数据。但是链表不是这么做的，因为链表妈妈家里并没有数组爸爸家里那么富有。他的数据存储并不是连续的，能这么做的原因是妈妈存储数据的土地中有两块区域，一块用来保存数据，一块用来记录下一个数据保存在哪块土地中（指针）。这样，别人找他存储数据的时候，她就要根据指示先找到下一块空余的土地，然后把数据保存在里面。链表这样的数据存储方式可以把一些碎片空间利用起来。 通过上面的这种保存数据的方式，链表在插入和删除数据的时候比较容易，比如编号为0-1-2-3-4这五块土地中都保存了数据，但是现在你要往1中插入一块数据，那么只需要依次更改0号土地和1号土地中记录下一块土地地址的值就行了。对于其他的数据存储没有任何影响。但是，如果你想从数据中取出一块数据那可就麻烦了，因为这意味着链表妈妈要帮你从第一块土地开始挨个帮你找。一直找到你要的数据为止。 我和我的胞弟 栈，也就是我，一个英俊潇洒的数据结构。我和队列是一堆孪生兄弟。我们两个都可以用数组和链表来实现。虽然是双胞胎，但是我们两个都是有性格的，我们要求别人存储数据和取出数据的顺序要按照我们的规矩来。 我的原则是：先进后出（栈） 弟弟的原则是：先进先出（队列） 我给你举个例子你就明白了，我和弟弟每个人都有一个管子，用来帮你们保存数据，当然这个管子可能是用数组爸爸是实现的也可能是链表妈妈实现的。我们握住管子的两头，我的这个管子只能通过管子左面的口子放入东西，也只能从左面的口子取出东西。右面的口子是不开的。而弟弟队列呢，他的管子的左面的口子放东西，管子的右面的口子取东西。 爸爸妈妈是如何生出我和弟弟的 上面说过了，栈和队列都是可以通过数组或者链表实现的。当然了，父母创造孩子，天经地义嘛。那么，先来看看我是如何实现的。作为一种数据结构，我接口有isEmpty()、size()、push()、pop()、peek()以及迭代。 先来看看如何通过数组实现栈： public class Stack implements Iterable { private Item[] a; // 数组表示栈，栈顶在最大的下标。 private int n; // 栈内元素的个数 /** * 初始化一个空栈 */ public Stack() { a = (Item[]) new Object[2]; n = 0; } /** * 判断栈内是否有元素 */ public boolean isEmpty() { return n == 0; } /** * 返回栈内元素个数 */ public int size() { return n; } // 改变栈的大小 private void resize(int capacity) { assert capacity >= n; // 注意不能直接创建泛型数组 Item[] temp = (Item[]) new Object[capacity]; for (int i = 0; i < n; i++) { temp[i] = a[i]; } a = temp; // 也可以选择下面这种方式改变数组大小 // a = java.util.Arrays.copyOf(a, capacity); } /** * 压入元素 */ public void push(Item item) { //先判断n的大小，如果栈满则改变栈的大小 if (n == a.length) resize(2*a.length); a[n++] = item; } /** * 弹出并返回元素 */ public Item pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); Item item = a[n-1]; a[n-1] = null; //防止对象游离 n--; // 如果有必要则调整栈的大小 if (n > 0 && n == a.length/4) resize(a.length/2); return item; } /** * 返回但不弹出栈顶元素 */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return a[n-1]; } /** * 返回一个可以进行先进后出迭代的迭代器 */ public Iterator iterator() { return new ReverseArrayIterator(); } // 用内部类实现迭代器接口，实现从栈顶往栈底的先进后出迭代，没有实现remove()方法。 private class ReverseArrayIterator implements Iterator { private int i; public ReverseArrayIterator() { i = n-1; } public boolean hasNext() { return i >= 0; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return a[i--]; } } /** * 测试 */ public static void main(String[] args) { Stack stack = new Stack(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) stack.push(item); else if (!stack.isEmpty()) StdOut.print(stack.pop() + " "); } StdOut.println("(" + stack.size() + " left on stack)"); } } 再来看看如何使用链表实现栈： public class Stack implements Iterable { private Node first; //栈顶节点 private int N; // 栈内元素数量 // 辅助类Node，用于形成链表 private static class Node { private Item item; private Node next; } /** * 初始化栈 */ public Stack() { first = null; N = 0; } /** * 判断栈是否为空 */ public boolean isEmpty() { return first == null; //return N == 0; } /** * 返回栈内元素数量 */ public int size() { return N; } /** * 压入元素 */ public void push(Item item) { Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; N++; } /** * 弹出元素 */ public Item pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); Item item = first.item; // 需弹出的元素 first = first.next; // 删除头节点 N--; return item; } /** * 返回但不弹出元素 */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return first.item; } /** * 从栈顶到栈底打印元素 */ public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) s.append(item + " "); return s.toString(); } /** * 实现Iterable接口 */ public Iterator iterator() { return new ListIterator(first); } // 实现Iterator接口用于迭代，没有实现remove方法 private class ListIterator implements Iterator { private Node current; //初始化时，current指向栈顶 public ListIterator(Node first) { current = first; } public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; } } /** * 测试 */ public static void main(String[] args) { Stack s = new Stack(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) s.push(item); else if (!s.isEmpty()) StdOut.print(s.pop() + " "); } StdOut.println("(" + s.size() + " left on stack)"); } } 同样作为数据结构的弟弟，也有些接口需要实现：isEmpty()、size()、enqueue()、dequeue()、peek()以及迭代。队列和栈不同的是，入列和出列是在两个地方，所以需要维护两个变量来表示队头和队尾。 使用数组实现队列： public class Queue implements Iterable { private Item[] q; private int N; // 队列中元素的数量 private int first; // 队头元素的下标 private int last; // 队尾元素的后一个位置的下标，也就是元素入列时可以放置的位置 /** * 初始化队列，此时头尾下标重合 */ public Queue() { q = (Item[]) new Object[2]; N = 0; first = 0; last = 0; } /** * 依旧用N判断队列是否为空 */ public boolean isEmpty() { return N == 0; } /** * 队列中元素数量 */ public int size() { return N; } // 调整数组大小 private void resize(int max) { assert max >= N; Item[] temp = (Item[]) new Object[max]; //注意这里：把N个元素放入总大小为max的队列（max>=N） //因为循环使用数组，从first开始的第i个元素可能保存在了first //前面（即last在first前面）。 for (int i = 0; i < N; i++) { temp[i] = q[(first + i) % q.length]; } q = temp; //把小队列按顺序复制到大队列后重置队头和队尾 first = 0; last = N; } /** * 元素入列 */ public void enqueue(Item item) { if (N == q.length) resize(2*q.length); q[last++] = item; // 元素入列 if (last == q.length) last = 0; // 如果last超出数组下标，把last置零，循环利用数组 N++; } /** * 元素出列 */ public Item dequeue() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); Item item = q[first]; q[first] = null; // 防止对象游离 N--; first++; if (first == q.length) first = 0; // 循环利用数组，下一个队头在下标为0的地方 if (N > 0 && N == q.length/4) resize(q.length/2); return item; } /** * 返回队头元素但不出列 */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); return q[first]; } /** * 实现Iterable接口 */ public Iterator iterator() { return new ArrayIterator(); } //实现迭代器 private class ArrayIterator implements Iterator { //维护一个i用于迭代 private int i = 0; public boolean hasNext() { return i < N; } public void remove() { throw new UnsupportedOperationException(); } //直接利用first进行遍历，注意可能存在数组的循环利用 public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = q[(i + first) % q.length]; i++; return item; } } /** * 测试 */ public static void main(String[] args) { Queue q = new Queue (); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) q.enqueue(item); else if (!q.isEmpty()) StdOut.print(q.dequeue() + " "); } StdOut.println("(" + q.size() + " left on queue)"); } } 使用链表实现队列： public class Queue implements Iterable { private Node first; // 队头节点 private Node last; // 队尾节点（注意和上面的last区分，last并不是队尾元素的下标） private int N; // 队列元素的数量 // 辅助类Node private static class Node { private Item item; private Node next; } /** * 初始化队列 */ public Queue() { first = null; last = null; N = 0; } public boolean isEmpty() { return first == null; } public int size() { return N; } /** * 返回但不删除头元素 */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); return first.item; } /** * 元素入列 */ public void enqueue(Item item) { //记录尾节点 Node oldlast = last; //创建新的尾节点 last = new Node(); last.item = item; last.next = null; //如果队列是空的，将first置为last，因为这时候队列中只有一个元素 if (isEmpty()) first = last; //否则执行正常的在尾节点插入新节点的操作 else oldlast.next = last; N++; } /** *元素出列 */ public Item dequeue() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); //队头元素出列 Item item = first.item; first = first.next; N--; //如果这时候队列为空，表示原来只有一个元素，这时候也将last置为null if (isEmpty()) last = null; return item; } public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) s.append(item + " "); return s.toString(); } public Iterator iterator() { return new ListIterator(first); } // 实现迭代 private class ListIterator implements Iterator { private Node current; //要实现迭代，我们只需要维护一个节点，并在开始的时候将它置为first public ListIterator(Node first) { current = first; } public boolean hasNext() { return current != null;} public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; } } /** * 测试 */ public static void main(String[] args) { Queue q = new Queue(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) q.enqueue(item); else if (!q.isEmpty()) StdOut.print(q.dequeue() + " "); } StdOut.println("(" + q.size() + " left on queue)"); } } 我是一个栈，我的双胞胎弟弟叫队列。我的爸爸是数组，我的妈妈是链表。 你们可以使用数组和链表来实现栈和队列。 好了，今天关于我和我的家族的故事就先给你介绍到这里了。偷偷告诉你一个秘密，其实我和弟弟之间是可以互相转换的。也就是说可以使用栈来实现队列，同样也可以使用队列来实现栈。关于这个小秘密，我下次再给你介绍哦。 参考资料 “数组、堆栈”与“链表、队列”的区别
-
使用两个栈实现队列，使用两个队列实现栈。 我是一个栈，我的双胞胎弟弟叫队列。我的爸爸是数组，我的妈妈是链表。在上一篇文章中，向你们介绍了我的家族成员对于数据存储方面的能力和特性。还包括如何通过数组和链表来实现栈和队列。 上一次的介绍中，还遗留一个问题。其实我和我的双胞胎弟弟队列之间是可以互相转换的。可以通过栈来实现队列，也可以通过队列来实现栈。这也是很多面试官喜欢问的知识点。这篇文章就来像你介绍下这个知识点。 栈的队列的特点 栈和队列都是用来保存数据的，无论底层是使用数组还是链表来实现，其基本原理是不变的，那就是栈的特点的先进后出，队列的特点是先进先出。 要想通过栈来实现队列，需要两个栈才可以。使用队列来实现栈亦然。 栈和队列，作为两个数据结构，都包含插入、删除等功能的。 栈的常用方法 isEmpty() 判断栈是否为空 size() 返回栈中元素的个数 push() 向栈中插入数据 pop() 从栈中弹出数据并返回 peek() 返回栈顶的数据 队列的常用方法 isEmpty() 判断队列是否为空 size() 返回队列中元素的个数 enqueue() 向队列中插入数据 dequeue() 从队列中弹出数据并返回 peek() 返回队列中第一个数据 本文，主要来实现栈和队列的插入和删除方法。即push()、pop()和 enqueue()、dequeue()方法。其他方法实现起来比较简单，作为思考题供大家自己实现。 使用栈来实现队列 首先我们来考虑如何使用两个栈来实现队列。队列的特点是先进后出，如果向队列中保存”hollis”的顺序是h、o、l、l、i、s，那么取出元素的数序也应该是h、o、l、l、i、s。 而对于栈来说，如果你想要让一个元素能够第一个被弹出，就要保证他永远位于栈的顶部。也就是说，如果你希望出站的顺序是h、o、l、l、i、s，那么入站顺序需要时silloh。 我们现在已经有的数据结构是栈，如果按照h、o、l、l、i、s的顺序向一个栈中保存数据的话，这些元素在栈中的顺序应该是s、i、l、l、o、h。也就是他正常的弹出顺序应该是silloh，但是我们想要的弹出顺序是hollis。 那么如何解决这个问题呢，就需要另外一个栈来配合，两个栈互相倒换。具体如何操作呢？ 有一种方案是这样的：两个栈严格区分开来使用，一个专门用来做插入（插入栈），一个专门用来做弹出（弹出栈）。这样在做插入的时候什么都不需要做，直接调用插入栈的push方法就可以了。但是在弹出的时候就要麻烦一点，先判断在弹出栈中是否包含数据，如果包含，直接从顶部弹出，如果不包含，把插入栈中的元素挨个导入到弹出栈中。然后再从栈顶将第一个元素弹出。 说起来好像挺绕的，没关系。接着往下看，我们先来定义一下这个队列： class MyQueue { stack in; stack out; } 接下来，我们通过一张图来模拟下如何使用两个栈来实现队列的插入操作。 上图中可以看出来，插入还是比较简单的，只需要往插入栈中push就可以了，代码实现如下： void push(int x) { in.push(x); } 插入的时候简单了，那么弹出的时候可能就要经过一番操作了。再来一张图，看看如何使用两个栈来实现队列的弹出操作。 简单介绍下过程：队列中原有三个数据，插入顺序是HOL，进行以下三个操作：1、弹出H，2、插入L，3、弹出O。 从上面的图中可以看到，当我们尝试弹出H的时候，由于stack-out为空，需要把stack-in栈中的数据pop出来，并push进入stack-out，然后再从stack-out的栈顶就能直接弹出H了。 当我们尝试弹出O的时候，因为stack-out中包含数据，那么就直接从stack-out中往外弹数据就可以了。 代码实现如下： int pop() { if (!out.empty()) { int temp = out.top(); out.pop(); return temp; } else { if (in.empty()) { return -1; } else { while (!in.empty()) { out.push(in.top()); in.pop(); } int temp = out.top(); out.pop(); return temp; } } } 使用队列来实现栈 上面的队列实现中。插入方法并没有额外的操作，只是在弹出的时候需要做些额度的处理。那么另外一个思路就是在插入的时候做些事情，这样在弹出的时候就可以无须额外操作直接弹出了。同样，还是需要两个队列来实现栈。具体如何操作呢？ 先来定义一下这个栈： class MyStack { queue a; queue b; } 还是通过一张图，看下使用队列实现的栈是如何进行元素的插入的。 从上图中可以看出，用来实现栈的两个队列是不区分用途的，也就是说两个队列都具备插入和弹出的功能。之所以可以这么做的原因就是，他要保证任何时候都只有一个队列中有元素。 上图的插入操作，插入H的时候，两个队列都为空，优先选择从queue1插入。 当想要插入O的时候，由于queue1中已经包含了数据，那么就讲O插入queue2中，然后再将queue1中的数据依次插入queue2。实现代码如下： void push(int x) { if (a.empty() && b.empty()) { a.push(x); return; } if (a.empty()) { a.push(x); while (!b.empty()) { a.push(b.front()); b.pop(); } } else { b.push(x); while (!a.empty()) { b.push(a.front()); a.pop(); } } } 再来一张图，看看如何使用两个队列来实现栈的弹出操作。 由于我们在插入的时候，保证了两个队列中只有一个队列包含数据，并且数据的顺序已经调整好了（包含数据的那个队列的队列头就是整个栈的栈顶），那么就直接从有数据的那个队列中往外弹数据就可以了。实现代码如下： int pop() { if (a.empty()) { int temp = b.front(); b.pop(); return temp; } else { int temp = a.front(); a.pop(); return temp; } } 好了，至此，我们已经完成了使用两个栈实现队列和两个队列实现栈的功能的介绍。总结一下，主要有两种方案。拿通过栈来实现队列举例。 方案一：定义两个栈，一个专门用来插入，一个专门用来弹出。插入操作只会插入到插入栈。弹出的时候，优先从弹出栈往外弹，如果弹出栈中的内容为空，那么就将插入栈中的数据依次弹出，并压入弹出栈，然后再弹出。 方案二：定义两个栈，不区分作用，但是有一个原则就是始终要保证其中一个栈为空。每次插入的时候先将待插入数据直接插入到空的栈中，然后再将另外一个栈中的数据依次弹出，并压入这个刚刚插入新数据的栈中。弹出的时候，只要从那个有数据的栈中往外弹数据就可以了。 无论以上哪种方案，其实根本原理都是和我们小时候玩的汉诺塔游戏差不多。
