什么是堆栈和指针，请生动的简单的解释一下

堆栈是一种执行“后进先出”算法的数据结构。

设想有一个直径不大、一端开口一端封闭的竹筒。有若干个写有编号的小球，小球的直径比竹筒的直径略小。现在把不同编号的小球放到竹筒里面，可以发现一种规律：先放进去的小球只能后拿出来，反之，后放进去的小球能够先拿出来。所以“先进后出”就是这种结构的特点。

堆栈就是这样一种数据结构。它是在内存中开辟一个存储区域，数据一个一个顺序地存入（也就是“压入——push”）这个区域之中。有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元，存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫做“栈底”。数据一个一个地存入，这个过程叫做“压栈”。在压栈的过程中，每有一个数据压入堆栈，就放在和前一个单元相连的后面一个单元中，堆栈指示器中的地址自动加1。读取这些数据时，按照堆栈指示器中的地址读取数据，堆栈指示器中的地址数自动减 1。这个过程叫做“弹出pop”。如此就实现了后进先出的原则。

堆栈是计算机中最常用的一种数据结构，比如函数的调用在计算机中是用堆栈实现的。
堆栈可以用数组存储，也可以用以后会介绍的链表存储。
下面是一个堆栈的结构体定义，包括一个栈顶指针，一个数据项数组。栈顶指针最开始指向-1,然后存入数据时，栈顶指针加1，取出数据后，栈顶指针减1。

#define MAX_SIZE 100
typedef int DATA_TYPE;
struct stack
{
DATA_TYPE data[MAX_SIZE];
int top;
};

什么是指针？

和其它变量一样，指针是基本的变量，所不同的是指针包含一个实际的数据，该数据代表一个可以找到实际信息的内存地址。这是一个非常重要的概念。许多程序和思想依靠指针作为他们设计的基础。

开始

怎样定义一个指针呢？除了你需要在变量的名称前面加一个星号外，其它的和别的变量定义一样。举个例子，以下代码定义了两个指针变量，它们都指向一个整数。

int* pNumberOne;

int* pNumberTwo;

注意到两个变量名称前的前缀’p’了么？这是一个惯例，用来表示这个变量是个指针。

现在，让我们将这些指针实际的指向某些东西：

pNumberOne = &some_number;

pNumberTwo = &some_other_number;

‘&’符号应该读作”什么什么的地址”，它返回一个变量在内存中的地址，设置到左侧的变量中。因此，在这个例子中，pNumberOne设置和some_number的地址相同，因此pNumberOne现在指向some_number。

现在，如果我们想访问some_number的地址，可以使用pNumberOne。如果我们想通过pNumberOne访问some_number的值，那么应该用*pNumberOne。这个星号表示解除指针的参照，应该读作“什么什么指向的内存区域”。

到现在我们学到了什么？举个例子

哟，有许多东西需要理解。我的建议是，如果你有哪个概念没有弄清楚的话，那么，不妨再看一遍。指针是个复杂的对象，可能需要花费一段时间来掌握它。

这儿有一个例子示范上面所将的概念。这是用C写的，没有C++扩展。

#include

void main()

{

// 申明变量

int nNumber;

int *pPointer;

//赋值

nNumber = 15;

pPointer = &nNumber;

// 输出nNumber的值

printf("nNumber is equal to : %d\n", nNumber);

// 通过pPointer修改nNumber的值

*pPointer = 25;

// 证明nNumber已经被改变了

// 再次打印nNumber的值

printf("nNumber is equal to : %d\n", nNumber);

}

通读一遍，并且编译样例代码，确信你理解了它为什么这样工作。如果你准备好了，那么继续。

一个陷阱！

看看你能否发现下面这段程序的毛病：

#include

int *pPointer;

void SomeFunction();

{

int nNumber;

nNumber = 25;

//将pPointer指向nNumber

pPointer = &nNumber;

}

void main()

{

SomeFunction(); //用pPointer做些事情

// 为什么会失败？

printf("Value of *pPointer: %d\n", *pPointer);

}

