C程序中如何使用堆栈

先从大家比较熟悉的栈说起，它是一种具有后进先出性质的数据结构，也就是说后存放的先取，先存放的后取。这就如同要取出放在箱子里面底下的东西（放入的比较早的物体），首先要移开压在它上面的物体（放入的比较晚的物体）。而堆就不同了，堆是一种经过排序的树形数据结构，每个结点都有一个值。通常所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同在图书馆的书架上取书，虽然书的摆放是有顺序的，但是想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，可以直接取出想要的书。

下面就说说C语言程序内存分配中的堆和栈，这里有必要把内存分配也提一下，一般情况下程序存放在Rom或Flash中，运行时需要拷到内存中执行，内存会分别存储不同的信息。

内存中的栈区处于相对较高的地址以地址的增长方向为上的话，栈地址是向下增长的，栈中分配局部变量空间，堆区是向上增长的用于分配程序员申请的内存空间。另外还有静态区是分配静态变量，全局变量空间的；只读区是分配常量和程序代码空间的；以及其他一些分区。来看一个网上很流行的经典例子：

maincpp

int a = 0; 全局初始化区

char p1; 全局未初始化区

main()

{

int b; 栈

char s[] = "abc"; 栈

char p2; 栈

char p3 = "123456"; 123456\0在常量区，p3在栈上。

static int c =0； 全局（静态）初始化区

p1 = (char )malloc(10); 堆

p2 = (char )malloc(20); 堆

}

堆和栈的第一个区别就是申请方式不同：栈（英文名称是stack）是系统自动分配空间的，例如定义一个 char a；系统会自动在栈上为其开辟空间。而堆（英文名称是heap）则是程序员根据需要自己申请的空间，例如malloc（10）；开辟十个字节的空间。由于栈上的空间是自动分配自动回收的，所以栈上的数据的生存周期只是在函数的运行过程中，运行后就释放掉，不可以再访问。而堆上的数据只要程序员不释放空间，就一直可以访问到，不过缺点是一旦忘记释放会造成内存泄露。

如果允许用标准库的话，或者你的链表能够提供如push_front()，pop_front()，或者push_back(),pop_back()中的任意一对和clear()函数，事情就好办了：

简单的标准库版本：（只有四个函数，top（））

#include <iostream>

#include <list>

using namespace std;

template <typename Type>

class Stack {

public:

void push(Type elem)

{

slistpush_back(elem);

}

void pop()

{

slistpop_back();

}

void clear()

{

slistclear();

}

Type top()

{

return slistback();

}

private:

list<Type> slist;

};

int main ()

{

Stack<int> st;

stpush(2);

stpush(3);

stpop();

cout << sttop() << endl;

}

自己编写的版本：（较为完善，empty(),size()，top()等都有）

#include <iostream>

using namespace std;

template <class Type>

class Stack {

private:

struct Node;

public:

Stack():theSize(0), head(0) { }

~Stack();

size_t size() const;

bool empty() const;

void clear();

Type& top();

const Type& top() const;

void push(const Type& x);

void pop();

private:

Node head;

size_t theSize;

};

template <class Type>

struct Stack<Type>::Node

{

Node(const Type& i = Type(), Node n = NULL)

:item(i), next(n) { }

Type item;

Node next;

};

template <class Type>

Stack<Type>::~Stack()

{

while (head) {

Nodetemp = head;

head = head->next;

delete temp;

}

}

template <class Type>

size_t Stack<Type>::size() const

{

return theSize;

}

template <class Type>

bool Stack<Type>::empty() const

{

return theSize==0;

}

template <class Type>

void Stack<Type>::clear()

{

while (head) {

Node temp;

temp = head;

head = head->next;

delete temp;

}

theSize = 0;

}

template <class Type>

Type& Stack<Type>::top()

{

return head->item;

}

template <class Type>

const Type& Stack<Type>::top() const

{

return head->item;

}

template <class Type>

void Stack<Type>::push(const Type& x)

