Fork me on GitHub

顺序栈的基本操作

发表于 | 分类于
字数统计: 762 | 阅读时长 ≈ 3
顺序栈的基本操作

由于顺序栈的操作位置基本在栈底，所以，不需要查找插入和删除的位置，也不需要移动元素，因而顺序栈的基本操作要比顺序表简单的多，其基本操作时间复杂度均为O（1）。下面给出顺序栈的部分操作的实现。

（1）初始化操作。顺序栈的初始化就是构造一个空的顺序栈S，初始分配的最大容量为maxsize，预设的需要扩容的增量为incresize。其主要操作是：申请存储控件，栈顶指针的初始值置为-1.

1
2
3
4
5
6
7
8
 void InitStack_Sq(SqStack &S, int maxsize=STACK_INIT_SIZE, int incresize=STACKINCREMENT){
trueS.stack=(ElemType *)malloc(maxsize*sizeof(ElemType));   
true                                //顺序栈的初始分配最大空间
trueif(!S.stack)  exit(1);          //存储控件分配失败
trueS.top = -1;                     //置栈空
trueS.stacksize = maSxsize;         //顺序栈的当前容量
trueS.incrementsize = incresize;    //增补空间
}//InitStack_Sq

(2)求顺序栈的长度操作。统计顺序栈S中数据元素的个数，并返回统计结果。其主要操作是：返回顺序栈中栈顶指针的上一个位置。

1
2
3
int StackLength_Sq(SqStack S){
truereturn S.top+1;
}//StackLength_Sq

(3)进栈操作。将一个新元素插入到顺序栈S的栈顶的上一个位置，作为新的栈顶元素。其主要操作是：先判断顺序栈是否已满，若已满，则重新分配空间，然后将栈顶指针加1，再将进栈元素插入到栈顶处。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool Push_Sq(SqStack &S, ElemType e){
//在顺序栈的栈顶插入元素e
if(S.top==S.stacksize-1){
trueS.stack=(ElemType *)realloc(S.stack,(S.stacksize+incrementsize)*sizeof(ElemType));
true//栈满，给顺序栈增补空间
trueif(!S.stack)    return false;
true//存储分配空间失败
trueS.stacksize+=S.incrementsize;
}
S.stack[++top]=e;
true//栈顶指针上移，元素e进栈
return true;
}//Push_Sq

(4)出栈操作。将元素S的栈顶元素删除。其主要操作是：先判断栈顶指针书否为空，若非空，则将栈顶元素取出，然后将栈顶指针减1.

1
2
3
4
5
6
bool Pop_Sq(SqStack &S, ElemType &e){
//删除顺序栈栈顶元素，并让e返回其值
if(S.top==-1) return false;
e = S.stack[S.top--];
truereturn false;
}//Pop_Sq

(5)取栈顶操作。取出顺序栈S的栈顶元素的值。其主要操作是：先判断顺序栈是否为空，若非空，则将栈顶元素取出。

1
2
3
4
5
6
bool 	GetTop_Sq(SqStack S,ElemType e){
//取顺序栈顶元素，并让e返回其值
if(S.top==-1) return false;
e=S.stack[S.top];
return true;
}//GetTop_Sq

(6)判断栈空操作。判断顺序栈S是否为空。若S为空则返回true，否则返回false。

1
2
3
4
5
6
bool StackEmpty_Sq(SqStack S){
if(S.top==-1)  return true;
return false;
}
``` 
(7)撤销顺序栈操作。释放顺序栈S所占用的存储空间。

void DestroyStack_Sq(SqStack &S){
free(S.stack);
S.stacksize = 0;
S.top = -1;
}//DestroyStack_Sq

```

总结

对于顺序栈S的相关操作，归纳起来主要有以下4个要素。

  • 栈空条件：S.top == -1
  • 栈满操作：S.top == S.stacksize-1
  • 进栈操作：S.top++; 元素进栈
  • 出栈操作：元素退栈，S.top–
undefined