【数据结构】链表栈

目录：

• 链表栈
  • 1. 链式栈的实现
  • 2. 链表栈的创建
  • 3. 压栈
  • 4. 弹栈

链表栈

栈的主要表示方式有两种，一种是顺序表示，另一种是链式表示。本文主要介绍链式表示的栈。
链栈实际上和单链表差别不大，唯一区别就在于只需要对链表限定从头部进行删除元素和增加元素就可以了。

1. 链式栈的实现

链式栈的实现，是通过先定义一个结构体节点，然后定义一个指向该结构体的指针，通过该指针来操作栈。
示例代码如下：

typedef struct node {
    struct node* next;  /* 指向下一个节点的指针 */
    int data;           /* 数据域 */
} Node;
typedef Node *Stack;
1
2
3
4
5

其中Stack是一个指向Node的指针，通过该指针可以访问链式栈的栈顶元素。

2. 链表栈的创建

类似于链表的创建，链表栈也分头结点和不带头结点两种。这里为了方便起见，我们决定使用带头结点的版本。
示例代码如下：

void InitStack(Stack *S)
{
    *S=(Stcak)malloc(sizeof(Node));
    if(S==NULL)
    {
        return;
    }
    (*S)->next=NULL;
}
1
2
3
4
5
6
7
8
9

3. 压栈

在进行压栈操作时，我们规定只在链表的头部进行插入，即在头结点之后插入一个元素，使得这个元素的指针指向头结点的下一个元素，然后让头结点的指针指向这个元素。
示例代码如下：

bool Push(Stack *S,int x)
{
    Node *p=(Stack)malloc(sizeof(Node));
    p->next=(*S)->next;
    p->data=x;
    (*S)->next=p;
    return true;
}
1
2
3
4
5
6
7
8

4. 弹栈

同样的，我们也只需要在头部进行删除元素即可
示例代码如下：

int Pop(Stack *S,int *x)
{
    Node *p=S;
    p=S->next;
    Node *q=p->next;
    S->next=q;
    (*x)=p->data;
    free(p);
}
1
2
3
4
5
6
7
8
9