首页 > 代码库 > 数据结构与算法分析 3.23 — 用一个数组实现三个(多个)栈
数据结构与算法分析 3.23 — 用一个数组实现三个(多个)栈
一、题目
用一个数组实现三个(或多个)栈
二、解答
用一个数组实现三个乃至多个栈，如果想使用一个数组构造两个栈的思想则行不通；
考虑使用静态链表，数组结点中存在两个域，关键字域与指示栈的前驱的游标，则可以使三个栈可以用一个数组表示；
ADT的关键术语：
Capacity: 数组的容量；
Size: 数组已经存储的数据元素个数；
Top_Fst：First栈的栈顶；
三、代码
struct Node;typedef struct Node ElementType;typedef struct StackRecord * Stack;struct Node{ Type Key; int Pre;};struct StackRecord{ int Capacity; int Size; int Top_Fst; int Top_Snd; int Top_Trd; ElementType *Array;};Stack CreateStack( int MaxElements );int IsEmpty_Fst( Stack S );int IsFull( Stack S );void Push_Fst( Type Key, Stack S );Type Pop_Fst( Stack S );void MakeEmpty( Stack S );void DisposeStack( Stack S );Stack CreateStack( int MaxElements ){ Stack S; S = (Stack)malloc( sizeof(struct StackRecord) ); if ( S == NULL ) { printf( "Out of space" ); return NULL; } S->Array = (ElementType *)malloc( sizeof(ElementType) * MaxElements ); if ( S->Array == NULL ) { printf( "Out of space" ); return NULL; } S->Capacity = MaxElements; MakeEmpty(S); return S;}int IsEmpty_Fst( Stack S ){ return S->Top_Fst == -1;}int IsFull( Stack S ){ return S->Size == S->Capacity;}void MakeEmpty( Stack S ){ if ( S != NULL ) { S->Size =0; S->Top_Fst = -1; S->Top_Snd = -1; S->Top_Trd = -1; }}void Push_Fst( Type Key, Stack S ){ int TmpCell; if ( IsFull(S) ) printf( "Stack is full" ); else { TmpCell = S->Top_Fst; S->Top_Fst = S->Size; S->Array[S->Top_Fst].Key = Key; S->Array[S->Top_Fst].Pre = TmpCell; S->Size++; }}Type Pop_Fst( Stack S ){ int TmpCell; if ( IsEmpty_Fst(S) ) printf( "Stack is empty" ); else { TmpCell = S->Top_Fst; S->Top_Fst = S->Array[TmpCell].Pre; S->Size--; } return S->Array[TmpCell].Key;}void DisposeStack( Stack S ){ if ( S != NULL ) { free( S->Array ); free( S ); }}
数据结构与算法分析 3.23 — 用一个数组实现三个(多个)栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。