[数据结构与算法]在Codesys基于链表实现栈LIFO数据结构详细说明+代码实例

一、 栈定义

栈是一种后进先出(LIFO——last in first out)线性表,它只允许在表的后端（tail）进行插入(push)和删除(pop)操作。

二、栈实现

实现栈，我们可以使用单向链表（逆向），链表中的每个结点不仅包含值，还包含链接到上一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。蓝色箭头显示单个链接列表中的结点是如何组合在一起的

三、 栈设计

我们分别采用c++和codesys中st语言进行实现基于链表的栈操作

(1) C++ 语言实现

功能如下

• Push(value) : 向栈顶插入一个元素，成功返回true
• pop():获得栈顶元素并弹出
• Empty(): 判断栈是否为空，为空返回true
• Size():获得栈的元素个数

typedef int DataElement;//用户自定义的数据

typedef struct StackElement//栈元素
{
    DataElement  mdata;//用户自定义的数据
    StackElement* Pre;//指向下一个节点
 }StackElement;
 
//通过链表实现队列
class ListStack
{
public:
    ListStack() {};
    ~ListStack() {};
private:
   
    StackElement* pTail = 0;//栈尾指针
public:
bool push(DataElement _data) 
    {
     // 申请一个结点空间
        StackElement* pTemp = (StackElement*)malloc(sizeof(StackElement));
         pTemp->mdata = _data;// 申请一个结点空间
         pTemp->Pre= 0;// 结点的next设为NULL
          if (Empty()) // 判断栈尾是否为空，用于第一次入队
          {
             pTail = pTemp; 
          }
          else
         {
          pTemp->Pre = pTail;// 让pTail成为当前尾部的上一结点
           pTail = pTemp;// 尾部指针指向pTemp
         }
         return true;
     }
     DataElement pop() 
    {
    DataElement  mdata = 0;
        if (Empty())
            return mdata ;
        if (pTail->Pre== 0)// 判断栈是否就1个,如果只有一个 ，移除后队列为空 
        {
           delete(pTail);//清除移除的内存空前
            pTail = 0;  
        }
        else
        {
          StackElement* pTemp = pTail;
         pTail = pTail->Pre;//移动头部指针
          delete(pTemp);//清除移除的内存空前
        }
        return true;
    };

     //返回节点个数
     int Size()
     {
         int iSize  = 0;
         StackElement* pTemp = pTail;
         while (pTemp != 0)
          {
             iSize = iSize + 1;
             pTemp = pTemp->Pre;
          }
        return iSize;
     }
     //判断栈是否为空
     bool Empty()
     {
       if (pTail == 0)
          return true;
       else
         return false;
     }
}

示例如下

(2) Codesys 实现

• 编程软件： Codesys V3.5 SP17
• 运行设备：PC电脑
• 编程语言： ST

定义结构体

//栈操作的数据
TYPE ListStackElement :
STRUCT
	mData : BaseElement;
	pPre : POINTER TO ListStackElement;
END_STRUCT
END_TYPE

其中 BaseElement 是一个别名，其定义如下，这里BaseElement 是用户自定义数据(比如结构体)，采用别名是方便替换。

TYPE BaseElement : INT; END_TYPE

定义功能块（FUNCTION_BLOCK）： ListQueue，实现如下函数

• Push(value) : 向栈顶插入一个元素，成功返回true
• pop():获得栈顶元素并弹出
• Empty(): 判断栈是否为空，为空返回true
• Size():获得栈的元素个数

示例如下

PROGRAM PLC_PRG
VAR
	t  : ListStack;
END_VAR

VAR
	bInit :BOOL:= FALSE;
	isize : INT;
	ivar1: ARRAY[0..10] OF BaseElement;
END_VAR

IF bInit = FALSE THEN 
	
bInit := TRUE;

t.Push(11);//入栈 ，返回TRUE
t.Push(22);//入栈 ，返回TRUE
t.Push(33);//入栈 ，返回TRUE
isize := t.Size();//返回3
ivar1[0] := t.Pop(); //返回33
ivar1[1] := t.Pop(); //返回22

END_IF

四、 Codesys代码下载