{

Node temp = head;

head = new Node;

head->next = temp;

head->item = x;

++theSize;

}

template <class Type>

void Stack<Type>::pop()

{

Node temp = head;

head = head->next;

delete temp;

--theSize;

}

int main ()

{

Stack<int> st;

stpush(2);

stpush(3);

stpush(4);

stpush(3);

stpop();

cout << sttop() << endl;

cout << stsize() << endl;

if (stempty())

cout << "empty" << endl;

else

cout << "not empty" << endl;

stclear();

if (stempty())

cout << "empty" << endl;

}

第二个，是我将以前的自己编的list头文件改编过来的，其中的push(),pop()分别取的是list中的pust_front(),pop_front()两个函数。用模板可能一些老编译器（包括VC60）编译不能通过，我的是在VC2008上运行的，当然你也可以再C++builder2009上运行，还有，如果你需要份文件运行，不要将Stack模板类的的定义和其成员的实现放在不同的文件里，因为很多很多编译器不支持export关键字，所以我也没用，当然主函数可以放在别的文件里。

CList 类2007年06月22日 星期五 09:55C++中实现通用数据结构

在程序设计当中经常会出现使用同种数据结构的不同实例的情况。例如:在一个

程序中可以使用多个队列、树、图等结构来组织数据。同种结构的不同实例,也

许只在数据元素的类型或数量上略有差异,如果对每个实例都重新定义,则非常麻

烦且容易出错。那么能否对同种类型数据结构仅定义一次呢答案是肯定的,C++

提供的类模板(Class Template)就可以实现该功能。

一、类模板

类模板是C++提供的一种特殊机制,通过它我们可以定义一种特殊的类(称为模板

类),在类的定义中可以包含待定的类型参数,在声明类的实例时,系统会自动根据

传递的类型生成用户想要生成的类实例。下面是用C++实现的一个简单的模板类

Clist的定义。

Template <class T, int I> class CList

{

public:

int SetItem(int Index, const T &Item);

int GetItem(int Index, T &Item);

private:

T Buffer[I];

}

在这里,T是类型参数,I是整型常量参数。T和I的实际值是在声明具体类实例时指

定的。模板类的<>号内可以包括任意个类型参数和常量参数(至少要有一个参数

)。类型参数和常量参数可以是任何合法的标准类型和用户自定义类型,包括简单

类型及各种结构体。同其他类一样,类成员函数SetItem的实现可以在类定义内完

成,也可以在类CList定义处实现:

template<class T, int I> int CList<T, I>::SetItem(int Index, const T

&Item)

{

if ( (Index<0)||(Index>I-1) )

return 0; // 出错

Buffer[Index]= Item ;

return 1; // 成功

}

值得注意的是,在类定义外完成函数实现时,必须以关键字template和类模板定义

中相同的参数表(<>号内的)开头(上例为template<class T, int I>),并且范围

分解 *** 作符前的类名后应跟上模板参数名清单(上例为CList<T, I>)。另外,与非

模板类不同的是,必须将函数实现包括在调用它的每个源文件中,使编译器能从函

数实现产生代码。通常的做法是将模板类的函数实现也放在定义该类的头文件中

,这样只需在调用的源文件中包含该头文件即可。

那么,如何使用生成特定的类实例呢我们可以像使用其他类一样来使用模板类,

不过必须指定模板参数的值。例如采用如下声明:

CList <int, 100> IntList;

则使IntList成为CList类的实例,每次出现的T参数都换成int, 每次出现的I参数

都换成100。这样,IntList类中的Buffer就是一个长度为100的整型数组,

SetItem和GetItem函数参数是int值的引用。例:

IntListSetItem(0, 5); //给数组第一个元素赋为整数5

模板类还可以像其他类一样可以定义构造函数和析构函数。下面我们以一种简单

的数据结构——堆栈为例,来说明如何用类模板来构造通用数据结构。

二、 利用类模板实现通用堆栈结构

