『C++&C语言』数据结构-栈(附上STL栈)

『C++&C 语言』数据结构-栈(附上 STL 栈)

数据结构–栈(附上 STL 栈)

定义:
栈是一种只能在某一端插入和删除数据的特殊线性表。他按照先进先出的原则存储数据,先进的数据被压入栈底,最后进入的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后被压入栈的,最先弹出)。因此栈也称先进后出表。
允许进行插入删除操作的一端称为栈顶,另一端称为栈底。栈底固定,栈顶浮动。插入元素称为进栈,删除一个元素称为进栈,栈内元素为零称为空栈。

我们今天讲一下 STL(标准模板库)的栈,和自己实现的栈(顺序栈,链式栈)

先说 STL 的栈 stack

stack 成员函数:
bool empty ( ) ————>栈为空返回 true,否则返回 false;
void pop ( ) ————>删除栈顶元素,出栈;
void push(const TYPE&value)————> 插入新元素 value,放置在栈顶进栈;TYPE:类型 int,char…;
size_type size ( ) ————> 返回堆栈中元素个数;(注意注意!!!!切不可赋值给 int ,很容易超过 int 的范围
TYPE&top()————> 查看当前栈顶元素;
注:TYPE 取决于声明的类型

stack 声明:

stackdemo;

格式 stack<类型(int double char….)> 名字

stack 函数调用:

stack<type> demo;//type可以是int可以是double也可以自定义数据类型
demo.push(val); //返回值void
demo.empty();//返回值为bool代表是否为空
demo.size();//返回栈内元素数量
demo.pop();//栈顶出栈
demo.top();//取出栈顶元素

自己写的顺序栈

一般都是类内声明了,类外定义,但是为了给大家直观的感受,我就写里面了,其次 getTop 的函数本来应该是返回 top 值但是鉴于每次去之前都需要判断是不是为空,就改成了我代码里的样子;

#include <iostream>
#define MaxSize 5000
using namespace std;
template <typename T>
class Stack
{
    T data[MaxSize];
    int top;
public:
    void InitStack( )
    {
         top = -1;
    }
    bool StackEmpty( )
    {
        if( top==-1)
            return true;
        else
            return false;
    }
    bool Push(T e)
    {
        if(top==MaxSize-1)
            return false;
        data[++top]=e;
        return true;
    }
    bool Pop( )
    {
        if( top==-1)
            return false;
        return true;
    }
    bool GetTop(T &x)
    {
        if( top==-1) return false;
        x = data[ top];
        return true;
    }
    bool Clear( )
    {
         top = -1;
    }
};
int main()
{

}



#include <iostream>
using namespace std;
template<class T>class Stack
{
private:
    struct Node
    {
        T data;
        Node *next;
    };
    Node *head;
    Node *p;
    int length;

public:
    Stack()
    {
        head = NULL;
        length = 0;
    }
    void push(T n)//入栈
    {
        Node *q = new Node;
        q->data = n;
        if (head == NULL)
        {
            q->next = head;
            head = q;
            p = q;
        }
        else
        {
            q->next = p;
            p = q;
        }
        length++;
    }

    T pop()//出栈并且将出栈的元素返回
    {
        if (length <= 0)
        {
            abort();
        }
        Node *q;
        int data;
        q = p;
        data = p->data;
        p = p->next;
        delete(q);
        length--;
        return data;
    }
    int size()//返回元素个数
    {
        return length;
    }
    T top()//返回栈顶元素
    {
        return p->data;
    }
    bool isEmpty()//判断栈是不是空的
    {
        if (length == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    void clear()//清空栈中的所有元素
    {
        while (length > 0)
        {
            pop();
        }
    }
};
int main()
{
    Stack<char> s;
    s.push('a');
    s.push('b');
    s.push('c');
    while (!s.isEmpty())
    {
        cout << s.pop() << endl;
    }
    system("pause");
    return 0;
}

『C++&C语言』数据结构-栈(附上STL栈)
https://chiamzhang.github.io/2024/06/29/『C++&C语言』数据结构-栈(附上STL栈)/
Author
Chiam
Posted on
June 29, 2024
Licensed under