数据结构与算法之美 | 一文掌握栈Stack-阿里云开发者社区

0. 数据结构图文解析系列

数据结构图文解析之：树的简介及二叉排序树C++模板实现.

数据结构图文解析之：AVL树详解及C++模板实现

数据结构图文解析之：二叉堆详解及C++模板实现

数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现

1. 栈的基本概念

1.1 栈的特点

栈(Stack)是一种线性存储结构，它具有如下特点：

（1）栈中的数据元素遵守”先进后出"(First In Last Out)的原则，简称FILO结构。

（2）限定只能在栈顶进行插入和删除操作。

1.2 栈的相关概念

栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
压栈：栈的插入操作，叫做进栈，也称压栈、入栈。
弹栈：栈的删除操作，也叫做出栈。

例如我们有一个存储整型元素的栈，我们依次压栈：{1,2,3}

在压栈的过程中，栈顶的位置一直在”向上“移动，而栈底是固定不变的。

如果我们要把栈中的元素弹出来：

出栈的顺序为3、2、1 ，顺序与入栈时相反，这就是所谓的”先入后出“。

在弹栈的过程中，栈顶位置一直在”向下“移动，而栈底一直保持不变。

如果你玩过一种称为汉诺塔的益智玩具，你就会知道游戏中小圆盘的存取就是一种先进后出的顺序，一个圆柱就是一个栈：

1.3 栈的操作

栈的常用操作为：

弹栈，通常命名为pop
压栈，通常命名为push
求栈的大小
判断栈是否为空
获取栈顶元素的值

2. 栈的实现

2.1 栈的抽象数据类型

栈提供了如上所述操作的相应接口。

template<typename T>
class ArrayStack
{
public:
    ArrayStack(int s = 10);    //默认的栈容量为10
    ~ArrayStack();
public:
    T top();            //获取栈顶元素
    void push(T t);        //压栈操作
    T pop();            //弹栈操作
    bool isEmpty();        //判空操作
    int size();            //求栈的大小
private:
    int count;            //栈的元素数量
    int capacity;        //栈的容量
    T * array;            //底层为数组
};

说明：

count 为栈的元素数量，capacity为栈的容量，count<=capacity，当栈满的时候，count = capacity。
本实现中不支持栈的动态扩容，栈满的时候无法再插入元素。栈的容量在定义栈的时候就需要指定，默认的栈容量为10。

2.2 栈的常见分类

（1）基于数组的栈实现——以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向

（2）基于单链表的栈实现——以链表为底层的数据结构时，以链表头为栈顶，便于节点的插入与删除，压栈产生的新节点将一直出现在链表的头部。

2.3 实例分析

使用标准库的栈时, 应包含相关头文件，在栈中应包含头文件： #include< stack > 。定义：stack< int > s;

s.empty();         //如果栈为空则返回true, 否则返回false;
s.size();          //返回栈中元素的个数
s.top();           //返回栈顶元素, 但不删除该元素
s.pop();           //弹出栈顶元素, 但不返回其值
s.push();          //将元素压入栈顶

（1）基于数组的栈

#include <stack>
#include <iostream>
using namespace std;
int main()
{
  stack<int> mystack;
  int sum = 0;
  for (int i = 0; i <= 10; i++){
    mystack.push(i);
  }
  cout << "size is " << mystack.size() << endl;
  while (!mystack.empty()){
    cout << " " << mystack.top();
    mystack.pop();
  }
  cout << endl;
  system("pause");
  return 0;
}
//size is 11
// 10 9 8 7 6 5 4 3 2 1 0

（2）基于单链表的栈

