栈和队列的链式存储结构
标签: 数据结构
学习人数: 15.8k


高清播放
赞赏支持

栈的链式存储结构,简称为链栈

通常我们使用栈的顺序存储结构来存储,栈的链式存储我们了解思想即可,进行扩展。
栈因为只是栈顶来做插入和删除操作,所以比较好的方法就是将栈顶放在单链表的头部,栈顶指针和单链表的头指针合二为一。

栈的链式存储结构实现

参考代码(使用链表实现)

#include <stdio.h>  
#include <stdlib.h>  
  
#define OK 1  
#define ERROR 0  
#define TRUE 1  
#define FALSE 0  
  
#define STACK_INIT_SIZE 100    //定义栈的初始大小  
#define STACK_INCR_SIZE 10    //定义栈的增长大小  
  
typedef int ElemType;  
typedef int Status;  
  
//设置链栈的结点  
typedef struct StackNode  
{  
    ElemType data;    //存放栈中的数据  
    struct StackNode* next;    //单链表的指针域  
}StackNode,*LinkStackPtr;  
  
//设置栈的结构体  
typedef struct  
{  
    LinkStackPtr top;    //top指针,始终与头指针保持一致  
    int count;    //栈元素计数器  
}LinkStack;  
  
//四个基础操作  
Status InitStack(LinkStack *s);    //初始化操作,建立一个空栈  
Status ClearStack(LinkStack *s);    //将栈清空  
Status StackEmpty(LinkStack s);    //若栈存在,返回true,否则返回false  
int StackLength(LinkStack s);        //返回栈S的元素个数  
  
Status GetTop(LinkStack s, ElemType *e);    //若是栈存在且非空,用e返回S的栈顶元素  
Status Push(LinkStack *s, ElemType e);    // 若是栈存在,则插入新的元素e到栈S中并成为栈顶元素  
Status Pop(LinkStack *s, ElemType *e);    //若是栈存在且非空,删除栈顶元素,并用e返回其值  
Status DestroyStack(LinkStack *s);        //若是栈存在,则销毁他  
  
int main()  
{  
    LinkStack sk;  
    ElemType e;  
    int i;  
    //初始化空栈,用于存放()[]{}''""这几个数据,的左半边进行匹配  
    InitStack(&sk);  
  
    printf("2.Push 1-5\n");  
    for (i = 1; i <= 5; i++)  
        Push(&sk, i);  
    printf("3.Pop numb...
登录查看完整内容


课后作业

掌握栈和队列的链式存储结构


登录后开始许愿

暂无评论,来抢沙发