模拟实现顺序栈及其改进

基础班

#include<iostream> #include<time.h> using namespace std; #define MAX 1024 typedef struct { int data[MAX]; int top; }SeqStack; void InitStack(SeqStack *stack) { stack->top = -1; } bool IsEmpty(SeqStack *stack) { if (-1 == stack->top) { return true; } return false; } int SeqStack_Top(SeqStack *stack) { if (!IsEmpty(stack)) { return stack->data[stack->top]; } return 65535; } int SeqStack_Pop(SeqStack *stack) { if (!IsEmpty(stack)) { return stack->data[stack->top--]; } return 65535; } void SeqStack_Push(SeqStack *stack, int val) { if ((MAX - 1)==stack->top) { return; } stack->top++; stack->data[stack->top] = val; } void SeqStack_Destory(SeqStack *stack) { if (!IsEmpty(stack)) { free(stack); } } int main() { srand((unsigned)time(0)); SeqStack stack; InitStack(&stack); for (int i = 0; i < 50; i++) { int res = rand() % 1000; SeqStack_Push(&stack,res ); } printf("栈顶元素%d\n", SeqStack_Top(&stack)); printf("栈中的元素："); for (int i = 0; i < 50; i++) { if (i % 5 == 0) { printf("\n"); } printf("%d\t", SeqStack_Pop(&stack)); } printf("\n"); system("pause"); return 0; }

改进版：

#include<stdio.h> #include<assert.h> #include<malloc.h> #include<CertExit.h> #define INITSIZE 10 #define RESIZE 3 typedef int DataType; typedef struct Stack { DataType *Base; DataType *top; int size; }SeqStack; void initStack(SeqStack &stack) { stack.Base = (DataType*)malloc(INITSIZE*sizeof(DataType)); stack.top=stack.Base; stack.size = INITSIZE; } void PushStack(SeqStack &stack, DataType data) { if (stack.top - stack.Base >= stack.size) { DataType *temp = (DataType*)realloc(stack.Base, (stack.size + RESIZE)*sizeof(DataType)); if (NULL == temp) { exit(0); } stack.Base = temp; stack.size += RESIZE; } *stack.top++ = data; //注意top一般来说指向栈顶元素的下一个位置 } DataType GetTop(SeqStack &stack) { if (stack.Base == stack.top) { printf("空栈！！\n"); return -1; } return *(stack.top - 1);//注意top一般来说指向栈顶元素的下一个位置 } DataType PopStack(SeqStack &stack) { if (stack.Base == stack.top) { printf("空栈！！\n"); return -1; } stack.size--; return *(--stack.top);//注意top一般来说指向栈顶元素的下一个位置 } int main() { SeqStack stack; initStack(stack); PushStack(stack, 12); PushStack(stack, 17); PushStack(stack, 2); PushStack(stack, 128); while (stack.Base != stack.top) { printf("%d\t", PopStack(stack)); } system("pause"); }