任何抽象数据结构在计算机中的实现,归根结底都只有两种方式:顺序存储(用数

组实现),链式存储(用指针实现)。堆栈也不例外,按其实现方式可分为顺序栈(用

数组实现)和链栈(用指针实现)。

1 通用顺序栈的实现

因为顺序栈中的元素在空间上连续存储,栈顶的元素位置需要注明,所以构造顺序

栈的模板类应该有这样的一些成员变量:一个待定类型和长度的数组Buffer,一个

记录栈顶元素的数组下标的整型变量top。堆栈的基本 *** 作主要有:入栈(Push)、

出栈(Pop)、置空(SetEmpty)、判断当前状态(IsEmpty)等,它们应用模板类的成

员函数来实现。作为一个标准的类,它还应该有自己的构造函数和析构函数。具

有这些功能的模板类,就可以作为一个通用的顺序栈来使用了。该类的定义如下

:

template <class T,int SIZE> class CArrayStackTemp

{

public:

CArrayStackTemp () //缺省构造函数,构造一个空堆栈

{

top= -1;

};

～ CArrayStackTemp (){};//析构函数

void SetEmpty (); //置空堆栈

bool IsEmpty(); //判断堆栈是否为空

bool Push(T element); //入栈

bool Pop(T& element);//出栈

private:

T Buffer[SIZE];

int top;

};

与堆栈的基本 *** 作相对应的成员函数的实现如下:

template <class T, int SIZE> void CArrayStackTemp<T, SIZE>::

SetEmpty ()

{

top= -1; //将栈顶指针赋 -1,并不实际清除数组元素

}

template <class T, int SIZE> bool CArrayStackTemp<T, SIZE>:: IsEmpty

()

{

return(top == -1);

}

template <class T, int SIZE> bool CArrayStackTemp<T, SIZE>:: Push (T

element)

{

top++;

if (top>SIZE-1)

{

top--;

return false; //堆栈已满,不能执行入栈 *** 作

}

Buffer[top]=element;

return true;

}

template <class T, int SIZE> void CArrayStackTemp<T, SIZE>:: Pop (T&

element)

{

if (IsEmpty())

return false;

element =Buffer[top];

top--;

return true;

}

根据实际需要,还可以扩充堆栈功能。例如:加入取栈顶元素、求堆栈长度等 *** 作

,其方法如上。

2 通用链栈的实现

模板类中允许使用指针和定义自己的结构,这就为实现链式结构提供了保证。这

里采用一个单链表来实现堆栈,栈顶指针指向链表的第一个结点,入栈和出栈均在

链表的头进行。该模板类的定义如下:

template <class T> class CLinkStackTemp

{

public:

//类的缺省构造函数,生成一个空堆栈

CLinkStackTemp ()

{

top=NULL;

};

～ClinkStackTemp(){}; //析构函数

//定义结点结构

struct node

{

T

data; //入栈元素

node next; //指向下一结点的指针

};

void SetEmpty(); //置空堆栈

bool IsEmpty(); //判断堆栈是否为空

bool Push(T element); //压入堆栈

bool Pop(T& element);//d出堆栈

private:

node top;

};

该类的成员函数实现如下:

template <class T> void CLinkStackTemp <T>::SetEmpty()

{

//释放堆栈占用的内存

node temp;

while (top!=NULL)

{

temp=top;

top=top->next;

delete temp;

}

}

template <class T> bool CLinkStackTemp <T>::IsEmpty()

{

return (top==NULL);

}

template <class T> bool CLinkStackTemp <T>::Push(T element)

{

node temp=new node();

if (temp ==NULL)

return false ;

temp->data=element;

temp->next=top;

top=temp;

return true;

}

template <class T> bool CLinkStackTemp <T>::Pop(T& element)

{

if ( IsEmpty())

return false;

node q = top;

element = top->data;

top=top->next;

delete q;

return true;

}

与顺序栈的实现略有不同,链栈不必指定栈的容量,其大小可以是近似"无限"的。

为了程序的使用方便,我们同样可以加入一些增强的功能。

三、 通用堆栈类的使用

