C++栈学习——顺序栈和链栈的差别

C++中栈有顺序栈和链栈之分。在顺序栈中，定义了栈的栈底指针（存储空间⾸地址base）、栈顶指针top以及顺序存储空间的⼤⼩stacksize（个⼈感觉这个数据成员是能够不⽤定义的）

//顺序栈数据结构C++类声明（基类）template class SqStack {

public:

void clear(); //把顺序栈置空

int getLength(); //求顺序栈中元素个数

int getstackSize(); //返回当前已分配的存储空间的⼤⼩ Status getTop(ElemType & e); //读栈顶的元素 bool isEmpty(); //推断顺序栈是否为空

SqStack operator =(SqStack rightS); //重载赋值运算符的定义 Status pop(ElemType & e); //弹出栈顶元素到e void push(ElemType & e ); //在栈顶压⼊元素e

//*****************************以下为系统⾃⼰主动调⽤构造函数及析构函数声明******************************// SqStack(); //顺序栈构造函数

virtual ~SqStack();//顺序栈析构函数

SqStack (const SqStack& otherS);//顺序栈拷贝初始换构造函数protected:

ElemType *base; ElemType *top;

int stackSize;//顺序存储空间的⼤⼩};

⽽对于链栈来说，它仅仅定义栈顶指针。

templateclass Linkstack{

private:

class LinkNode {

public:

ElemType data; LinkNode *next; };

typedef LinkNode * NodePointer;

public:

void clear(); int getlength(); void display();

void randLinkStack();

Linkstack operator = (Linkstack rightS);protected:

NodePointer top;};

事实上这⼆者的差别是由顺序表和链表的存储结构决定的，在空间上，顺序表是静态分配的，⽽链表则是动态分配的；就存储密度来说：顺序表等于1，⽽链式表⼩于1。可是链式表能够将⾮常多零碎的空间利⽤起来；顺序表查找⽅便。链式表插⼊和删除时⾮常⽅便。

顺序表的这样的静态存储的⽅式，决定了必须⾄少得有⾸地址和末地址来决定⼀个空间。否则，不知道查找到哪了。链式表每⼀个节点存储了下⼀个节点的指针信息，故，对于链栈来说，仅仅须要⼀个top指针就可以查找到整个栈。

另外，顺序栈和链栈的top指针有差别，顺序栈的top指针指向栈定的空元素处，top-1才指向栈定元素，⽽链栈的top指针相当于链表的head指针⼀样，指向实实在在的元素。

另外附⾃⼰写的顺序栈和链栈的随机产⽣函数：

//顺序栈：

template

void MyStack::RandStack(){

int *p;

ElemType n;

ElemType Elem[11]; srand(time(NULL)); n=rand()%10+1;

cout<<\"产⽣的随机栈的深度为：\"<for (int i = 0; i < n; i++) {

Elem[i]=rand()%100+1; cout<cout<base=new ElemType[n]; assert(base!=0); top=base; stackSize=n;

for (int j = 0; j < n; j++) *(base+j)=Elem[j]; top=base+n;

cout<<\"随机产⽣的栈为：\"<for (int i = 1; i setw(4); cout<<\" \"; }

cout<<\" ♂\"<for (int i = 1; i setw(4); cout<<\" \"; }

cout<<\" top\"<template

void MyStack::display(){

int n=top-base;

cout<<\"当前栈为：\"<for (int i = 1; i setw(4); cout<<\" \"; }

cout<<\" ♂\"<for (int i = 1; i setw(4); cout<<\" \"; }

cout<<\" top\"<//链栈

template

void Linkstack::display(){

NodePointer r; int num=0; r=top; while (r) {

cout<data<<\" \"; r=r->next; num++; }

cout<for(int i=0;ifor(int i=0;itemplate

void Linkstack::randLinkStack()

{

ElemType elem[11];

srand(unsigned(time(NULL))); int n;

n=rand()%10+1;

cout<<\"the number of the stack is:\"<elem[i]=rand()%100+1; cout<cout<NodePointer p,s; p=NULL;

for (int i = 0; i < n; i++) {

s=new(LinkNode); assert(s!=NULL); s->data=elem[i]; s->next=p; p=s; }

top=p;

cout<<\"the stack produced is:\"<cout<data<<\" \"; r=r->next; num++; }

cout<for(int i=0;ifor(int i=0;i