数据结构栈的代码实现(C语言)

一 、栈的顺序代码实现

bool InitStack(SqStack *s) {s->base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof(ElemType));if(s->base == NULL) {return false;}s->top = s->base;s->stack_size = STACK_INIT_SIZE;return true;}

判断栈是否为空

bool isEmpty(SqStack *s) {return s->base == s->top? true : false;}

获得栈中元素的个数

int getLength(SqStack *s) {return s->top - s->base;}

打印栈中的元素

void printStack(SqStack *s) {while(s->top != s->base) {s->top--;printf("elems in the stack :%d\n", *(s->top));}}

向栈中插入元素

bool putStack(SqStack *s, ElemType e) {//栈已满重新分配存储空间if(s->top - s->base >= s->stack_size) {s->base = (ElemType *) realloc(s->base,(s->stack_size + STACK_INCREASEMENT)*sizeof(SqStack));if(s->base == NULL)return false;s->top = s->base + s->stack_size;s->stack_size += STACK_INCREASEMENT;}//入栈*(s->top) = e;s->top++;return true;}

栈中元素出栈

int outStack(SqStack *s) {if(isEmpty(s)) return NULL;s->top--;ElemType e = *(s->top);return e;}

清空栈

bool clearStack(SqStack *s) {s->top = s->base;return true;}

主函数

int main(){int n, tmp;SqStack S;InitStack(&S);printf("请输入要入栈的元素个数:");scanf("%d",&n);for (int i = 0; i < n; i++) {printf("请输入第 %d 个需要入栈的元素:",i+1);scanf("%d",&tmp);putStack(&S, tmp);}printf("length of S:%d \n",getLength(&S));printf("the out stack elem is : %d \n",outStack(&S));printf("length of S:%d \n",getLength(&S));printStack(&S);clearStack(&S);printf("the length of stack after cleared : %d", getLength(&S));return 0;}

二 、栈的链式代码实现

void initStack(PSTACK pStack) {pStack->pTop = (PNODE) malloc(sizeof(NODE));if (NULL != pStack->pTop) {pStack->pBottom = pStack->pTop;pStack->pTop->pNext = NULL;} else {printf("内存分配失败!程序退出!\n");exit(-1);}return;}

向栈中添加元素

void pushStack(PSTACK pStack, int val) {//动态创建一个新结点PNODE pNew = (PNODE) malloc(sizeof(NODE));//设置新结点的数据域的值pNew->data = val;//将新结点的指针域指向之前建的空节点pNew->pNext = pStack->pTop; //pStack->pTop不能换成pStack->pBottom//pTop指向新的结点pStack->pTop = pNew;}

栈中元素出栈

bool popStack(PSTACK pStack, int *pVal) {if (isEmpty(pStack)) {return false;} else {//先保存栈顶元素的地址，然后将pTop指向下一元素,最后释放之前栈顶元素的内存PNODE rNode = pStack->pTop;*pVal = rNode->data;pStack->pTop = rNode->pNext;free(rNode);return true;}}

判断栈是否为空

bool isEmpty(PSTACK pStack) {if (pStack->pTop == pStack->pBottom)return true;elsereturn false;}

遍历栈中的元素

void traverseStack(PSTACK pStack) {//将栈顶赋给一个临时结点,因为在遍历栈的时候不能销毁栈PNODE pNode = pStack->pTop;//循环遍历栈,直到栈底while (pStack->pBottom != pNode) {printf("%d ", pNode->data);pNode = pNode->pNext;}printf("\n");return;}

清空栈

void clearStack(PSTACK pStack) {//栈为空，则退出该函数if (isEmpty(pStack)) {return;} else {//两个结点指针变量用来释放栈中元素的内存PNODE p = pStack->pTop;PNODE q = NULL;//循环释放内存while (p != pStack->pBottom) {q = p->pNext;free(p);p = q;}//将栈顶和栈底指向同一个指针域为空的结点pStack->pTop = pStack->pBottom;return;}}

主函数

int main(void) {PSTACK stack;int val, param, a;initStack(stack);printf("请输入入栈的个数:");scanf("%d",&a);for (int i = 0; i < a; i++) {printf("请输入第 %d 个入栈的数:",i+1);scanf("%d",&param);pushStack(stack, param);}traverseStack(stack);//调用出栈的函数if (popStack(stack, &val))printf("出栈成功，出栈的元素值为：%d\n", val);elseprintf(" 出栈失败!");//调用清空栈的函数clearStack(stack);traverseStack(stack);system("pause");return 0;}