# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
typedef struct Node
{
int data
struct Node *pNext
}NODE, *PNODE
typedef struct Stack
{
PNODE pTop
PNODE pBottom//pBottem是指向栈底下一个没有实际意义的元素
}STACK, *PSTACK
void init( PSTACK )
void push( PSTACK, int )
void traverse( PSTACK )
int pop( PSTACK, int * )
int empty( PSTACK pS )
int main( void )
{
STACK S//STACK等价于struct Stack
int val
init( &S )//目的是造出一个空栈
push( &S, 1 )//压栈
push( &S, 2 )
push( &S, 3 )
push( &S, 4 )
push( &S, 5 )
push( &S, 6 )
push( &S, 7 )
traverse( &S )//遍历输出
// clear( &S )//清空数据
// traverse( &S )//遍历输出
if( pop( &S, &val ) )
{
printf( "出栈成功,出栈的元素是%d\n", val )
}
else
{
printf( "出栈失败" )
}
traverse( &S )//遍历输出出栈之后的元素
return 0
}
void init( PSTACK pS )
{
pS->pTop = ( PNODE )malloc( sizeof( NODE ) )
if( NULL == pS->pTop )
{
printf( "动态内存分配失败!\n" )
exit( -1 )
}
else
{
pS->pBottom = pS->pTop
pS->pTop->pNext = NULL//或是pS->pBottom = NULL
}
}
void push( PSTACK pS, int val )
{
PNODE pNew = ( PNODE )malloc( sizeof( NODE ) )
pNew->data = val
pNew->pNext = pS->pTop//pS->Top不能改为pS->pBottom
pS->pTop = pNew
}
void traverse( PSTACK pS )
{
PNODE p = pS->pTop
while( p != pS->pBottom )
{
printf( "%d ", p->data )
p = p->pNext
}
printf( "\n" )
}
int empty( PSTACK pS )
{
if( pS->pTop == pS->pBottom )
return 1
else
return 0
}
//把pS所指向的栈出栈一次,并把出栈的元素存入pVal形参所指向的变量中,如果出栈失败,则返回false,否则true
int pop( PSTACK pS, int *pVal)
{
if( empty( pS ) )//pS本身存放的就是S的地址
{
return 0
}
else
{
PNODE r = pS->pTop
*pVal = r->data
pS->pTop = r->pNext
free( r )
r = NULL //为什么要把r赋给NULL呢??
return 1
}
}
//clear清空
void clear( PSTACK pS )
{
if( empty( pS ) )
{
return
}
else
{
PNODE p = pS->pTop
PNODE q = p->pNext
while( p != pS->pBottom )
{
q = p->pNext
free( p )
p = q
}
pS->pTop = pS->pBottom
}
}
#include <stdio.h>#include <stdlib.h>
typedef struct _stack {
int size
int* base
int* sp
} stack
void init(stack* s, int n)
{
s->base = (int*)malloc(sizeof(int)*n)
s->size = n
s->sp = s->base
}
int push(stack* s, int val)
{
if(s->sp - s->base == s->size) {
puts("overflow")
exit(1)
}
return *s->sp++ = val
}
int pop(stack* s)
{
if(s->sp == s->base) {
puts("underflow")
exit(2)
}
return *--s->sp
}
int empty(stack* s)
{
return s->sp == s->base
}
void clean(stack* s)
{
if(s->base)
free(s->base)
}
int main(void)
{
stack s
int i
init(&s, 100)
for(i = 0i <10++i)
printf("%d ", push(&s, i))
putchar('\n')
while(!empty(&s))
printf("%d ", pop(&s))
clean(&s)
return 0
}
