栈的常见操作.docx

栈的常见操作.docx

《栈的常见操作.docx》由会员分享，可在线阅读，更多相关《栈的常见操作.docx（15页珍藏版）》请在冰点文库上搜索。

栈的常见操作

数据结构面试之三——栈的常见操作

题注：

《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。

三、栈的基本操作

3.1用数组构造栈

【注意以下几点】：

1.基于数组的栈的三要素：

1）栈的最大容量maxSize;2）栈的当前容量=当前栈中元素的个数=栈顶top-1；3）动态数组存储栈的元素Type*list；

      2.对于出栈、入栈的操作要对应先判断栈空、栈满；如果空、满要有异常处理或错误提示。

      3.注意入栈push操作，先入栈后top+1；出栈pop则相反，先top-1，再出栈。

【注意因为，top指向数组中最后一个元素的下一个位置】。

      4.拷贝构造函数和赋值函数要注意，尤其赋值的时候，避免自身赋值、同时要注意大小不一致的不能完成赋值操作，要有相关提示。

template

classarrStack

{

public:

arrStack（intnSize=100）;

~arrStack（）;

arrStack（constarrStack©Stack）;

arrStack&operator=（constarrStack&otherStack）;

voidinitializeStack（）;

voiddestroyStack（）;

boolisStackEmpty（）;

boolisStackFull（）;

voidpush（constType&item）;

voidpop（Type&poppedItem）;

private:

intmaxSize;

inttop;

Type*list;

};

template

arrStack:

:

arrStack（intnSize=100）

{

if（nSize<0）

{

nSize=100;

list=newType[nSize];

top=0;

maxSize=100;

}

else

{

list=newType[nSize];

top=0;

maxSize=nSize;

}

}

template

arrStack:

:

~arrStack（）

{

if（!

list）

{

delete[]list;//注意数组的删除，为delete[]list;

list=NULL;

}

}

template

arrStack:

:

arrStack（constarrStack©Stack）

{

maxSize=copyStack.maxSize;

top=copyStack.top;

list=newType[maxSize];//注意需要自定义大小,容易出错.

for（inti=0;i

{

list[i]=copyStack.list[i];

}

}

template

arrStack&arrStack:

:

operator=（constarrStack&otherStack）

{

if（this==&otherStack）

{

cout<<"can'tcopyoneSelf!

"<

return*this;

}

else

{

if（maxSize!

=otherStack.maxSize）

{

cout<<"TheSizeoftwostackarenotequal!

"<

return*this;

}

else

{

maxSize=otherStack.maxSize;

top=otherStack.top;

for（inti=0;i

{

list[i]=otherStack.list[i];

}//endfor

return*this;

}

}//endelse

}

template

voidarrStack:

:

initializeStack（）

{

destroyStack（）;

}

template

voidarrStack:

:

destroyStack（）

{

top=0;

}

template

boolarrStack:

:

isStackEmpty（）

{

return（top==0）;

}

template

boolarrStack:

:

isStackFull（）

{

return（top==maxSize）;

}

template

voidarrStack:

:

push（constType&item）

{

if（!

isStackFull（））

{

list[top]=item;

top++;

}

else

{

cout<<"TheStackwasalreadyFull!

"<

}

}

template

voidarrStack:

:

pop（Type&poppedItem）

{

if（!

isStackEmpty（））

{

top--;

poppedItem=list[top];

}

else

{

cout<<"TheStackwasalreadyEmpty!

"<

}

}

3.2用链表构造栈

链表构造栈注意：

1） 判断栈空的标记是top==NULL；由于栈的空间可以动态分配，因此可以认为链栈不会满。

2） 栈的入栈Push操作要先判定栈是否已经满，非满才可以入栈。

先入栈，再调整top指针；

3） 栈的出栈Pop操作要先判定栈是否已空，非空才可以出栈。

先调整top指针，再出栈，并删除原结点。

4） 可以加count判定当前结点的个数。

template

structnodeType

{

Typeinfo;

nodeType*link;

};

