一、栈的定义和特点:
1.定义:只能在表的一端（栈顶）进行插入和删除运算的线性表。
2.逻辑结构:与线性表相同，仍为一对一关系。
3.存储结构:用顺序栈或链栈存储均可，但以顺序栈更常见。
4.运算规则:后进先出 或 先进后出。
5.实现方式:(1)初始化、(2)压栈、(3)出栈、(4)取栈顶元素值、(5)判断栈满、(6)栈判空。
6.解决顺序栈溢出的一个方法是:双栈共享一个栈空间。
二、顺序栈:
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
说明：
1.base表示栈底指针，在判断出栈、初始化和重新分配空间的时候需要用到。
2.top表示栈顶指针，是栈最关键和核心的组成，入栈时top向上移动，出栈时top向下移动。
3.此处的stacksize并不表示当前的栈中的元素数量，而是表示栈的容量，也就是能装多少个元素。
(1)栈的初始化：
Status InitStack( SqStack &S )
{
S.base =new SElemType[MAXSIZE]；
if( !S.base ) return OVERFLOW;
S.top = S.base;
S.stackSize = MAXSIZE;
return OK;
}
说明：
1.顺序栈初始化无非就是给栈分配连续的内存空间，base是栈底指针，在上面提到过，它用来指示一段连续的内存空间的首地址，也就是用来初始化。
2.分配空间不意味着一定会有那么多空间，所以判断也不可缺少。
3.分配空间后，base和top的地址应该一致，此时top还没有移动。
(2)压栈:
Status Push( SqStack &S, SElemType e)
{
if( S.top - S.base== S.stacksize ) // 栈满
return ERROR;
*S.top++=e;
return OK;
}
说明：
1.压栈是栈的核心操作，关键步骤无非是*S->top++=elem;但是在进行此步操作时，一定要判断栈是否超出容量。
2.如果栈超出容量，则要在进行原空间的基础上重新分配空间，realloc是关键的命令。
(3)出栈:
Status Pop( SqStack &S, SElemType &e)
{
if( S.top == S.base ) // 栈空
return ERROR;
e＝ *--S.top;
return OK;
}
说明：
1.出栈是简单操作，其实这里并没有完美的实现这个效果，你应该考虑到如果在扩容后又迅速减小，会造成大量的空间浪费。
(4)取顺序栈栈顶元素:
Status GetTop( SqStack S, SElemType &e)
{
if( S.top == S.base ) return ERROR; // 栈空
e = *( S.top – 1 );
return OK;
}
1.判断是否空栈，若空则返回错误
2.否则通过栈顶指针获取栈顶元素
(5栈的判空:
bool StackEmpty( SqStack S )
{
if(S.top == S.base) return true;
else return false;
}
(6)求顺序栈长度:
int StackLength( SqStack S )
{
return S.top – S.base;
}
(7)清空顺序栈:
Status ClearStack( SqStack S )
{
if( S.base ) S.top = S.base;
return OK;
}
(8)销毁顺序栈:
Status DestroyStack( SqStack &S )
{
if( S.base )
{
delete S.base ;
S.stacksize = 0;
S.base = S.top = NULL;
}
return OK;
}
.
顺序栈和顺序表的对比:
京公网安备 11010502036488号