在数据结构中,栈是一种桶状结构,每次往桶里放数据,最后放的数据最先被拿出来,最先放进去的数据最后才能出来(FILO)
C语言:
一、文件清单:
MyStack.h:
#ifndef _MYSTACK_H#define _MYSTACK_H#include#include typedef unsigned char bool;#define true 1;#define false 0;typedef int Elem;typedef struct mystack{ int iMaxSize; int iLength; Elem *Datas;}MyStack;extern bool Stack_Init(MyStack* stack,int size);extern bool Stack_Delete(MyStack *stack);extern bool isStackEmpty(MyStack *stack);extern bool isStackFull(MyStack *stack);extern int Stack_size(MyStack *stack);extern bool Stack_push(MyStack *stack,Elem data);extern bool Stack_top(MyStack *stack,Elem *container);extern bool Stack_bottom(MyStack *stack,Elem *container);extern bool Stack_pop(MyStack *stack);extern void Stack_printf(MyStack *stack);#endif
MyStack.c:
#include "MyStack.h"bool Stack_Init(MyStack* stack,int size);bool Stack_Delete(MyStack *stack);bool isStackEmpty(MyStack *stack);bool isStackFull(MyStack *stack);int Stack_size(MyStack *stack);bool Stack_push(MyStack *stack,Elem data);bool Stack_top(MyStack *stack,Elem *container);bool Stack_bottom(MyStack *stack,Elem *container);bool Stack_pop(MyStack *stack);void Stack_printf(MyStack *stack);bool Stack_Init(MyStack* stack,int size){ if(NULL != stack->Datas) //Stack has been init return false; stack->iMaxSize = size; stack->iLength =0; stack->Datas = (Elem*)malloc(size * sizeof(Elem)); return true;}bool Stack_Delete(MyStack *stack){ if(NULL == stack->Datas) //Stack does not exist return false; free(stack->Datas); stack->Datas=NULL; return true;}bool isStackEmpty(MyStack *stack){ if(0== stack->iLength) { return true; } return false ;}bool isStackFull(MyStack *stack){ if(stack->iMaxSize == stack->iLength) { return true; } return false ; }int Stack_size(MyStack *stack){ return stack->iLength;}bool Stack_push(MyStack *stack,Elem data){ if(isStackFull(stack)) { return false; } stack->Datas[stack->iLength] = data; stack->iLength++; return true;}bool Stack_top(MyStack *stack,Elem *container){ if(isStackEmpty(stack)) { return false ; } *container = stack->Datas[stack->iLength-1]; return true;}bool Stack_bottom(MyStack *stack,Elem *container){ if(isStackEmpty(stack)) { return false; } *container = stack->Datas[0]; return true;}bool Stack_pop(MyStack *stack){ if(isStackEmpty(stack)) { return false; } stack->iLength--; return true;}void Stack_printf(MyStack *stack){ int i; printf("Stack:"); for(i=0;iiLength;i++) { printf(" %d ",stack->Datas[i]); } printf(" \r\n");}
main.c:
#include "MyStack.h"int main(){ MyStack stack={ 0}; int top; int bottom; //Stack_Init() Stack_Init(&stack,5); //Stack_push() and Stack_printf() Stack_push(&stack,1); Stack_push(&stack,2); Stack_push(&stack,3); Stack_push(&stack,4); Stack_push(&stack,5); Stack_push(&stack,6); Stack_printf(&stack); //Stack_size() printf("stack length:%d\r\n",Stack_size(&stack)); //Stack_top() Stack_bottom() Stack_top(&stack,&top); Stack_bottom(&stack,&bottom); printf("stack top:%d,stack bottom:%d\r\n",top,bottom); //Stack_pop() Stack_pop(&stack); Stack_printf(&stack); Stack_pop(&stack); Stack_pop(&stack); Stack_pop(&stack); Stack_pop(&stack); Stack_pop(&stack); Stack_pop(&stack); Stack_printf(&stack); system("pause"); return 1;}
二、函数详解:
Stack_Init(MyStack* stack,int size)
bool Stack_Init(MyStack* stack,int size){ if(NULL != stack->Datas) //Stack has been init return false; stack->iMaxSize = size; stack->iLength =0; stack->Datas = (Elem*)malloc(size * sizeof(Elem)); return true;}
- 设置栈的最大深度iMaxSize;
- 因为栈中还没有数据,设置栈的的现有长度iLength为0;
- 使用malloc()函数为栈中的数据区*Datas分配空间;
Stack_Delete(MyStack *stack)
bool Stack_Delete(MyStack *stack){ if(NULL == stack->Datas) //Stack does not exist return false; free(stack->Datas); stack->Datas=NULL; return true;}
- 栈如果已经被删除则返回
- 使用free()来回收分配的空间
- 将*Datas置为NULL
Stack_push(MyStack *stack,Elem data)
bool Stack_push(MyStack *stack,Elem data){ if(isStackFull(stack)) { return false; } stack->Datas[stack->iLength] = data; stack->iLength++; return true;}
- 如果栈未满,往栈顶放入数据
- 增加栈的深度iLength来指示
Stack_top(MyStack *stack,Elem *container)
bool Stack_top(MyStack *stack,Elem *container){ if(isStackEmpty(stack)) { return false ; } *container = stack->Datas[stack->iLength-1]; return true;}
- 如果栈非空,在不删除任何东西的情况下获取栈顶的首个数据(这里注意数组下标减1)
Stack_pop(MyStack *stack)
bool Stack_pop(MyStack *stack){ if(isStackEmpty(stack)) { return false; } stack->iLength--; return true;}
- 如果栈非空,进行出栈操作,只需要把栈深度指示iLength减1
三、结果:
第一行:我们使用Stack_push()函数放入了1-6,6个整数,但是栈被设置的大小只有5,所以“6”没有入栈。调用printf()打印只能看到1到5。
第二行:调用Stack_size()函数获取到的栈深度为5。
第三行:此时栈中有5个数据,通过Stack_top()和Stack_bottom栈顶数据为“5”,栈底数据为“1”。
第四行:调用Stack_pop()函数进行出栈操作后5被移除,栈中剩下1-4,调用printf()打印出1-4
第五行:连续调用6次Stack_pop(),因为栈中只有4个元素,所以实际只有4次pop生效,调用printf()打印栈为空。
最后连续调用两次Stack_delete(),根据程序第二次会没有执行free(),所以程序没有发生崩溃。
C++语言:
一、文件清单:
包含两个文件,MyStack.h中用类模板实现Stack类
Main.c中为main测试程序
MyStack.h:
#ifndef _MYSTACK_H#define _MYSTACK_H#includeusing namespace std;template class MyStack{public: MyStack(int size); ~MyStack(); bool isStackEmpty(); bool isStackFull(); int getStackLength(); bool push(T data); bool getTop(T *data); bool getBottom(T *data); bool pop(); void printf();private: T *m_tDatas; int m_iMaxSize; int m_iLength;};template MyStack ::MyStack(int size){ m_iMaxSize = size; m_iLength = 0; m_tDatas = new T[size];}template MyStack ::~MyStack(){ delete []m_tDatas ;}template bool MyStack ::isStackEmpty(){ if(0!=m_iLength) { return false ; } return true;}template bool MyStack :: isStackFull(){ if(m_iMaxSize != m_iLength) { return false; } return true;}template int MyStack ::getStackLength(){ return m_iLength;}template bool MyStack ::push(T data){ if(!isStackFull()) { m_tDatas[m_iLength]=data; m_iLength++; return true; } return false;}template bool MyStack ::getTop(T *data){ if(!isStackEmpty()) { *data = m_tDatas[m_iLength-1]; return true; } return false ;}template bool MyStack ::getBottom(T *data){ if(!isStackEmpty()) { *data = m_tDatas[0]; return true; } return false ;}template bool MyStack ::pop(){ if(!isStackEmpty()) { m_iLength--; return true; } return false ;}template void MyStack ::printf(){ cout<<"Stack:"; for(int i=0;i
main.cpp(用于测试)
#include#include "MyStack.h"using namespace std;int main(){ MyStack mystack(5); float top; float bottom; //push(); mystack.push(1.0f); mystack.push(2.0f); mystack.push(3.0f); mystack.push(4.0f); mystack.push(5.0f); mystack.push(6.0f); mystack.printf(); //getTop();getBottom() mystack.getTop(&top); mystack.getBottom(&bottom); cout<<"top:"< <<", bottom:"< <
二、函数详解:
构造函数:
templateMyStack ::MyStack(int size){ m_iMaxSize = size; m_iLength = 0; m_tDatas = new T[size];}
m_iMaxSize 用于记录栈的最大深度,设置为输入值。
m_iLength用于记录栈的当前大小,构造时栈为空,所以置0。
m_tDatas为栈数据,这里为它分配空间。
push(T data):
templatebool MyStack ::push(T data){ if(!isStackFull()) { m_tDatas[m_iLength]=data; m_iLength++; return true; } return false;}
如果栈还没满,就往栈顶放入数据,同时m_iLength++来指示栈的容量增加了。
getTop(T *data):
templatebool MyStack ::getTop(T *data){ if(!isStackEmpty()) { *data = m_tDatas[m_iLength-1]; return true; } return false ;}
如果栈非空,获取栈顶的数据,这里注意获取对应数据时,数组的下标减一。
pop():
templatebool MyStack ::pop(){ if(!isStackEmpty()) { m_iLength--; return true; } return false ;}
如果栈非空,移除栈顶的数据,只需要改变m_iLength就能达到目的。
三、结果:
第一行:我们使用push()函数放入了1-6,6个浮点数,但是栈被设置的大小只有5,所以“6”没有入栈。调用printf()打印只能看到1到5。
第二行:此时栈中有5个数据,栈顶数据为“5”,栈底数据为“1”。
第三行:调用pop()函数进行出栈操作后5被移除,栈中剩下1-4,调用printf()打印出1-4
第四行:连续调用10次pop(),因为栈中只有4个元素,所以实际只有4次pop生效,调用printf()打印栈为空。