这段程序先调用SomeFunction函数，该函数创建一个叫做nNumber的变量，并将pPointer指向它。那么，问题是，当函数退出时，nNumber被删除了，因为它是一个局部变量。当程序执行到局部变量定义的程序块以外时，局部变量总是被删除了。这就意味着，当SomeFunction函数返回到main函数时，局部变量将被删除，因此pPointer将指向原先nNumber的地址，但这个地址已经不再属于这段程序了。如果你不理解这些，那么重新阅读一遍关于局部变量和全局变量的作用范围是明智的选择。这个概念也是非常重要的。

那么，我们如何解决这个问题呢？答案是使用大家都知道的一个方法：动态分配。请明白C和C++的动态分配是不同的。既然现在大多数程序员都使用C++，那么下面这段代码就是常用的了。

动态分配

动态分配可以说是指针的关键所在。不需要通过定义变量，就可以将指针指向分配的内存。也许这个概念看起来比较模糊，但是确实比较简单。下面的代码示范如何为一个整数分配内存：

int *pNumber;

pNumber = new int;

第一行申明了一个指针pNumber，第二行分配一个整数内存，并且将pNumber指向这个新内存。下面是另一个例子，这次用一个浮点数：

double *pDouble;

pDouble = new double;

动态分配有什么不同的呢？当函数返回或者程序运行到当前块以外时，你动态分配的内存将不会被删除。因此，如果我们用动态分配重写上面的例子，可以看到现在能够正常工作了。

#include

int *pPointer;

void SomeFunction()

{

// make pPointer point to a new integer

pPointer = new int;

*pPointer = 25;

}

void main()

{

SomeFunction(); // make pPointer point to something

printf("Value of *pPointer: %d\n", *pPointer);

}

通读一遍，编译上面的代码，确信你已经理解它是如何工作的。当调用SomeFunction时，分配了一些内存，并且用pPointer指向它。这次，当函数返回时，新内存就完整无缺了。因此pPointer仍旧指向有用的东西。这是因为使用了动态分配。确信你已经理解它了。那么继续向下看，了解为什么上面的程序还会有一系列的错误。

内存分配和内存释放

这里有一个问题，可能会变得十分严重，虽然它很容易补救。这个问题就是，虽然你用动态分配可以方便的让内存完整无缺，确实不会自动删除，除非你告诉计算机，你不再需要这块内存了，否则内存将一直被分配着。因此结果就是，如果你不告诉计算机你已经使用完这块内存，那么它将成为被浪费的空间，因为其它程序或者你的应用程序的其它部分不能使用这块内存。最终将导致系统因为内存耗尽而崩溃。因此这个问题相当重要。内存使用完后释放非常容易：

delete pPointer;

需要做的就是这些。但是你必须确定，你删除的是一个指向你实际分配的内存的指针，而不是其它任何垃圾。尝试用delete已经释放的内存是危险的，并且可能导致程序崩溃。

这里再次举个例子，这次修改以后就不会有内存浪费了。

#include

int *pPointer;

void SomeFunction()

{

// make pPointer point to a new integer

pPointer = new int;

*pPointer = 25;

}

void main()

{

SomeFunction(); // make pPointer point to something

printf("Value of *pPointer: %d\n", *pPointer);

delete pPointer;

}

只有一行不同，但这行是要点。如果你不删除内存，就会导致“内存泄漏”，内存将逐渐减少，除非应用程序重新启动，否则将不能再生。

向函数传递指针

传递指针给函数非常有用，但不容易掌握。如果我们写一个程序，传递一个数值并且给它加上5，我们也许会写出如下的程序：

#include

void AddFive(int Number)

{

Number = Number + 5;

}

void main()

{

int nMyNumber = 18;

printf("My original number is %d\n", nMyNumber);

AddFive(nMyNumber);

printf("My new number is %d\n", nMyNumber);

}

但是，程序中函数AddFive的参数Number只是变量nMyNumber的一个拷贝，而不是变量本身，因此，Number = Number + 5只是为变量的拷贝增加了5，而不是最初的在main()函数中的变量。当然，你可以运行程序，以证明这一点。

为了将值传递出去，我们可以传递这个变量的指针到函数中，但我们需要修改一下函数，以便传递数值的指针而不是数值。因此将void AddFive(int Number)修改为void AddFive(int *Number)，增加了一个星号。下面是修改了的函数，注意，我们必须确认传递了nMyNumber的地址，而不是它本身。这通过增加&符号来完成，通常读作“什么什么的地址”。

#include

