在数据结构中，栈是一种桶状结构，每次往桶里放数据，最后放的数据最先被拿出来，最先放进去的数据最后才能出来（FILO）
C语言：
一、文件清单：
MyStack.h:
#ifndef _MYSTACK_H
#define _MYSTACK_H
#include <stdio.h>
#include <stdlib.h> 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 =;
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(== 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-];
return true;
} bool Stack_bottom(MyStack *stack,Elem *container)
{
if(isStackEmpty(stack))
{
return false;
} *container = stack->Datas[];
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=;i<stack->iLength;i++)
{
printf(" %d ",stack->Datas[i]);
}
printf(" \r\n");
}
main.c:
#include "MyStack.h" int main()
{
MyStack stack={};
int top;
int bottom; //Stack_Init()
Stack_Init(&stack,); //Stack_push() and Stack_printf()
Stack_push(&stack,);
Stack_push(&stack,);
Stack_push(&stack,);
Stack_push(&stack,);
Stack_push(&stack,);
Stack_push(&stack,);
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 ;
}
二、函数详解：
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 =;
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-];
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 #include<iostream>
using namespace std; template <typename T>
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 <typename T>
MyStack<T>::MyStack(int size)
{
m_iMaxSize = size;
m_iLength = ;
m_tDatas = new T[size];
}
template <typename T>
MyStack<T>::~MyStack()
{
delete []m_tDatas ;
} template <typename T>
bool MyStack<T>::isStackEmpty()
{
if(!=m_iLength)
{
return false ;
}
return true;
} template <typename T>
bool MyStack<T>:: isStackFull()
{
if(m_iMaxSize != m_iLength)
{
return false;
}
return true;
} template <typename T>
int MyStack<T>::getStackLength()
{
return m_iLength;
} template <typename T>
bool MyStack<T>::push(T data)
{
if(!isStackFull())
{
m_tDatas[m_iLength]=data;
m_iLength++;
return true;
}
return false;
} template <typename T>
bool MyStack<T>::getTop(T *data)
{
if(!isStackEmpty())
{
*data = m_tDatas[m_iLength-];
return true;
}
return false ;
} template <typename T>
bool MyStack<T>::getBottom(T *data)
{
if(!isStackEmpty())
{
*data = m_tDatas[];
return true;
}
return false ;
} template <typename T>
bool MyStack<T>::pop()
{
if(!isStackEmpty())
{
m_iLength--;
return true;
}
return false ;
} template <typename T>
void MyStack<T>::printf()
{
cout<<"Stack:";
for(int i=;i<m_iLength;i++)
{
cout<<m_tDatas[i];
}
cout<<endl;
} #endif
main.cpp(用于测试)
#include <iostream>
#include "MyStack.h" using namespace std; int main()
{
MyStack<float> mystack();
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:"<<top<<", bottom:"<<bottom<<endl; //pop()
mystack.pop();
mystack.printf(); for(int i=;i<;i++)
{
mystack.pop();
}
mystack.printf(); system("pause");
return ;
}
二、函数详解：
构造函数：
template <typename T>
MyStack<T>::MyStack(int size)
{
m_iMaxSize = size;
m_iLength = ;
m_tDatas = new T[size];
}
m_iMaxSize 用于记录栈的最大深度，设置为输入值。
m_iLength用于记录栈的当前大小，构造时栈为空，所以置0。
m_tDatas为栈数据，这里为它分配空间。
push(T data):
template <typename T>
bool MyStack<T>::push(T data)
{
if(!isStackFull())
{
m_tDatas[m_iLength]=data;
m_iLength++;
return true;
}
return false;
}
如果栈还没满，就往栈顶放入数据，同时m_iLength++来指示栈的容量增加了。
getTop(T *data):
template <typename T>
bool MyStack<T>::getTop(T *data)
{
if(!isStackEmpty())
{
*data = m_tDatas[m_iLength-];
return true;
}
return false ;
}
如果栈非空，获取栈顶的数据，这里注意获取对应数据时，数组的下标减一。
pop():
template <typename T>
bool MyStack<T>::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()打印栈为空。