一、栈(Stack)的介绍
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
二、具体
1、添加相关头文件
#include <stdio.h>
#include <stdlib.h>
#include <time.h></time.h></stdlib.h></stdio.h>
2、定义栈
typedef struct Stack {
int *data;
int top, size;
} Stack;
3、初始化栈
Stack *init(int n) {
Stack *s = (Stack *)malloc(sizeof(Stack));
s->data = (int *)malloc(sizeof(int) * n);
s->size = n;
s->top = -1;
return s;
}
4、判断是否为空及查看栈顶
int empty(Stack *s) {
return s->top == -1;
}
int top(Stack *s) {
if (empty(s)) return 0;
return s->data[s->top];
}
5、插入
int push(Stack *s, int val) {
if (s == NULL) return 0;
if (s->top + 1 == s->size) return 0;
s->top += 1;
s->data[s->top] = val;
return 1;
}
6、出栈操作
int pop(Stack *s) {
if (s == NULL) return 0;
if (empty(s)) return 0;
s->top -= 1;
return 1;
}
7、清空
void clear(Stack *s) {
if (s == NULL) return ;
free(s->data);
free(s);
return ;
}
8、输出栈
void output(Stack *s) {
printf("stack(%d) = [", s->top + 1);
for (int i = s->top; i >= 0; i--) {
printf(" %d", s->data[i]);
}
printf("]\n");
return ;
}
9、主函数（随机进行20次随机测试）
int main() {
srand(time(0));
#define MAX_OP 20
Stack *s = init(MAX_OP);
for (int i = 0; i < MAX_OP; i++) {
int op = rand() % 2, val = rand() % 100;
switch (op) {
case 0: {
printf("push %d to stack = %d\n", val, push(s, val));
} break;
case 1: {
printf("pop %d from stack = %d\n", top(s), pop(s));
}
}
output(s);
}
return 0;
}
10、完整代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Stack {
int *data;
int top, size;
} Stack;
Stack *init(int n) {
Stack *s = (Stack *)malloc(sizeof(Stack));
s->data = (int *)malloc(sizeof(int) * n);
s->size = n;
s->top = -1;
return s;
}
int empty(Stack *s) {
return s->top == -1;
}
int top(Stack *s) {
if (empty(s)) return 0;
return s->data[s->top];
}
int push(Stack *s, int val) {
if (s == NULL) return 0;
if (s->top + 1 == s->size) return 0;
s->top += 1;
s->data[s->top] = val;
return 1;
}
int pop(Stack *s) {
if (s == NULL) return 0;
if (empty(s)) return 0;
s->top -= 1;
return 1;
}
void clear(Stack *s) {
if (s == NULL) return ;
free(s->data);
free(s);
return ;
}
void output(Stack *s) {
printf("stack(%d) = [", s->top + 1);
for (int i = s->top; i >= 0; i--) {
printf(" %d", s->data[i]);
}
printf("]\n");
return ;
}
int main() {
srand(time(0));
#define MAX_OP 20
Stack *s = init(MAX_OP);
for (int i = 0; i < MAX_OP; i++) {
int op = rand() % 2, val = rand() % 100;
switch (op) {
case 0: {
printf("push %d to stack = %d\n", val, push(s, val));
} break;
case 1: {
printf("pop %d from stack = %d\n", top(s), pop(s));
}
}
output(s);
}
return 0;
}</time.h></stdlib.h></stdio.h>
三、栈的基本概念
要搞清楚这个概念，首先要明白”栈”原来的意思，如此才能把握本质。栈,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。
首先系统或者数据结构栈中数据内容的读取与插入（压入)push和 弹出pop是两回事！压入是增加数据，弹出是删除数据 ，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作 ，但读取栈中的数据是随便的，没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用 即 cpu 与内存的交流通道 ，cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令， 用一个形象的词来形容它就是pipeline（管道线、流水线）。cpu内部交互具体参见 EU与BIU的概念介绍。
以上定义是在经典计算机科学中的解释。
如果有任何问题请留言
Original: https://www.cnblogs.com/HanaKoo/p/16098380.html
Author: HanaKoo
Title: (3)栈的操作
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/619431/
转载文章受原作者版权保护。转载请注明原作者出处！