#include <iostream>
using namespace std;
template<class T>class Stack
{
private:
  struct Node
  {
    T data;
    Node *next;
  };
  Node *head;
  Node *p;
  int length;
public:
  Stack()
  {
    head = NULL;
    length = 0;
  }
  void push(T n)//入栈
  {
    Node *q = new Node;
    q->data = n;
    if (head == NULL)
    {
      q->next = head;
      head = q;
      p = q;
    }
    else
    {
      q->next = p;
      p = q;
    }
    length++;
  }
  T pop()//出栈并且将出栈的元素返回
  {
    if (length <= 0)
    {
      abort();
    }
    Node *q;
    int data;
    q = p;
    data = p->data;
    p = p->next;
    delete(q);
    length--;
    return data;
  }
  int size()//返回元素个数
  {
    return length;
  }
  T top()//返回栈顶元素
  {
    return p->data;
  }
  bool isEmpty()//判断栈是不是空的
  {
    if (length == 0)
    {
      return true;
    }
    else
    {
      return false;
    }
  }
  void clear()//清空栈中的所有元素
  {
    while (length > 0)
    {
      pop();
    }
  }
};
int main()
{
  Stack<char> s;
  s.push('a');
  s.push('b');
  s.push('c');
  while (!s.isEmpty())
  {
    cout << s.pop() << endl;
  }
  system("pause");
  return 0;
}

3. 真题练习

练习1 返回栈中最小元素

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

解法参考博客：设计一个有getMin功能的栈（C++版），具体过程如下：

（1）使用两个栈，一个栈用来保存当前的元素，记做：stackData，一个栈用来保存压入操作每一步的最小元素，记做：stackMin。

（2）入栈：当stackData栈中压入一个数据时，判断satckMin中是否为空。若为空，将该元素压入stackMin栈中。若不空，判断两者之间的大小，当前者小于或等于后者时，将前者中的数据压入后者中；当前者大于后者时，不进行任何操作。

（3）出栈：保证stackMin中栈顶的元素是stackData中最小的。

#include<iostream>  
#include <stack>  
#include <cassert>  
using  namespace std;
//方法一：  一个辅助栈，如果这个栈为空，直接将元素入这个栈，如果辅助栈中有元素，将压入的元素和辅助栈顶元素比较，  
//压入两者中较小的那个元素使得辅助栈总是维持栈顶元素为最小值。  
//class Stack  
//{  
//public:  
//  void Push(int data)  
//  {  
//      stackData.push(data);  
//      if (stackMin.empty())  
//      {  
//          stackMin.push(data);  
//      }  
//      else  
//      {  
//          int tmp = stackMin.top();  
//          int min = data > tmp ? tmp : data;  
//          stackMin.push(min);  
//      }  
//  }  
//  
//  void Pop()  
//  {  
//      assert(!stackData.empty() && !stackMin.empty());  
//      stackData.pop();  
//      stackMin.pop();  
//  }  
//  
//  int GetMin()  
//  {  
//      assert(!stackMin.empty());  
//      return stackMin.top();  
//  }  
//  
//private:  
//  stack<int> stackData;  
//  stack<int> stackMin;  
//};  
//方法二： 一个辅助栈，如果这个栈为空，直接将元素入这个栈，如果辅助栈中有元素，将压入的元素和辅助栈顶元素比较，  
//如果压入的元素小于等于辅助栈顶元素，者将这个元素入辅助栈，否则无操作，出栈的时候判断要出栈的元素是否等于辅助  
//栈顶元素，如果是，也将辅助栈顶元素出栈。否则无操作。  
class Stack
{
public:
  void Push(int data)
  {
    stackData.push(data);
    if (stackMin.empty())
    {
      stackMin.push(data);
    }
    else
    {
      if (data <= stackMin.top())
      {
        stackMin.push(data);
      }
    }
  }
  void Pop()
  {
    assert(!stackData.empty() && !stackMin.empty());
    if (stackData.top() == stackMin.top())
    {
      stackMin.pop();
    }
    stackData.pop();
  }
  int GetMin()
  {
    assert(!stackMin.empty());
    return stackMin.top();
  }
private:
  stack<int> stackData;
  stack<int> stackMin;
};
int main()
{
  Stack s;
  //s.Push(5);  
  s.Push(36);
  s.Push(15);
  s.Push(95);
  s.Push(50);
  s.Push(53);
  cout << s.GetMin() << endl;
  system("pause");
  return 0;
}//15

