当前位置 博文首页 > 王木木：数据结构 之 栈【图文详解】
栈是一种操作受限的线性表只允许从一端插入和删除数据。栈有两种存储方式，即线性存储和链接存储（链表）。栈的一个最重要的特征就是栈的插入和删除只能在栈顶进行，所以每次删除的元素都是最后进栈的元素，故栈也被称为后进先出（LIFO）表。每个栈都有一个栈顶指针，它初始值为-1，且总是指向最后一个入栈的元素，栈有两种处理方式，即进栈（push）和出栈（pop），因为在进栈只需要移动一个变量存储空间，所以它的时间复杂度为O(1)，但是对于出栈分两种情况，栈未满时，时间复杂度也为O(1)，但是当栈满时，需要重新分配内存，并移动栈内所有数据，所以此时的时间复杂度为O(n)。以下举例栈结构的两种实现方式，线性存储和链接存储。
1、线性存储
线性存储的方式和线性表基本一致，只不过多了后进先出的限制而已，它是静态分配的，即使用前，它的内存就已经以数组的形式分配好了，所以在初始化时，需要指明栈的节点最大个数。
#include "stdafx.h"
#include <iostream>
#include <new>
//定义
template<class T>
class LineStack
{
public :
LineStack(int MaxListSize=10); //构造函数
~LineStack() //析构函数
{
delete[] elements;
}
bool IsEmpty() const //判断是否为空
{
return top==-1;
}
bool IsFull() const //判断是否满
{
return top==MaxSize-1;
}
T pop(); //出栈
int push(const T& data); //进栈
T getPop(); //获取栈顶元素值
void clear(); //清空栈
void print() ;
private:
int top; //栈顶指针
int MaxSize; //数组最大长度
T *elements;//一维动态数组
};
//实现...
template<class T>
LineStack<T>::LineStack(int MaxListSize)
{
//基于公式的线性表的构造函数
MaxSize = MaxListSize;
elements = new T[MaxSize];
top = -1;
}
template<class T>
T LineStack<T>::pop()
{
if(IsEmpty())
{
return NULL;
}
return elements[top--];
}
template<class T>
int LineStack<T>::push(const T& data)
{
if(IsFull())
{
return -1;
}
else
{
elements[++top] = data;
}
return 0;
}
template<class T>
T LineStack<T>::getPop()
{
if(IsEmpty())
{
return NULL;
}
return elements[top];
}
template<class T>
void LineStack<T>::clear()
{
top = -1;
return true;
}
template<class T>
void LineStack<T>::print()
{
for(int i=0;i<=top;i++)
{
std:: cout<<elements[i]<<" ";
}
}
void LineStackSample()
{
int j;
int a = 10,b = 20,c = 30,d = 40;
LineStack<int> S(10);
std::cout<<"IsFull = "<<S.IsFull()<<std::endl;
std::cout<<"IsEmpty = "<<S.IsEmpty()<<std::endl;
S.push(a);
S.push(b);
S.push(c);
S.push(d);
j = S.pop();
std::cout<<j<<std::endl;
j = S.pop();
std::cout<<j<<std::endl;
j = S.pop();
std::cout<<j<<std::endl;
j = S.pop();
std::cout<<j<<std::endl;
return;
}
int main(int argc, _TCHAR* argv[])
{
LineStackSample();
//暂停操作
char str;
std::cin>>str;
//程序结束
return 0;
}
运行结果如下：
2、链接存储
实际上只要对单链表类做适当的修改，限制其插入、删除、修改和访问结点的行为，使其符合栈先进后出的规则即可，另外需要单独提供栈访问的接口函数，例如进栈、出栈、获取栈大小等，链表知识可以参考https://blog.csdn.net/Chiang2018/article/details/82730174。
// 栈动态.cpp : 定义控制台应用程序的入口点。
//
// 单链表.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
template <class T>
class Node
{
public:
T data;
Node(T& item);
Node<T>* next;
};
template<class T>
class LinkList
{
public:
LinkList();
~LinkList();
int getSize(void);
bool IsEmpty(void);
int gotoNext(void);
int getPostion(void);
int InsertNode(T& data);
int DeleteNode(void);
void getCurrNodeData(T& data);
void setCurrNodeData(T& data);
void clear();
void print();
private:
Node<T>* head;
Node<T>* currNode;
int size;
int position;
void freeNode(Node<T>* p);
};
/* 链表节点构造函数 */
template <class T>
Node<T>::Node(T& item)
{
data = item;
next = NULL;
}
/* 链表构造函数 */
template <class T>
LinkList<T>::LinkList()
{
head = NULL;
currNode = NULL;
size = 0;
position = -1;
}
/* 链表析构函数 */
template <class T>
LinkList<T>::~LinkList()
{
clear();
}
/* 获取链表长度 */
template <class T>
int LinkList<T>::getSize(void)
{
return size;
}
/* 判断链表是否为空 */
template <class T>
bool LinkList<T>::IsEmpty(void)
{
return size==0?true:false;
}
/* 移动到下个节点，返回下个节点的位置值 */
template <class T>
int LinkList<T>::gotoNext(void)
{
if(NULL == head)
{
return -1;
}
if(NULL == currNode)
{
return -1;
}
else
{
currNode = currNode->next;
position++
}
return position;
}
/* 获取当前节点的位置 */
template <class T>
int LinkList<T>::getPostion(void)
{
return position;
}
/* 在当前节点前插入新节点 */
template <class T>
int LinkList<T>::InsertNode(T& data)
{
Node<T>* p = new Node<T>(data);
if(0 == size)
{
head = p;
head->next = NULL;
currNode = p;
}
else
{
p->next = currNode->next;
currNode->next = p;
currNode = p;
}
size++;
position++;
return size;
}
/* 删除当前节点 */
template <class T>
int LinkList<T>::DeleteNode(void)
{
if(0 == size)
{
return -1;
}
Node<T>* p = head;
Node<T>* tmp;
for(int i = 0;i < size;i++)
{
if(NULL == p)
{
return -1;
}
if(p->next == currNode)
{
p->next = currNode->next;
break;
}
p = p->next;
}
tmp = currNode;
if(currNode == head)
{
head = currNode->next;
}
if(NULL == currNode->next)
{
position--;
currNode = p;
}
else
{
currNode = currNode->next;
}
freeNode(p);
size--;
if(0 == size)
{
position = -1;
}
return 0;
}
/* 释放指定节点的内存 */
template <class T>
void LinkList<T>::freeNode(Node<T>* p)
{
if(!p)
{
delete p;
}
return;
}
/* 获取当前节点的数据 */
template <class T>
void LinkList<T>::getCurrNodeData(T& data)
{
if(currNode)
{
data = currNode->data;
}
return ;
}
/* 修改当前节点的数据 */
template <class T>
void LinkList<T>::setCurrNodeData(T& data)
{
if(currNode)
{
currNode->data = data;
}
return ;
}
/* 清空链表 */
template <class T>
void LinkList<T>::clear()
{
if(0 == size)
{
return;
}
Node<T>* p = head;
Node<T>* tmp = head->next;
while(p)
{
freeNode(p);
p = tmp;
if(tmp)
{
tmp = tmp->next;
}
}
head = NULL;
currNode = NULL;
size = 0;
position = -1;
return;
}
template <class T>
void LinkList<T>::print()
{
if(0 == size)
{
return;
}
Node<T>* p = head;
Node<T>* tmp = head->next;
while(p)
{
std::cout<<p->data<<std::endl;
p = tmp;
if(tmp)
{
tmp = tmp->next;
}
}
return;
}
template <class T>
class LinkedStack
{
private:
LinkList<T>* link;
public:
LinkedStack();
void push(T& data);
T pop();
void ClearStack();
int getSize();
bool isEmpty();
};
template <class T>
LinkedStack<T>::LinkedStack()
{
link = new LinkList<T>;
}
template <class T>
bool LinkedStack<T>::isEmpty()
{
return link->IsEmpty();
}
template <class T>
int LinkedStack<T>::getSize()
{
return link->size;
}
template <class T>
void LinkedStack<T>::ClearStack()
{
link->clear();
}
template <class T>
void LinkedStack<T>::push(T& data)
{
link->InsertNode(data);
}
template <class T>
T LinkedStack<T>::pop()
{
T tmp;
if(isEmpty())
{
return NULL;
}
link->getCurrNodeData(tmp);
link->DeleteNode();
return tmp;
}
int main(int argc, _TCHAR* argv[])
{
int j = 0;
int a = 10,b=20,c=30,d=40,e=50;
LinkedStack<int> list;
list.push(a);
list.push(b);
list.push(c);
list.push(d);
list.push(e);
j = list.pop();
std::cout<<j<<std::endl;
j = list.pop();
std::cout<<j<<std::endl;
j = list.pop();
std::cout<<j<<std::endl;
j = list.pop();
std::cout<<j<<std::endl;
j = list.pop();
std::cout<<j<<std::endl;
std::cin.get();
return 0;
}
运行结果是：
