数据结构-栈 C和C++的实现

时间：2021-10-06 14:57:53

在数据结构中，栈是一种桶状结构，每次往桶里放数据，最后放的数据最先被拿出来，最先放进去的数据最后才能出来（FILO）

C语言：

一、文件清单：

数据结构-栈 C和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;

}
  1. 设置栈的最大深度iMaxSize；
  2. 因为栈中还没有数据，设置栈的的现有长度iLength为0；
  3. 使用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;

}
  1. 栈如果已经被删除则返回
  2. 使用free()来回收分配的空间
  3. 将*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;

}
  1. 如果栈未满，往栈顶放入数据
  2. 增加栈的深度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. 如果栈非空，在不删除任何东西的情况下获取栈顶的首个数据（这里注意数组下标减1）

Stack_pop(MyStack *stack)

bool Stack_pop(MyStack *stack)

{

    if(isStackEmpty(stack))

    {

        return false;

    }

    stack->iLength--;

    return true;

}
  1. 如果栈非空，进行出栈操作，只需要把栈深度指示iLength减1

三、结果：

数据结构-栈 C和C++的实现

第一行：我们使用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测试程序

数据结构-栈 C和C++的实现

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就能达到目的。


三、结果：


数据结构-栈 C和C++的实现


第一行：我们使用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()打印栈为空。
相关文章