赞
踩
栈是限定在表尾进行插入和删除的线性表。栈又称为后进先出的线性表,简称LIFO结构。
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数元素的栈称为空栈。
栈的插入操作,也叫做进栈,也称为压栈、入栈。栈的删除操作,叫做出栈,也称作弹栈。
栈有两种实现方式,一种是由数组实现的栈称为顺序栈,另一种是由链表实现的栈,称为链栈。
最先进栈的元素不一定最后出栈。
如:1、2、3一次进栈,会有哪些出栈顺序?
1、2、3依次进,3、2、1依次出
1进,1出,2进,2出,3进,3出
1、2依次进,2、1依次出,3进,3出
1、2依次进,2出,3进,3出,1出
1进,1出,2、3依次进,3、2依次出
由这个例子可以看出,栈是很灵活的。
栈的常用操作如下:
顺序栈是用数组来实现的,由于如果在数组第一个元素进行插入删除元素的时间复杂度为O(n),而在数组最后一个元素位置进行插入删除的时间复杂度只有O(1),因此,采用下标为0的一端作为栈底。我们定义一个top变量来指示栈顶元素在数组中的位置,top的值小于栈存储长度。
顺序栈的进栈、出栈操作的时间复杂度都是O(1).
顺序栈的C++实现如下:
#define SIZE 100 //创建栈默认的大小 class ArrayStack{ public: ArrayStack(); //构造函数 ArrayStack(int val); //有参构造 ~ArrayStack(); //析构函数 void push(int elem); //压栈 void pop(); //出栈 int top(); //返回栈顶元素 bool empty(); //判断栈是否为空 int size(); //返回栈的大小 private: int *_arr; //数组地址,即栈底 int _size; //栈的长度,_size-1为栈顶指针 }; ArrayStack::ArrayStack(){ _arr=new int[SIZE]; _size=0; } ArrayStack::ArrayStack(int val):_arr(nullptr),_size(val){} ~ArrayStack::ArrayStack(){ if(_arr){ delete[]_arr; _arr=nullptr; } } void ArrayStack::push(int elem){ arr[_size++]=elem; } void ArrayStack::pop(){ arr[--_size]=0; } int ArrayStack::top(){ return _arr[_size]; } bool ArrayStack::empty(){ return (_size>0)?true:false; } int ArrayStack::size(){ return _size; }
链栈的头指针就是栈顶指针,栈顶放在单链表的头部,链栈没有虚拟头结点。并且对于链栈来说,不存在栈满的情况。
**进栈操作是在创建一个新的结点,将栈顶指针赋值给新的结点的后继,然后将新的结点的地址赋值给栈顶指针。**假设新创建的结点为s,值为elem,链栈对象为this,则操作如下:
ListNode *s=new ListNode(elem);
s->next=this->top;
this->top=s;
**出栈操作是先设置一个变量p存放栈顶元素,然后将top指针指向栈顶元素的下一个元素,释放掉p。**操作如下:
ListNode *p=this->top;
this->top=p->next;
delete p;
与顺序栈一样,链栈进栈出栈的时间复杂度都是O(1).
C++的链栈实现如下:
class ListStack { public: struct ListNode { ListNode(int val) :val(val), next(nullptr) {} int val; ListNode* next; }; ListStack(); //链栈的默认构造函数 ~ListStack(); //析构函数 void push(int elem); //压栈 void pop(); //出栈 int top(); //返回栈顶元素 bool empty(); //判断栈是否为空 int size(); //返回栈的大小 private: ListNode* _top; //栈顶指针 int _size; //链栈的大小 }; ListStack::ListStack() { _top = nullptr; int _size = 0; } ListStack::~ListStack() { ListNode* p = nullptr; while (!this->_top) { p = this->_top; this->_top = p; delete p; p = nullptr; } } void ListStack::push(int elem) { ListNode* newNode = new ListNode(elem); newNode->next = this->_top; this->_top = newNode; ++_size; } void ListStack::pop() { ListNode* p = this->_top; this->_top = p->next; delete p; --_size; } int ListStack::top() { if (!this->_top) { return -1; } return this->_top->val; } bool ListStack::empty() { return (this->_top) ? true : false; } int ListStack::size() { return this->_size; }
链栈和顺序栈的异同:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。