（3）栈的应用举例

1）进制转换

2）括号匹配的检验

3）行编辑程序

4）迷宫求解、汉诺塔等经典问题

5）表达式求值

6）栈与递归的实现

练习2 剑指offer面试题30——包含min函数的栈

参考链接：包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

class Solution {
public:
    stack<int> stackData;//保存数据用的栈stackData
    stack<int> stackMin;//保存最小的数的栈stackMin，其中它的栈顶始终为最小的数
    void push(int value) {
        stackData.push(value);
        if(stackMin.empty()) 
            stackMin.push(value);//如果stackMin为空，则value是最小的值，入栈
        else{
            if(stackMin.top()>=value) 
                stackMin.push(value);//否则当value小于等于stackMin的栈顶元素时，入栈（等于的时候也入栈是因为我考虑有相同的数）
        }
  }
  void pop() {
      if(stackData.top()==stackMin.top())//如果出栈的数刚好是最小的数，那么stackMin也应该出栈
        stackMin.pop();
      stackData.pop();
  }
  int top() {
    return stackData.top();//栈顶元素应返回stackData的栈顶元素
  }
  int min() {
    return stackMin.top();//stackMin的栈顶元素即是最小的数
  }
};

运行结果：

练习3 剑指offer面试题31——栈的压入、弹出序列

参考博客：剑指offer题解C++【21】栈的压入、弹出序列，解题思路为：创建一个栈进行压入、弹出操作。具体操作如下：

（1）当栈为空或者栈顶元素和popV当前元素不相等时，将pushV当前元素压入；

（2）当栈顶元素与popV当前元素相等时，将栈顶元素弹出，并移至popV下一个元素；

（3）如果需要压入的元素个数大于pushV的元素个数，说明popV不可能是pushV的弹出序列。

代码为：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        //特殊输入测试
        if(pushV.empty() || popV.empty() || pushV.size()!=popV.size())
            return false;
        stack<int> mystack;//定义一个辅助栈
        int index=0;
        for(int i=0;i<popV.size();i++){
            //当辅助栈为空或者栈顶元素和popV当前元素不相等时，将pushV当前元素压入
            while(mystack.empty()||mystack.top()!=popV[i]){
                if(index>=pushV.size())
                    //如果需要压入的元素个数大于pushV的元素个数，说明popV不可能是pushV的弹出序列
                    return false;
                mystack.push(pushV[index++]);
            }
            //当栈顶元素与popV当前元素相等时，将栈顶元素弹出，并移至popV下一个元素
            if(mystack.top()==popV[i])
                mystack.pop();
        }
        return true;
    }
};

运行结果：

当然可以利用其他思想解决，如引入哈希或直接利用向量的方式求解。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.empty() && popV.empty() && pushV.size() != popV.size()){
            return false;
        }
        map<int,int> Hash; //用map做一个映射，入栈顺序的值不一定是递增  
        for(int i=0;i<pushV.size();i++){
            Hash[pushV[i]]=i+1;
        }
        int now=Hash[popV[0]]; //当前最靠后入栈的键值，例如题目给的4 3 5 1 2，now先等于4，再等于5
        for(int i=0;i<popV.size();i++){
        //如果入栈序列中没有这个值
            if(Hash[popV[i]]==0){
                return false;
            }
            if(Hash[popV[i]]>=now){
            now=Hash[popV[i]];
            }
            else if(Hash[popV[i]]<=Hash[popV[i-1]]){
                continue ;
            }
            else{
                return false;
            }
        }
        return true;
    }
};

练习4 简单的括号匹配判断

例如，爱奇艺的一道实习在线编程题：当输入为（）（（））（），返回true；当输入为）（）（）（）（）），返回false，时间15min。（不能使用栈）

1、假设可以使用栈（15min可以完成）

