分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。

Question

用C++编写

Answer 1

顺序存储结构

#include<iostream>
typedef char ElemType;
#define MaxSize 100
using namespace std;
typedef struct
{
ElemType data[MaxSize];
int top;
}sqStack;
void InitStack(sqStack *&s);//初始化栈
void ClearStack(sqStack *&s);//摧毁栈
int StackLength(sqStack *s);//返回栈的长度
bool StackEmpty(sqStack *s);//判断栈是否为空
int Push(sqStack *&s,ElemType e);//进栈
int Pop(sqStack *&s,ElemType &e);//出栈
int GetTop(sqStack *s,ElemType &e);//取栈顶元素
void DispStack(sqStack *s);//显示栈中元素值
int main()
{

return 0;
}

void InitStack(sqStack *&s)//初始化栈
{
s=new sqStack;
s->top=-1;
}
void ClearStack(sqStack *&s)//摧毁栈
{
delete s;
}

int StackLength(sqStack *s)//返回栈的长度
{
return (s->top+1);
}

bool StackEmpty(sqStack *s)//判断栈是否为空
{
return (s->top==-1);
}

int Push(sqStack *&s,ElemType e)//进栈
{
if(s->top==MaxSize-1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}

int Pop(sqStack *&s,ElemType &e)//出栈
{
if(s->top==-1)
return 0;
e=s->data[s->top];
s->top--;
return 1;

}

int GetTop(sqStack *s,ElemType &e)//取栈顶元素
{
if(s->top==-1)
return 0;
e=s->data[s->top];
return 1;
}

void DispStack(sqStack *s)//显示栈中元素值
{
for(int i=s->top;i>=0;i--)
cout<<s->data[i]<<" ";
cout<<endl;
}

链式存储结构

typedef char ElemType;

typedef struct linknode
{
ElemType data;
struct linknode *next;
}LiStack;
void InitStack(LiStack *&s);//初始化栈
void ClearStack(LiStack *&s);//摧毁栈
int StackLength(LiStack *s);//返回栈的长度
bool StackEmpty(LiStack *s);//判断栈是否为空
void Push(LiStack *&s,ElemType e);//进栈
int Pop(LiStack *&s,ElemType &e);//出栈
int GetTop(LiStack *s,ElemType &e);//取栈顶元素
void DispStack(LiStack *s);//显示栈中元素值

int main()
{
return 0;
}

void InitStack(LiStack *&s)//初始化栈
{
s=new LiStack;
s->next=NULL;
}

void ClearStack(LiStack *&s)//摧毁栈
{
for(LiStack *p=s->next;p;p=p->next)
{
delete s;
s=p;
p=p->next;
}
delete s;
}

int StackLength(LiStack *s)//返回栈的长度
{
int i=0;
for(LiStack *p=s->next;p;p=p->next)
i++;
return i;
}

bool StackEmpty(LiStack *s)//判断栈是否为空
{
return (s->next==NULL);
}

void Push(LiStack *&s,ElemType e)//进栈
{
LiStack *p=new LiStack;
p->data=e;
p->next=s->next;
s->next=p;
}

int Pop(LiStack *&s,ElemType &e)//出栈
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
delete p;
return 1;

}
int GetTop(LiStack *s,ElemType &e)//取栈顶元素
{
if(s->next==NULL)
return 0;
e=s->next->data;
return 1;
}
void DispStack(LiStack *s)//显示栈中元素值
{
LiStack *p=s->next;
for(;p;p=p->next)
cout<<p->data<<" ";
cout<<endl;

}

Answer 2

一、顺序栈
栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。因此，可用数组来实现顺序栈。
因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；
栈顶位置是随着进栈和退栈操作而变化的.

栈的顺序存储表示 — 顺序栈

#include <assert.h>
template <class Type> class Stack {
private:
int top; //栈顶数组指针
Type *elements; //栈数组
int maxSize; //栈最大容量
public:
Stack ( int=10 ); //构造函数
~Stack ( ) { delete[ ] elements; }//析构函数

void Push ( const Type & item ); //入栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶元素
void MakeEmpty ( ) { top=-1; } //置空栈
int IsEmpty ( ) const { return top == -1; }
int IsFull ( ) const
{ return top == maxSize-1; }

}
void Push ( const Type & item ); //入栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶元素
void MakeEmpty ( ) { top=-1; } //置空栈
int IsEmpty ( ) const { return top == -1; }
int IsFull ( ) const
{ return top == maxSize-1; }

}
构造函数
template <class Type> Stack<Type>::
Stack ( int s ) : top (-1), maxSize (s) {
elements = new Type[maxSize];
}
template <class Type> void Stack<Type>::
Push ( const Type & item ) {
assert ( !IsFull ( ) );或//先决条件断言
if(top != maxSize-1 )
elements[++top] = item; //加入新元素
}
template <class Type> Type Stack<Type>:: Pop ( ) {
assert ( !IsEmpty ( ) ); //先决条件断言
return elements[top--]; //退出栈顶元素
}
template <class Type> Type stack<Type>::
GetTop ( ) {
assert ( !IsEmpty ( ) ); //先决条件断言
return elements[top]; //取出栈顶元素
}

链式栈 (LinkedStack)类的定义

template <class Type> class Stack;
template <class Type> class StackNode {
friend class Stack<Type>;
private:
Type data; //结点数据
StackNode<Type> *link; //结点链指针
StackNode ( Type d=0, StackNode<Type>
*l=NULL ) : data (d), link (l) { }
};
template <class Type> class Stack {
private:
StackNode<Type> *top; //栈顶指针public:
Stack ( ) : top ( NULL ) { }
~Stack ( );
void Push ( const Type & item);
Type Pop ( );
Type GetTop ( );
void MakeEmpty ( ) ;
int IsEmpty ( ) const
{ return top == NULL; }
}
template <class Type> void Stack<Type>::
~Stack ( ) {
StackNode <Type> *p;
while ( top != NULL ) //逐结点回收
{ p = top; top = top→link; delete p; }
}
template <class Type> void Stack<Type>::
Push ( const Type &item ) { //入栈
top = new StackNode<Type> ( item, top );
//新结点链入top之前, 并成为新栈顶
}
template <class Type> Type Stack<Type>::
Pop ( ) { //出栈
assert ( !IsEmpty ( ) );或
if(top){
StackNode<Type> *p = top;
Type retvalue = p→data; //暂存栈顶数据
top = top→link; //修改栈顶指针
delete p; //释放空间
return retvalue; //返回数据
}//if
}
template <class Type> Type Stack<Type>::
GetTop ( ) { //取栈顶元素
assert ( !IsEmpty ( ) );
return top→data;
}