数据结构笔记——堆栈

1.特点：

先进后出只在一端(栈顶)进行插入删除操作

2.堆栈ADT

类型名：Stack；数据对象集：一个有0个或多个元素的有穷线性表；操作集： 1.Stack() :构造函数，生成空堆栈，最大程度maxSize； 2.IsFull():判空； 3.IsEmpty()：判满； 4.Push()：插入栈顶元素； 5.Pop()：删除并返回栈顶元素；

3.堆栈的顺序实现

//代码未测试 #include <iostream> #include <stdio.h> using namespace std； template <class T> class Stack{ public: Stack(int maxSize); ~Stack(); bool IsFull(); bool IsEmpty(); bool Pop(T &x); bool Push(T x); private: int top; //指向当前栈顶元素所在位置 T *s; int maxSize; }; template <class T> Stack ::Stack(int n){ maxSize = n; s = new T[maxSize]; top = -1; } template <class T> Stack ::~Stack(){ delete []s; s = NULL; } template <class T> bool IsFull(){ if(top == maxSize-1) return true; else return false; } template <class T> bool IsEmpty(){ if(top == -1) return true; else return false; } template <class T> bool Pop(T &x){ if(IsEmpty) return flase; else { x = s[top]; top--; return true; } } template <class T> bool Push(T x){ if(IsFull) return false; else{ s[++top] = x; return true; } }

4.题目：用一个数组实现两个堆栈，要求最大程度的利用数组空间，使数组只要有空间入栈操作就可以成功。

分析：

可以使两个栈分别从数组的两头开始向中间增长；当两个堆栈指针相遇时就表示两个栈都满了；在执行push、pop操作时增添一个tag变量用于区分是对第一个堆栈操作还是对第二个堆栈操作； //代码未测试 #include <iostream> #include <stdio.h> using namespace std; template <class T> class dStack(){ public: dStack(int n); ~dStack(); bool IsFull(); bool IsEmpty(); //判别整个堆栈空不空 bool Pop(T &x,int tag); bool Push(T x,int tag); private: int top1,top2; //分别指向两个堆栈当前栈顶元素所在位置 T *s; int maxSize; }; template <class T> dStack ::dStack(int n){ maxSize = n; s = new T[maxSize]; top1 = -1; top2 = maxSize; } template <class T> dStack ::~dSTack(){ delete []s; s = NULL; } template <class T> bool dSTack ::IsFull(){ if(top2-top1==1) return true; else return false; } template <class T> bool dSTack ::IsEmpty(){ if(top1==-1 &&top2==maxSize) return true; else return false; } template <class T> bool dSTack ::Push(T x,int tag){ if(IsFull) return false; else { if(tag==1) { s[++top1] = x; return true; } else { s[--top2] = x; return true; } } } template <class T> bool dSTack ::Pop(T &x,int tag){ if(tag == 1){ if(top1==-1) return false; x = s[top1--]; return true; } if(top2==maxSize) return false; x = s[top2++]; return true; }

5.堆栈的链式存储

栈的链式存储实际上是一个单链表，叫做链栈；由于插入和删除只能在链栈的栈顶进行，所以栈顶应当取链表的头部，方便插入删除的进行。（尾部不方便删除元素） //代码未测试 #include <iostream> #include <stdio.h> using namespace std; //用带头节点的链表实现堆栈 template <class T> class TNode{ private: T data; TNode *next; }; template <class T> class lineStack{ public: lineStack(); //构造一个堆栈的头节点 ~lineStack(); bool IsFull(); bool Pop(T &x); //弹出栈顶元素并将元素值赋给x bool Push(T x); private: TNode *head; int maxSize; int n; }; template <class T> lineStack ::lineStack(){ head = new TNode; head->next = NULL; } template <class T> lineStack ::~lineStack(){ TNode *q; while(head) { q = head; head = head->next; delete head; } } bool lineStack ::IsFull(){ TNode *p = head; int count = 1; while(p){ p = p->next; count++; } if(count<maxSize) return false; else return true; } bool lineStack ::Pop(T &x){//弹出栈顶元素并将元素值赋给 x TNode *p = NULL; if(head->next) { //如果栈非空 p = head->next; x = p->data; head->next = p->next; delete p; return true; } return false; } bool lineStack ::Push(T x){ if(IsFull()) return false; //若不限制链表的最大长度就不用判满了 else { TNode *q = new TNode; q->data = x; q->next = head->next; head->next = q; return true; } }