栈是一种先进后出的线性数据结构,规定只允许在一端进行插入和删除元素的操作。其中进栈操作又叫做压栈(Push),出栈操作又叫做弹出(Pop)。允许进行操作的一端叫做栈顶(top),另一端叫做栈底(base)。
分类
代码实现
顺序栈
1.构建栈的结构
1 2 3 4 5
| #define MAXSIZE 1024 typedef struct stack{ int data[MAXSIZE]; int top; }Stack;
|
2.初始化
1 2 3 4 5 6 7 8 9 10 11 12 13
| Stack *Init(){ Stack stack; stack = (Stack*)malloc(sizeof(Stack)); if(!stack){ printf("Memory allocation failed!"); return NULL; } else{ stack->top = -1; printf("Init successfully!"); return stack; } }
|
3.判断栈是否为空
1 2 3 4 5 6 7
| int isEmpty(Stack* stack){ if(stack->top == -1){ printf("The stack is empty!"); return 1; } return 0; }
|
4.判断栈是否满
1 2 3 4 5 6 7
| int isFull(Stack* stack){ if(stack->top == MAXSIZE-1){ printf("The satck is full!"); return 1; } return 0; }
|
5.进栈操作(Push)
1 2 3 4 5 6
| void Push(Stack* stack,int item){ if(isFull(stack)){ return; } stack->data[++stack->top] = item; }
|
入站操作先移动Top,再压入元素
6.出栈操作(Pop)
1 2 3 4 5 6
| int Pop(Stack* stack){ if(isEmpty(stack)){ return -99; } return stack->data[stack->top--]; }
|
7.遍历操作
1 2 3 4 5 6
| void Traverse(Stack* satck){ printf("The items in the stack are:\n"); for (int i=stack->top;i >= 0;i--){ printf ("%d\n",stack->data[i]); } }
|
链式栈
1.构建栈的结构
1 2 3 4
| typedef struct node{ int data; struct node* next; }Node;
|
2.初始化栈
1 2 3 4 5 6 7 8 9 10 11 12 13
| Node* Init(){ Node* s; s = (Node*)malloc(sizeof(Node)); if(!s){ printf("Memory allocation failed!"); return NULL; } else{ printf("Init successfully!"); s->next = NULL; return s; } }
|
3.判断栈是否为空
1 2 3
| int isEmpty(Node* s){ return (s->next == NULL); }
|
4.进栈操作
1 2 3 4 5 6 7 8 9 10 11
| void Push(Node* s,int item){ Node* node; node = (Node*)malloc(sizeof(Node)); if(!node){ printf("Memory allocation failed!"); return NULL; } node->data = item; node->next = s->next; s->next = node; }
|
5.出栈操作
1 2 3 4 5 6 7 8 9 10 11 12 13
| int Pop(Node* s){ Node* Top; int data; if(isEmpty(s)){ printf("The stack is empty!"); return -99; } Top = s->next; s->next = Top->next; data = Top->data; free(Top); return data; }
|
6.遍历操作
1 2 3 4 5 6 7 8 9
| void Traverse(Node* s){ printf("The items in the stack are:\n"); Node* p; p = s; while (p->next != NULL){ printf("%d\n",p->data); p = p->next; } }
|