顺序栈的表示与实现

一、顺序表实现

说明
  想要使用顺序表实现栈，结构体中应包含栈顶和栈底的指针，同时需要指定栈的存储单元大小（动态可变）。其中栈底指针base用来动态分配栈的内存空间，栈顶指针top用来指定栈顶元素在顺序栈中的位置。
  初始化时$top=base$，表示栈中无元素，而后每压入一个新的元素，先为栈顶内存赋值，再让栈顶指针指向下一块内存单元。
  值得注意的是，栈顶指针总是在栈顶元素的下一个位置。我觉得可以这样理解：假设$0$为最初下标，没有元素时，可以认为此时元素位置是$-1$，而后加入元素，指针上移，始终比元素下标高一个位置。
  另外，对于$push$和$pop$等各种操作，都应该对栈中元素进行判空或判满处理，以使无错误之虞。
代码

//顺序表实现栈
#include<iostream>
#include<cstring>
#include<string>
#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 1024
#define STACKINCREMENT 128
using namespace std;
typedef int ElemType;
typedef struct {
ElemType *top;
ElemType *base;
int stacksize;
}Stack;
int InitStack(Stack &st)
{
st.base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
if (!st.base)
return ERROR;
st.stacksize = STACK_INIT_SIZE;
st.top = st.base;
return OK;
}
int DestroyStack(Stack &st)
{
if (!st.base)
return ERROR;
free(st.base);
return OK;
}
int ClearStack(Stack &st)
{
if (st.base == st.top)
return ERROR;
st.top = st.base;
return OK;
}
bool StackEmpty(Stack &st)
{
return st.top == st.base;
}
int StackLenght(Stack &st)
{
return st.stacksize;
}
int GetTopElem(Stack &st)
{
if (StackEmpty(st))
return ERROR;
return *(st.top - 1);
}
int Push(Stack &st, ElemType e)
{
if (st.top - st.base >= st.stacksize) {
// 如果不够则分配更多空间
st.base = (ElemType *)realloc(st.base, 
(st.stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!st.base)
return ERROR;
st.top = st.base + st.stacksize;
st.stacksize += STACKINCREMENT;
}
*st.top++ = e;
return OK;
}
int Pop(Stack &st, ElemType &e)
{
if (StackEmpty(st))
return ERROR;
e = *--st.top;	// 栈顶指针在栈顶元素的下一个位置
return OK;
}
//学习函数指针详解
void test(Stack &st)
{
ElemType temp;
for (int i = 1;i <= 9;i++)
Push(st, i);
cout <<"top element:"<< GetTopElem(st) << endl;
cout << "stack size:" << (st.top-st.base) << endl;
cout << "inverse:";
for (int i = 1;i <= 9;i++) {
Pop(st, temp);
cout << temp << ' ';
}
cout << endl;
}
int main()
{
Stack s;
InitStack(s);
test(s);
system("pause");
return 0;
}

最后

以上就是神勇电灯胆为你收集整理的顺序栈的表示与实现的全部内容，希望文章能够帮你解决顺序栈的表示与实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。