通用堆栈类的使用较为简单,堆栈类的实例就是一个可以方便使用的堆栈。对堆

栈的 *** 作都是通过类的成员函数来实现的。使用的具体步骤如下:

1 在要使用堆栈类的程序代码的文件开头包括模板类及其成员函数的定义。

2 类的实例化,可声明成变量,也可以声明它的指针,如:

CArrayStackTemp <int, 100> intStack; //生成一个长度为100的int型堆栈

//生成一个元素为Record型的堆栈,Record为自定义结构

CLinkStackTemp <Record> RecordStack;

RecordStack=new CLinkStackTemp<Record>;

应注意在定义顺序栈时,必须指定栈的大小,而链栈则不必。另外在指定指针类型

和执行new *** 作时,必须对模板参数赋值,并且前后要一致。

3 对堆栈进行 *** 作,如:

intStackPush(3); //将整数3入栈

RecordStackSetEmpty(); //将堆栈置空

无论我们使用哪种堆栈类,对用户来讲都是透明的, *** 作起来并无差别。

CList类的两个参数什么意思啊？第一个参数表示链表中存储的数据类型，后面一个表示链表类中函数参数的传递方式，通常为存储数据类型的引用。

CList<string,string> MyList_x;

CList<string,string&>MyList_y;

//两种方式实现的功能一样，不过后面一个更加高效。

CList <int,string> list;声明方式就是错误，

CList <int,int>list1;CList <int,char>list2;CList<char,int> list3;都是可以接受的声明方式。

我举一个函数例子来说明这一点。

template <class TYPE ,class ARG_TYPE>

class ELEMENT

{

TYPE data;

public:

TYPE set_value(ARG_TYPE m){ data=m+m;}

};

进行如下调用

string z("hello");

ELEMENT<string,string> sample;

sampleset_value(z);

ELEMENT<string,string&> example;//sample,example得到的是完全一样的数据，但是第二种 *** 作高效

exampleset_value(z);

ELEMENT<int,char> demo_a;//由于int,char 支持自动类型转化，可以混合两种类型进行声明

ELEMENT<int,int> demo_b;

ELEMENT<char,char> demo_c;

ELEMENT<char,int> demo_d;

demo_aset_value(''c'');

demo_bset_value(20);

demo_cset_value(''c'');

demo_dset_value(15);

//ELEMENT <int ,string> demo;//这两行错误调用，单纯该行的申明可以通过编译，

//demoset_value(string(hello));//但是有了这一行编译器就不客气了，不能通过

本程序实现了基于堆栈的字符串中括号配对检查功能。在本程序中，使用栈这种数据结构来检查输入的字符串中的括号是否配对。如果括号配对，则输出“括号配对成功”，否则输出“括号配对失败”。

程序实现

程序实现的思路如下：

定义一个栈（使用list数据类型实现），用于存储左括号。

遍历输入的字符串中的每个字符。对于每个字符：

如果是左括号，则将其压入栈中。

如果是右括号，则d出栈顶元素，判断其是否是对应的左括号。如果是，则继续遍历字符串，否则输出“括号配对失败”。

如果遍历完字符串后栈不为空，则输出“括号配对失败”，否则输出“括号配对成功”。

程序实现的Python代码如下：

def check_brackets(input_str):

   stack = []

   for char in input_str:

       if char == '(' or char == '{' or char == '[':

           stackappend(char)

       elif char == ')' or char == '}' or char == ']':

           if not stack:

               return "括号配对失败"

           top = stackpop()

           if (top == '(' and char == ')') or (top == '{' and char == '}') or (top == '[' and char == ']'):

               continue

           else:

               return "括号配对失败"

   if not stack:

       return "括号配对成功"

   else:

       return "括号配对失败"

使用方法

将上述代码复制到Python环境中。

调用check_brackets函数，并传入需要检查的字符串作为参数。

程序将输出“括号配对成功”或“括号配对失败”。

例如：

input_str = "({[()]})"

result = check_brackets(input_str)