C++代码：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
bool isRight(vector<char> &vec){
  stack<char> stack1;
  bool index = false;
  if (vec.size() <= 1 || vec[0]!='(' || vec.size()%2!=0){
    return index;
  }
  for (int i = 0; i < vec.size(); i++){
    if (vec[i] == '(')
      stack1.push(vec[i]);
    else if (vec[i] == ')')
      stack1.pop();
  }
  if (stack1.empty())
    index = true;
  return index;
}
int main(){
  //输入不定长的括号
  vector<char> vec;
  char tmpCh;
  char t;
  cout << "输入一串括号为：";
  do{
    cin >> tmpCh;
    vec.push_back(tmpCh);
  } while ((t = cin.get()) != '\n');
  //调用isRight函数
  bool myRes = isRight(vec);
  cout << myRes << endl;
  system("pause");
  return 0;
}

运行结果：

python代码：

def isRight(str1):
    index = False
    tmp = []
    if(len(str1)>=2 and len(str1)%2==0 and str1[0]=='('):
        for id in range(len(str1)):
            if str1[id] == '(':
                tmp.append(str1[id])
            else:
                tmp.pop()
        if len(tmp)==0:
            index = True
    return index
if __name__ == "__main__":
    try:
        while True:
            str1 = [i for i in input().split()]
            print(isRight(str1))  # 返回判断结果
    except:
        pass

运行结果：

2、不能使用栈（15min，不太好想，笔试那会儿就没想到！）

以下是具体的过程如下：（1）由于不能使用栈，将左括号定义为数值1，右括号定义为数值-1，存放到向量id（C++）或列表tmp （Python）中；（2）初始化变量sum，用于判断总的求和结果是否等于0，若不等于0，则肯定不正确，若等于0，不一定正确；（3）循环遍历输入的括号向量vec，判断当前括号属性的同时，进行累加求和，如果求和值小于等于-1，break（跳出循环）；（4）最后再检查sum是否等于0，此时若等于0，则为正确。

C++代码：

#include <iostream>
#include <vector>
using namespace std;
bool isRight(vector<char> &vec){
  vector<int> id(vec.size()); //用于存放左右括号的属性：左括号用1表示，右括号用-1表示
  int sum = 0;
  bool index = false;
  if (vec.size() <= 1 || vec[0]!='(' || vec.size()%2!=0){
    return index;
  }
  for (int i = 0; i < vec.size(); i++){
    if (vec[i] == '('){
      id.push_back(1);
      sum = id[i] + sum;
    }
    else if (vec[i] == ')'){
      id.push_back(-1);
      sum = id[i] + sum;
      if (sum <= -1)
        break;
    }
  }
  if (sum == 0)
    index = true;
  return index;
}
int main(){
  //输入不定长的括号
  vector<char> vec;
  char tmpCh;
  char t;
  cout << "输入一串括号为：";
  do{
    cin >> tmpCh;
    vec.push_back(tmpCh);
  } while ((t = cin.get()) != '\n');
  //调用isRight函数
  bool myRes = isRight(vec);
  cout << myRes << endl;
  system("pause");
  return 0;
}

运行结果同上

python代码：

def isRight(str1):
    index = False
    sum = 0
    tmp = []
    if(len(str1)>=2 and len(str1)%2==0 and str1[0]=='('):
        for id in range(len(str1)):
            if str1[id] == '(':
                tmp.append(1)
                sum += tmp[id]
            else:
                tmp.append(-1)
                sum += tmp[id]
                if sum<=-1:
                    break
        if sum == 0:
            index = True
    return index
if __name__ == "__main__":
    try:
        while True:
            str1 = [i for i in input().split()]
            print(isRight(str1))  # 返回判断结果
    except:
        pass

运行结果同上。

最后奉上`数据结构与算法之美`专栏中的精彩文章

数据结构与算法之美 | 一文掌握栈Stack

0. 数据结构图文解析系列

1. 栈的基本概念

1.1 栈的特点

1.2 栈的相关概念

1.3 栈的操作

2. 栈的实现

2.1 栈的抽象数据类型

2.2 栈的常见分类

2.3 实例分析

3. 真题练习

热门文章

最新文章

相关课程

相关电子书

相关实验场景