堆栈 ( stack )，也可直接称栈。堆栈数据结构只允许在一端进行操作，并按照后进先出( LIFO, Last In First Out )的原理运作。
堆栈数据结构使用两种基本操作：
压栈( push ) ：将数据放入堆栈的顶端，堆栈顶端指针指标+1。
弹栈( pop ) ：将顶端数据资料输出，堆栈顶端指针指标-1。
/**
* <!--
* File : stack.h
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define Element char
#define INIT_SIZE 10
#define INCREMENT_SIZE INIT_SIZE / 2
typedef struct TStack {
Element *base;
Element *top;
int size;
} *Stack;
//栈的构造器,创建空栈
void stackConstructor(Stack &stack){
stack->base = (Element *)malloc(INIT_SIZE * sizeof(Element));
if(!stack->base){
printf("\n为栈分配内存空间失败!\n");
exit(0);
}
stack->top = stack->base; //空栈 top == base
stack->size = INIT_SIZE;
}
//是否为空栈
bool isEmpty(Stack stack){
if(stack->top == stack->base){
return true;
}
return false;
}
//压栈
bool push(Stack &stack, Element e){
if(stack->top - stack->base >= stack->size){ //栈满
stack->base = (Element *)realloc(stack->base, (stack->size + INCREMENT_SIZE) * sizeof(Element));
if(!stack->base){
printf("\n为栈扩展内存空间失败!\n");
return false;
}
stack->top = stack->base + stack->size;
stack->size += INCREMENT_SIZE;
}
*stack->top++ = e;
return true;
}
//弹栈
Element pop(Stack stack){
if(isEmpty(stack)){
printf("\n栈为空,弹栈操作失败!\n");
return ' ';
}
return *--stack->top;
}
/**
* <!--
* File : Stack.cpp
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include "stack.h"
int main() {
Stack stack;
stackConstructor(stack);
push(stack, 'f');
push(stack, 'a');
push(stack, 'n');
push(stack, 'c');
push(stack, 'y');
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
//output[result]: ycnaf
return 0;
}
posted on 2013-02-03 06:40
fancydeepin 阅读(1567)
评论(0) 编辑 收藏