print(result)

输出结果为“括号配对成功”。

1程序的问题：

template<class T,class T1> //模板申明用的是尖括号<>

2另外一个问题想请教一下提问者，在函数定义后要加分号";" 是个人习惯还是知道可以这么使用？ 从学习编程至今，几乎没有听谁说过函数定义完成后要加分号。只有类定义完成后加分号之说。可是，调试之后，我惊讶发现，函数定义之后加分号不加分号都可以运行！长了见识。

3附模板详解，以供参阅：

12 模板的基本语法

C++语言中使用关键字template开始一个模板的声明，模板声明的一般形式为：

template<模板参数表>说明体

模板参数表可以包含一个或多个模板参数声明，如果有多个模板参数，参数与参数之间以逗号隔开。例如带有一个参数的模板可以以下述形式开头：

template<class T>

class表示参数T是一个数据类型。在使用该模板时，T可以用用户定义的数据类型，也可以用C++语言固有的数据类型，如int、float等替换。这里的class与类定义中的class没有关系。

参数标识符T也可以用其它的任何标识符来表示，例如：

template<class first>

通常的习惯是，表示数据类型的参数用T打头，后跟表示该参数的含义的英文单词，T表示英文Type。

多个参数的模板声明的格式为：

template<class T1, class T2>

类模板参数除了可以是数据类型外，还可以是其它类型的数据，例如整型数据：

template<class T, int size>

参数的具体使用方法将在下面两节中详细介绍。

2 函 数 模 板

不管它们的性质如何，所有的函数模板都具有同样的基本格式：

template<参数说明>

函数头

函数体

例如，下面是一个单参数的模板的声明：

template<class T>

void f(T param)

{

//此处为函数体

}

template关键字和尖括号中的class T一起开始了模板的构造。下面的函数头函数体中的T在使用时将被指定的类型标识符替代。模板中的每个参数在函数参数表中必须至少使用一次。下面的声明是不允许的：

template<class T1,class T2>

void f(T1 param)

{

//函数体

}

这个函数模板声明了两个参数T1和T2，但是函数本身却只使用了T1来定义param。正确的声明应该是在函数参数表中至少使用T1和T2各一次：

template<class T1,class T2>

void f(T1 param1,T2 param2)

{

//函数体

}

下面是一个模板声明的程序源文件，读者可以将它输入命名为minmaxh，以便在需要时使用。通常的习惯是，将模板放在头文件中声明，以便不同的程序文件可以共享。目前的编译器一般不支持将函数模板的声明与函数模板的函数体部分分别存放，生成独立的函数库文件，然后使用（普通函数可以在头文件中声明原型，函数实现放在独立的源文件中，编译生成函数库，在使用时只需要头文件中函数原型声明，而不需要函数实现的源代码）。

3 类 模 板

31 类模板的定义与使用

类模板也叫模板类或者类生成符，它让用户定义类的模式。例如前面提到的整型数据元素集合和实型数据元素集合的例子，它们实现的功能相同，不同的只是其存储的数据类型不同。将其定义为类模板，模板的参数为该数据类型，可以由它来生成整型集合类和实型集合类。下面通过一个简单的例子来介绍如何定义和使用类模板。

#include <iostreamh>

template<class T>

class Vector{

T data;

int size;

public:

{ Vector(int);

~Vector( ){delete [ ]data;}

T& operator[ ](int i){return data[i];}

};

template<class T>

Vector<T>::Vector(int n)

{

data = new T[n];

size = n;

}

4 编程示例: 栈模板

栈又叫堆栈，是一种常用的数据结构，它是一种运算受限的线性表。仅允许在表的一端进行插入和删除运算，是一种后进先出表。

#include <iostreamh>

enum bool {False, True};

//抽象堆栈类模板定义

template <class T>

以上就是关于C程序中如何使用堆栈全部的内容，包括:C程序中如何使用堆栈、高分悬赏！！！[C++]利用链表构造一个堆栈类Stack、CList类是作什么用的等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！