template

classlinkedStack

{

public:

linkedStack（）;

~linkedStack（）;

linkedStack（constlinkedStack&）;

linkedStack&operator=（constlinkedStack&）;

voidinitializeStack（）;

voiddestroyStack（）;

boolisStackEmpty（）const;

boolisStackFull（）const;

voidpush（constType&item）;

voidpop（Type&poppedItem）;

voidnodeCount（）;

voidreversePrint（）;//逆向打印的非递归实现...

private:

nodeType*top;

intcount;//统计节点个数

};

template

linkedStack:

:

linkedStack（）

{

count=0;

top=NULL;

}

template

linkedStack:

:

~linkedStack（）

{

while（top!

=NULL）

{

nodeType*tempNode=newnodeType;

tempNode=top;

top=top->link;

deletetempNode;

}//endif

}

template

linkedStack:

:

linkedStack（constlinkedStack©Stack）

{

if（copyStack.top!

=NULL）

{

nodeType*current;

nodeType*first;

nodeType*newNode;

top=newnodeType;

top->info=copyStack.top->info;//此处的top不能直接用，内存报错！

top->link=copyStack.top->link;

first=top;//first跟进当前链表...

current=copyStack.top->link;//current跟进copy链表...

while（current!

=NULL）

{

newNode=newnodeType;

newNode->link=current->link;

newNode->info=current->info;

first->link=newNode;

first=newNode;

current=current->link;

}//endwhile

count=copyStack.count;

}//endif

else

{

top=NULL;

count=0;

}

}

template

linkedStack&linkedStack:

:

operator=（constlinkedStack&otherStack）

{

//1避免自身赋值

if（this==&otherStack）

{

cout<<"Can'tcopyoneself!

"<

return*this;

}

//2其他

else

{

if（top!

=NULL）

{

destroyStack（）;

}

if（otherStack.top!

=NULL）

{

nodeType*current;

nodeType*first;

nodeType*newNode;

top=newnodeType;

top->info=otherStack.top->info;

top->link=otherStack.top->link;

first=top;//first跟进当前链表...

current=otherStack.top->link;//current跟进copy链表...

while（current!

=NULL）

{

newNode=newnodeType;

newNode->link=current->link;

newNode->info=current->info;

first->link=newNode;

first=newNode;

current=current->link;

}//endwhile

count=otherStack.count;

}//endif

else

{

top=NULL;

count=0;

}

return*this;

}

}

template

voidlinkedStack:

:

initializeStack（）

{

destroyStack（）;

}

template

voidlinkedStack:

:

destroyStack（）

{

count=0;

top=NULL;

}

template

boollinkedStack:

:

isStackEmpty（）const

{

return（count==0）;

}

template

boollinkedStack:

:

isStackFull（）const//空间非固定，动态申请!

{

returnfalse;

}

template

voidlinkedStack:

:

push（constType&item）

{

if（!

isStackFull（））

{

nodeType*newNode=newnodeType;

newNode->info=item;

newNode->link=NULL;

if（top==NULL）

{

top=newNode;

}

else

{

newNode->link=top;

top=newNode;

}

count++;

cout<

"<

}

}

template

voidlinkedStack:

:

pop（Type&poppedItem）

{

if（!

isStackEmpty（））

{

nodeType*temp=newnodeType;

temp=top;

poppedItem=top->info;

top=top->link;

count--;

cout<

"<

deletetemp;

}

}

template

voidlinkedStack:

:

nodeCount（）

{

cout<<"nodeCount="<

}

//上一节的递归实现逆向链表打印，这是非递归的实现。

template

voidlinkedStack:

:

reversePrint（）//逆向打印的非递归实现...

{

//注释部分可作为链表调用栈的非递归实现。

//nodeType*current=newnodeType;

//current=top;

//while（current!

=NULL）

//{

//pop（current->info）;

//current=current->link;

//}

intpoppedItem=0;

while（!

isStackEmpty（））

{

pop（poppedItem）;

}