数据结构C++之栈和队列:链栈(即用链表实现栈)

对于栈的结构,比如说现在有一个圆筒,有五个直径恰好等于圆筒直径的小球,将五个小球依次放入圆筒中,圆筒恰好被填满。那么此时,第一个放进去的小球就是栈底元素,最后一个放进去的小球就是栈顶元素。如果想要取出第一个小球,那么必须要先把第一个小球上面的四个小球取出才行。也就是说,最先进入圆筒的小球,只能最后才能被取出来;而最后放进去的小球,可以最先被取出来。这就是一个简单的栈。将小球取出的过程即为栈内元素出栈的过程。

如果想用链表来实现栈的功能,其实操作要比创建一个单链表简单的多。

简单之处就在于不需要建立头指针,只需要建立一个top指针和一个临时指针即可。用top指针来指向栈顶元素。

数据结构C++之栈和队列:链栈(即用链表实现栈)

 

#include <iostream>
using namespace std;
struct node
{
public:
    node *next;
    int data;
};
class Linkstack
{
public:
    Linkstack(){}
    ~Linkstack(){}
    int creatstack();       //创建一个空的链栈
    int push(int x);        //向栈内压入元素
    int pop();                  //将元素出栈
    int get_top();              //获得栈顶元素
    int empty();            //判空操作,如果为空,则返回1
private:
    node *p,*top;
};
int Linkstack::creatstack()
{
    top = new node;
    top=NULL;               //此时栈内元素为空
}
int Linkstack::push(int x)
{

    if(top==NULL)               //压入第一个元素时
    {
        p = new node;
        p->data = x;
        p->next = NULL;     //此时栈内只有一个元素,所以这个节点的后继指针指向空
        top = p;
    }
    else                                //当栈内存在元素时
    {
        p = new node;
        p->data = x;
        p->next = top;          //将结点的指针域指向top
        top = p;                    //然后将p的值赋给top
    }
    return top->data;           //此时返回的就是栈顶元素

}
int Linkstack::get_top()
{
    int x;
      x = top->data;
      return x;
}
int Linkstack::pop()
{
    int x;
    x = top->data;          //先暂存栈顶元素
    p = top->next;          //暂存栈顶元素的下一个元素的地址
    delete top;                 //将栈顶元素出栈,并清空top内存
    top = p;                    //此时栈内总元素个数-1,top指针向下移动一位
    return x;
}
int Linkstack::empty()
{
    if(top==NULL)
        return 1;
    else
        return 0;
}

int main()
{
    Linkstack l;
    l.creatstack();
    cout<<"判断链栈是否为空:"<<l.empty()<<endl;
    cout<<"入栈的元素为:"<<l.push(1)<<endl;
    cout<<"入栈的元素为:"<<l.push(2)<<endl;
    cout<<"入栈的元素为:"<<l.push(3)<<endl;
    cout<<"入栈的元素为:"<<l.push(4)<<endl;
    cout<<"栈顶元素为:"<<l.get_top()<<endl;
    cout<<"将栈顶元素出栈:"<<l.pop()<<endl;
    cout<<"出栈后栈顶元素为:"<<l.get_top()<<endl;
    return 0;
}

上一篇:基于链栈的进制转换算法


下一篇:栈的基本操作