栈
一言以蔽之，就是后进的先出（LIFO）。
C语言实现代码：
#include<stdio.h>
#include<stdlib.h> typedef struct Stack
{
/*Stack has three properties.*/
int capacity; //the maximum number of elements stack can hold
int size; //current size of stack
int *elements; //array of elements
}Stack; Stack *createStack(int maxElements)
{
/*Create a Stack.*/
Stack *S;
S=(Stack*)malloc(sizeof(Stack));
/*Initialize its properties*/
S->elements=(int*)malloc(sizeof(int)*maxElements);
S->size=;
S->capacity=maxElements;
/*Return the pointer*/
return S;
} void pop(Stack *S)
{
/*We cannot pop if its size is zero(as it's empty)*/
if(S->size==)
{
printf("Stack is Empty\n");
return;
}
/*Removing an element is equivalent to reducing its size by one!!!*/
else
{
S->size--;
}
return;
} int top(Stack *S)
{
if(S->size==)
{
printf("Stack is Empty\n");
exit();
}
/*Return the topmost element*/
return S->elements[S->size-];
} void push(Stack *S,int element)
{
int *newbase;
/*If the Stack is full,extend it*/
if(S->size>=S->capacity)
{
printf("Stack is Full\n");
newbase=(int*)realloc(S->elements,(S->size+)*sizeof(int));
S->elements=newbase;
S->capacity++;
}
else
{
/*Push the new element on the top of the Stack and increase its size*/
S->elements[S->size++]=element;
}
return;
} int main()
{
int i;
int e;
int n=random()%; //set n as the capacity
printf("next!\n");
Stack *S=createStack(n);
for(i=;i<n;i++)
{
e=random()%;
push(S,e);
printf("%d ",e);
}
printf("\nTop element is %d\n",top(S));
pop(S);
printf("After the first pop,top element is:%d\n",top(S));
pop(S);
printf("After the second pop,top element is:%d\n",top(S));
pop(S);
printf("After the third pop,top element is:%d\n",top(S));
}
关于指针函数啊结构体什么的，一直以来有些迷糊。当由结构体的指针变量只想起成员时，用‘->’，而当表示结构体类型变量的成员，用“.”。以上我用的是Stack *S，故全程使用"->"指向其成员。
最后的测试函数使用random()函数提供数据。例如，random()%20用于获取20以内的数字。
下面一个小例子咯，数制转化，因为最后要把求得的余数按照反序输出得结果，所以可以应用到栈后进先出的特性：
//将上面的测试主函数替换为下面一个主函数加一个转换函数 void convert(int n)
{
Stack *S=createStack();
int e;
while(n!=)
{
push(S,n%);
n/=;
}
while(S->size!=)
{
pop(S);
printf("%d",S->elements[S->size]);
}
} int main()
{
convert();
}
即将十进制1348转换为8进制，结果为2504。
以上为数据结构考前预习系列。唔知能不能预习完嘞。