void AddFive(int* Number)

{

*Number = *Number + 5;

}

void main()

{

int nMyNumber = 18;

printf("My original number is %d\n", nMyNumber);

AddFive(&nMyNumber);

printf("My new number is %d\n", nMyNumber);

}

大家可以试着自己做个例子来实验一下。注意在AddFive函数中Number变量前那个重要的星号。只是必须的，用来告诉编译器我们想将5加到变量Number指向的数值，而不是将5加到指针本身。

关于函数最后需要注意的是你也可以返回一个指针。比如：

int * MyFunction();

在这个例子中，MyFunction函数返回一个指向整数的指针。

类的指针

关于指针还有两个需要注意的问题。其中一个是结构或者类。你可以如下定义一个类：

class MyClass

{

public:

int m_Number;

char m_Character;

};

然后，你可以如下方式定义一个类变量：

MyClass thing;

你应该已经知道这些了，如果还不知道的话，那么再将上面的内容读一遍。定义MyClass的指针应该这么写：

MyClass *thing;

然后你需要分配内存，并将指针指向这个内存

thing = new MyClass;

问题来了，你如何使用这个指针呢？一般的，我们写thing.m_Number，但你不能对指针用’.’操作，因为thing不是一个MyClass对象。只是指向一个MyClass对象的指针。因此，指针thing不包含m_Number这个变量。只是它指向的结构中包含这个变量。因此，我们必须使用一个不同的协定，用->取代’.’。以下是一个例子：

class MyClass

{

public:

int m_Number;

char m_Character;

};

void main()

{

MyClass *pPointer;

pPointer = new MyClass;

pPointer->m_Number = 10;

pPointer->m_Character = 's';

delete pPointer;

}

数组的指针

你也可以构造一个指向数组的指针，如下：

int *pArray;

pArray = new int[6];

将创建一个叫做pArray的指针，指向一个包含6个元素的数组。另一种构造的方法是使用动态分配，如下：

int *pArray;

int MyArray[6];

pArray = &MyArray[0];

注意，你这里也可以不用&MyArray[0]，而直接使用&MyArray取代。当然，这仅仅适用于数组。

使用指向数组的指针

一旦你有了指向数组的指针，那么如何使用它呢？现在假设你有一个指向整数数组的指针，那么指针开始时将指向第一个整数。举例如下：

#include

void main()

{

int Array[3];

Array[0] = 10;

Array[1] = 20;

Array[2] = 30;

int *pArray;

pArray = &Array[0];

printf("pArray points to the value %d\n", *pArray);

}

将指针移到指向数组的下一个值，可以用pArray++。也许你也可以猜出来了，我们可以用pArray+2的方式将指针向后移动两个位置。要注意的问题是，你自己必须知道数组的上限是多少（例子中是3），因为编译器不能检查你是否将指针移到了数组以外，因此你可以很容易的将系统搞崩溃了。以下是个例子，显示我们设置的三个值：

#include

void main()

{

int Array[3];

Array[0] = 10;

Array[1] = 20;

Array[2] = 30;

int *pArray;

pArray = &Array[0];

printf("pArray points to the value %d\n", *pArray);

pArray++;

printf("pArray points to the value %d\n", *pArray);

pArray++;

printf("pArray points to the value %d\n", *pArray);

}

你也可以使用pArray-2这样的方式来向前移动2个位置。不管是加或者减，你必须保证不是对指针所指向的数据的操作。这种操作指针和数组的方式在循环中是最常用的。例如for和while循环。

另外要提的是，如果你有一个指针比如int pNumberSet，你也可以把它当成数组。例如pNumberSet[0]等于*pNumberSet，并且pNumberSet[1]等于*(pNumberSet+1)。

对于数组，还有一点要注意的，如果你用new为数组分配内存，比如：

int *pArray;

pArray = new int[6];

你必须用以下方式进行删除：

delete[] pArray;

注意delete后的[]，它告诉编译器，这是删除整个数组，而不仅仅是第一个元素。对于数组你必须使用这种方法，否则就会有内存泄漏。

总结

一条要注意的：你不能删除不是用new分配的内存。比如以下例子：

void main()

{

int number;

int *pNumber = number;

delete pNumber; // wrong - *pNumber wasn't allocated using new.

}

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=239295