初学栈Ⅰ

初学栈Ⅰ


接触了链表之后,感觉栈的结构还算是十分简单的。

(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。

在计算机系统中,栈则是一个动态内存区域。程序可以将数据压入栈中,也可以将数据从栈顶弹出。

栈的结构示意

栈的顺序储存

用C语言表示大概是这样的:

1
2
3
4
5
struct stack
{
int data[Max_size];
int top; //表示栈顶
};

入栈操作

栈满的判断条件是s->top == Max_size,因为栈顶元素处于Max_size - 2的位置时,top的值已经为Max_size - 1,显然已到达数组最大下标。这就意味着栈实际只能存储Max_size - 1个元素

1
2
3
4
5
6
7
int push(struct stack *s,int num)
{
if(s->top == Max_size-1) return -1;
s->top++;
s->data[s->top] = num;
return 0;
}

出栈操作

变量 t 用来返回pop出来的元素。

1
2
3
4
5
6
7
8
int pop(struct stack *s,int *t)
{
*t = s->data[s->top];
if(s->top == 0)
return -1;
s->top--;
return 0;
}

创建一个栈

1
2
3
4
5
6
7
8
9
10
11
12
void create_stack(struct stack *s,int n)
{
int num;
s->top = 0;
for(int i=0; i<n; i++)
{
scanf("%d",&num);
if(push(s,num)==-1)
break;
}
return;
}

遍历输出栈内的元素

1
2
3
4
5
6
7
8
9
10
11
12
void print(struct stack *s)
{
while(1)
{
int t;
if(~pop(s,&t))
printf("%d ",t);
else break;
}
printf("\n");
return;
}