链栈基本操作

女爷i 2022-08-02 01:52 202阅读 0赞

**栈基本概念：**  
栈（stack）是限定在表尾进行插入和删除操作的线性表（或单链表）。  
//只能在一段进行插入和删除，因此不存在，在中间进行插入  
**栈顶（top）：允许插入和删除的一端。**而另一端称为栈底（bottom）  
空栈：不含任何数据元素的栈。  
**后进先出**

**两个基本操作：**  
栈的插入操作（**push**），叫做进栈，或压栈，或入栈  
删除操作（**pop**），叫做出栈，或弹栈  
**注意链栈next指针的指向，与队列不同：**  
如果插入一个元素，它的next指针是指向前一个已经在栈中的元素的  
而队列则是，插入一个元素，其next指针是往外指，指向空。  
链栈的next指针之所以这样，是方便删除操作，这一点可以在编程的过程中体会到。  
![这里写图片描述][20150705203302372]

**以下是代码：**

#include <iostream>
    
    using namespace std;
    
    typedef struct node{
        int data;
        struct node *next;
    }Node;
    
    typedef struct stack{
        Node *top;            /**书本写法是：加一个bottom，个人感觉没什么用，反而加一个count用于表示节点数会更好*/
        int count;
    }Link_Stack;
    
    /**创建一个空栈*/
    Link_Stack * Creat_stack()
    {
        Link_Stack *p;
        p = new Link_Stack;   /**这一步不要忘！需要给p创建空间*/
        p->count = 0;
        p->top = NULL;
    
        return p;
    }
    
    /**入栈操作：push*/
    Link_Stack * Push_stack(Link_Stack *p,int elem)
    {
        if(NULL == p)
            return NULL;
    
        Node *temp;
        temp = new Node;
        temp->data = elem;
    
        temp->next = p->top;   /**注意这里和队列的入队操作不同，next指向不同，为了方便出栈操作*/
        p->top = temp;
    
        p->count += 1;
    
        return p;
    }
    
    /**出栈操作：pop*/
    Link_Stack * Pop_stack(Link_Stack *p)
    {
        Node *temp;
        temp = p->top;
        if(NULL == p->top)
        {
            cout << "The stack is empty." << endl;
            return p;
        }
        else{
            p->top = p->top->next;    /** temp = temp->next;  千万不能这么写，看看下一步是什么？*/
            delete temp;
    
            p->count -= 1;
    
            return p;
        }
    }
    
    /**栈的遍历：输出栈*/
    int Show_stack(Link_Stack *p)
    {
        Node *temp;
        temp = p->top;
    
        if(NULL == p->top)
        {
            cout << "The stack is empty." << endl;
            return 0;
        }
        while(NULL != temp)
        {
            cout << temp->data << ' ';
            temp = temp->next;
        }
        cout << endl;
    
        return 0;
    }
    
    int main()
    {
        int i = 5;
        int elem;
        Link_Stack *p;
        p = Creat_stack();
        while(i--)
        {
            cin >> elem;
            Push_stack(p,elem);
        }
        cout << "空栈插入5个元素后:" << endl;
        Show_stack(p);
    
        cout << "删除3个元素后:" << endl;
        for(i = 3;i--;)
        {
            Pop_stack(p);
        }
        Show_stack(p);
        cout << "count:" << p->count << endl;
    
        cout << "删除2个元素后:" << endl;
        for(i = 2;i--;)
        {
            Pop_stack(p);
        }
        Show_stack(p);
        cout << "count:" << p->count << endl;
    
        Push_stack(p,6);
        cout << "插入元素6后:" << endl;
        Show_stack(p);
        cout << "count:" << p->count << endl;
    
        return 0;
    }

**结果如下：**  
![这里写图片描述][20150705203921131]

/*点滴积累，我的一小步O(∩\_∩)O~*/

[20150705203302372]: /images/20220731/cb65afb3d1dc42309c9674091abcb43f.png
[20150705203921131]: /images/20220731/b70cf8f5de7640ea989b00587e49bbcd.png