初学数据结构栈和队列都是必修的,下面我们来浅谈一下栈
【1】什么是栈?
栈是一种可以实现先进后出的存储结构,也可以说栈是一种特殊容器
FILO = first in last out;先进后出和后进先出是栈的主要特征
类似于 车子开进死胡同(借用大佬的)image.png
【2】分类
(1)静态栈(顺序存储结构)
- 个人理解 静态栈是对数组进行操作
(2)动态栈(链式存储结构)- 个人理解是针对链表进行处理
【3】算法
(1)出栈
(2)压栈
栈的本质是线性表,可以说他是一种特殊的线性表,因为只能在线性表的一端进行操作(栈顶),不能操作的那一端交栈底。
栈的性质:后进先出(LIFO)
栈可以分为两种:静态栈和动态栈
两种栈的实现都可以复用单链表的代码,其中静态栈可以复用顺序表的代码;动态栈可以复用单链表的代码。其实可以从头到尾实现一个栈数据结构,但是那样做是没有意义的。代码复用的思想是工程中常见的,而且基于已经测试过的代码就减少了中间会遇到的其它问题。
而且由于栈的操作仅仅能在线性表的一端进行,所以无论是入栈还是出栈的操作,时间复杂度都是O(1)
首先是静态栈的实现,项目中需要添加之前实现的顺序表代码。需要注意的是栈顶的选择可以有两种方式,在顺序表的头部或者尾部,这里选择线性表的尾部作为栈顶,也就是说只能允许在这一端进行操作;相应的在进行出栈操作时也是从线性表的尾部开始。
SeqStack* SeqStack_Greate(int capacity) { return SeqList_Create(capacity); } void SeqStack_Destroy(SeqStack* stack) { SeqList_Destroy(stack); } void SeqStack_Clear(SeqStack* stack) { SeqList_Clear(stack); } int SeqStack_Push(SeqStack* stack, void* item) { return SeqList_Insert(stack, item, SeqList_Length(stack)); // 选择线性表的尾部作为栈顶,在这一端操作栈 } void* SeqStack_Pop(SeqStack* stack) { return SeqList_Delete(stack, SeqList_Length(stack) - 1); } // 返回栈顶元素 void* SeqStack_Top(SeqStack* stack) { return SeqList_Get(stack, SeqList_Length(stack) - 1); } int SeqStack_Size(SeqStack* stack) { return SeqList_Length(stack); } int SeqStack_Capacity(SeqStack* stack) { return SeqList_Capacity(stack); }
动态栈的实现比顺序栈要复杂,首先需要定义结点的结构体,用来表示每次进栈或者出栈的元素,然后进栈和出栈的操作也要malloc和free相应的内存空间。
// 定义栈的每一个结构体组成 typedef struct _tag_LinkStackNode { LinkListNode header; void* item; // 保存地址 } TLinkStackNode; // 创建一个只含头结点的栈 LinkStack* LinkStack_Create() { return LinkList_Create(); } void LinkStack_Destroy(LinkStack* stack) { LinkStack_Clear(stack); LinkList_Destroy(stack); } // 链表中的每一个元素都是malloc出来的,单纯clear会产生内存泄漏 void LinkStack_Clear(LinkStack* stack) { while( LinkStack_Size(stack) > 0 ) { LinkStack_Pop(stack); } } int LinkStack_Push(LinkStack* stack, void* item) { TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode)); int ret = (node != NULL) && (item != NULL); if( ret ) { node->item = item; // 保存传进来的参数地址 ret = LinkList_Insert(stack, (LinkListNode*)node, 0); // 使用队头作为栈顶 } if(!ret) { free(node); } return ret; } void* LinkStack_Pop(LinkStack* stack) { TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0); // 首元素为栈顶 void* ret = NULL; if( node != NULL ) { ret = node->item; // 返回删除的元素 free(node); // 释放掉结点空间 } return ret; } void* LinkStack_Top(LinkStack* stack) { TLinkStackNode* node = (TLinkStackNode*)LinkList_Get(stack, 0); void* ret = NULL; if( node != NULL ) { ret = node->item; // 返回栈顶元素结点 } return ret; } int LinkStack_Size(LinkStack* stack) { return LinkList_Length(stack); }
初学数据结构栈和队列都是必修的,下面我们来浅谈一下栈
【1】什么是栈?
栈是一种可以实现先进后出的存储结构,也可以说栈是一种特殊容器
FILO = first in last out;先进后出和后进先出是栈的主要特征
类似于 车子开进死胡同(借用大佬的)image.png【2】分类
(1)静态栈(顺序存储结构)
- 个人理解 静态栈是对数组进行操作
(2)动态栈(链式存储结构)- 个人理解是针对链表进行处理
【3】算法
(1)出栈
(2)压栈
一.简介
在哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-b站搜索:av6159200(P33),通过学习,能独立把赫斌老师教的敲出来,由于动态栈(链表阉割版)的功能很少,我并没有增加什么其它功能,但是我自己实现了静态栈(数组阉割版),还有就是分享一些我对动态栈,以及静态栈的理解.
二.什么是栈
简介已经说了,栈可以分为静态栈和动态栈.
静态栈是用数组来实现而动态栈是用链表来实现.
栈实现的功能就是:先进后出.
打个比喻就是把一块一块的方块放进一个箱子里,等到你不想放,想要从箱子取出来的时候,第一个出来的,就是你最后一次放的,而最后一个出来的,只能是最后一个出来,这就是所谓的先进后出.
具体图解
栈的实现需要确定顶部与底部.
静态栈与动态栈的区别:
静态栈必须提前确定栈的大小(有限的),并且都是连续的. 动态栈可以无限大小(内存够的情况下),并且是不连续的.
三.动态栈的图解
由于图片较多…具体可以链接下载详看:百度网盘四.函数功能实现的源码
理解不了可以看第三部分的图解
void init(PSTACK); //初始化
void push_stack(PSTACK , int); //入栈(压栈)
void traversal_output(PSTACK ); //遍历输出
int air(PSTACK ); //判断是否为空
int pop(PSTACK , int*); //出栈
void empty(PSTACK ); //清空栈
五.源码分享(可复现)
动态栈链接:百度网盘
静态栈链接:百度网盘
六.栈可以应用在那些方面
1.函数调用
2.中断
3.表达式求值(计算器)
4.内存分配
5.缓冲处理
6.迷宫
静态栈:
#include<iostream> #include<assert.h> using namespace std; template <class T,size_t N=100> class Stack//栈顶插入,删除 因此适合用顺序表 //静态 { public: void Push(const T&x) { if (_size == N) { throw out_of_range("out of range");//如果空间不够,抛异常 } _a[size++] = x; } void Pop() { assert(_size > 0); --_size; } T& Top() { assert(_size > 0); return _a[_size - 1]; } private: T _a[N]; size_t _size; };
动态栈:template<class T> class Stack { public: Stack() :_a(NULL) , _size(0) , _capacity(0) {}; void Push(const T& x) { CheckCapacity(); _a[_size] = x; _size++; } void Pop() { if (_size <= 0) return; --_size; } T Top() { assert(_size > 0); return _a[_size-1]; } void CheckCapacity() { if (_size >= _capacity) { size_t capacity = _capacity * 2 + 3; T* tmp = new T[capacity];//开空间 注意此处T类型不确定,可能为自定义类型 因此不能用realloc开空间 for (size_t i = 0; i < _size; i++) { tmp[i] = _a[i]; } delete[] _a; _a = tmp; _capacity = capacity; } } size_t Size() { return _size; } bool Empty() { return (_size == 0); } private: T* _a; size_t _size; size_t _capacity; }; void TestStack() { Stack<int> s1; s1.Push(1); s1.Push(2); s1.Push(3); s1.Push(4); int size = s1.Size(); for (size_t i = 0; i <size; i++) { cout << s1.Top() <<" "; s1.Pop(); } cout << endl; /*s1.Pop(); s1.Pop(); for (size_t i = 0; i < s1.Size(); i++) { cout << s1.Top() << " "; s1.Pop(); }*/ cout << endl; } int main() { TestStack(); system("pause"); return 0; }
队列:
#include<iostream> using namespace std; template<class T> struct QueueNode { T _data; QueueNode<T>* _next; QueueNode(const T& x) :_data(x) ,_next(NULL) {} }; template <class T> class Queue { public: Queue() :_head(NULL) , _tail(NULL) {} typedef QueueNode<T> Node; void Push(const T& x) { Node* tmp = new Node(x); if (_head == NULL) { _tail= _head = tmp; } else { _tail->_next = tmp; _tail = tmp; } } void Pop() { //三种情况 if (_head == NULL) { return; } else if (_head == _tail) { _head = _tail = NULL; } else { Node* next = _head->_next; delete _head; _head = next; } } T& Front() { if (_head != NULL) { return _head->_data; } } bool Empty() { return _head == NULL; } size_t Size() { size_t count = 0; Node *tmp = _head; while (tmp) { count++; tmp = tmp->_next; } return count; } private: Node* _tail; Node* _head; }; void TestQueue() { Queue<int> q1; q1.Push(1); q1.Push(2); q1.Push(4); q1.Push(5); /*while (!q1.Empty())//方法二 时间复杂度为O(N^2) { cout << q1.Front() << " "; q1.Pop(); } cout << endl;*/ while ( !q1.Empty())//方法一 时间复杂度为O(N) 因此在链表中,应该少用Size().因为它把链表遍历了一遍时间复杂度为0(N) { cout << q1.Front() << " "; q1.Pop(); } cout << endl; } int main() { TestQueue(); system("pause"); return 0; }