栈也比较的简单,后进先出嘛。
使用单链表实现比较简单,在表头节点后面push与pop就可以了。但是每次push或者pop均需要malloc或者free,开销可能有点大。所以流行的做法是使用数组实现栈。
栈的结构体定义:
struct stack
{
unsigned int capacity;
int topPoint;
int *num;
};
支持的基本操作有:
/*创建一个空的栈*/
stack * createStack(int capacity)
/*判断一个栈是否为空
栈为空的话返回1,否则返回0*/
int isEmpty(stack *S)
/*判断一个栈是否满了
栈满的话返回1,否则返回0*/
int isFull(stack *S)
/*把一个数压到栈里*/
void push(int element, stack * S)
/*出栈,返回栈顶元素*/
int pop(stack *S)
/*仅仅获得栈顶元素*/
int top(stack *S)
/*释放栈空间*/
void deleteStack(stack *S)
参考代码:
#include<stdio.h>
#include<stdlib.h>
struct stack
{
unsigned int capacity;
int topPoint;
int *num;
};
typedef struct stack stack;
/*创建一个空的栈*/
stack * createStack(int capacity)
{
stack * S = (stack*)malloc(sizeof(stack));
S->capacity=capacity;
S->topPoint=-1;
S->num =(int*)malloc(sizeof(int)*capacity);
return S;
}
/*判断一个栈是否为空
栈为空的话返回1,否则返回0*/
int isEmpty(stack *S)
{
return S->topPoint==-1?1:0;
}
/*判断一个栈是否满了
栈满的话返回1,否则返回0*/
int isFull(stack *S)
{
return S->topPoint==S->capacity-1?1:0;
}
/*把一个数压到栈里*/
void push(int element, stack * S)
{
if(isFull(S))
{
printf("stack is full\n");
exit(1);
}
S->num[++S->topPoint]=element;
}
/*出栈,返回栈顶元素*/
int pop(stack *S)
{
if(isEmpty(S))
{
printf("stack is empty\n");
exit(1);
}
return S->num[S->topPoint--];
}
/*仅仅获得栈顶元素*/
int top(stack *S)
{
if(isEmpty(S))
{
printf("stack is empty\n");
exit(1);
}
return S->num[S->topPoint];
}
/*释放栈空间*/
void deleteStack(stack *S)
{
if(S!=NULL)
{
free(S->num);
free(S);
}
}