精华内容
下载资源
问答
  • [数据结构]——单调

    万次阅读 多人点赞 2019-04-09 17:23:28
    笔者做leetcode的题(下一个出现的最大数字)时,接触到了单调这一种数据结构,经过研究之后,发现单调栈在解决某些问题时出奇的好用,下面是对单调的性质和一些典型题目。 什么是单调? 从名字上就听的出来...

    单调栈

    笔者在做leetcode的题(下一个出现的最大数字)时,接触到了单调栈这一种数据结构,经过研究之后,发现单调栈在解决某些问题时出奇的好用,下面是对单调栈的性质和一些典型题目。
    2020年11月23日更新

    没想到文章会火,这半年来一直有读者反映文章有问题,但本人也是大四学生一直在忙秋招,没时间修改文章。今天过来重新修改了下单调栈的定义。如果有问题请接着指正,十分感谢!

    2020年4月23日更新

    感谢各位同学对笔者之前文章错误的指出,此文章写于笔者学习数据结构早期,所以有些地方由于理解不深刻以及代码不规范出现了一些偏差。由于访问量的越来越多经常收到同学们的抱怨。在这里笔者非常感谢那些认真阅读文章后指出错误的小伙伴,现在笔者已经将错误改正,如果还有问题请接着指正!!!笔者90度鞠躬感谢!!!

    什么是单调栈?

    从名字上就听的出来,单调栈中存放的数据应该是有序的,所以单调栈也分为单调递增栈单调递减栈

    • 单调递增栈:单调递增栈就是从栈底到栈顶数据是从大到小
    • 单调递减栈:单调递减栈就是从栈底到栈顶数据是从小到大

    模拟单调栈的数据push和pop

    模拟实现一个递增单调栈:

    现在有一组数10,3,7,4,12。从左到右依次入栈,则如果栈为空入栈元素值小于栈顶元素值,则入栈;否则,如果入栈则会破坏栈的单调性,则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。

    • 10入栈时,栈为空,直接入栈,栈内元素为10。

    • 3入栈时,栈顶元素10比3大,则入栈,栈内元素为10,3。

    • 7入栈时,栈顶元素3比7小,则栈顶元素出栈,此时栈顶元素为10,比7大,则7入栈,栈内元素为10,7。

    • 4入栈时,栈顶元素7比4大,则入栈,栈内元素为10,7,4。

    • 12入栈时,栈顶元素4比12小,4出栈,此时栈顶元素为7,仍比12小,栈顶元素7继续出栈,此时栈顶元素为10,仍比12小,10出栈,此时栈为空,12入栈,栈内元素为12。

    单调栈的伪代码

    stack<int> st;
    //此处一般需要给数组最后添加结束标志符,具体下面例题会有详细讲解
    for (遍历这个数组)
    {
    	if (栈空 || 栈顶元素大于等于当前比较元素)
    	{
    		入栈;
    	}
    	else
    	{
    		while (栈不为空 && 栈顶元素小于当前元素)
    		{
    			栈顶元素出栈;
    			更新结果;
    		}
    		当前数据入栈;
    	}
    }
    

    单调栈的应用

    单调栈的应用我们直接拿一些具体的题来对照应用:

    1.视野总和

    描叙:有n个人站队,所有的人全部向右看,个子高的可以看到个子低的发型,给出每个人的身高,问所有人能看到其他人发现总和是多少。
    输入:4 3 7 1
    输出:2
    解释:个子为4的可以看到个子为3的发型,个子为7可以看到个子为1的身高,所以1+1=2
    思路:观察题之后,我们发现实际上题目转化为找当前数字向右查找的第一个大于他的数字之间有多少个数字,然后将每个          结果累计就是答案,但是这里时间复杂度为O(N^2),所以我们使用单调栈来解决这个问题。

    1.设置一个单调递增的栈(栈内0~n为单调递减)
    2.当遇到大于栈顶的元素,开始更新之前不高于当前人所能看到的值
    在这里插入图片描述

    int FieldSum(vector<int>& v)
    {
    	v.push_back(INT_MAX);/这里可以理解为需要一个无限高的人挡住栈中的人,不然栈中元素最后无法完全出栈
    	stack<int> st;
    	int sum = 0;
    	for (int i = 0; i < (int)v.size(); i++)
    	{
    		if (st.empty() || v[st.top()] > v[i])//小于栈顶元素入栈
    		{
    			st.push(i);
    		}
    		else
    		{
    			while (!st.empty() && v[st.top()] <= v[i])
    			{
    				int top = st.top();//取出栈顶元素
    				st.pop();
    				sum += (i - top - 1);//这里需要多减一个1
    			}
    			st.push(i);
    		}
    	}
    	return sum;
    }
    

    2.柱状图中的最大矩形

    https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
    在这里插入图片描述
    在这里插入图片描述
    思路:当前的数字可以向两边拓展,遇到比自己大的就接着拓展,小的就停止,然后用自己的高度乘以拓展的宽度,每次都         跟新最大面积,时间复杂度同样为O(N^2),所以我们接着借助单调栈

    上面使用了单调递增栈,这里我们通过这道例题来使用一下单调递减栈

    1.设置一个单调递减的栈(栈内0~n为单调递增)
    2.当遇到小于栈顶元素的值,我们开始更新数据,因为有可能最大面积就会出现在栈中的序列里
    3.牢记栈中数据永远是有序的,这个问题比较复杂,所以读者不妨对照着代码来理解问题

    int largestRectangleArea(vector<int>& heights) {
    	heights.push_back(-1);/同理,我们希望栈中所有数据出栈,所以给数组最后添加一个负数
    	stack<int> st;
    	int ret = 0, top;
    	for (int i = 0; i < heights.size(); i++)
    	{
    		if (st.empty() || heights[st.top()] <= heights[i])
    		{
    			st.push(i);
    		}
    		else
    		{
    			while (!st.empty() && heights[st.top()] > heights[i])
    			{
    				top = st.top();
    				st.pop();
    				//i-top指的是当前矩形的宽度,heights[top]就是当前的高度
    				//再次强调栈中现在为单调递增
    				int tmp = (i - top)*heights[top];
    				if (tmp > ret)
    					ret = tmp;
    			}
    			st.push(top);
    			heights[top] = heights[i];
    		}
    	}
    	return ret;
    }
    

    很多读者不太懂下图这两句代码:
    在这里插入图片描述
    假设遇到了小于栈顶的数据,我们需要判断下图中哪个矩形更大,并且跟新数据,这里应该都可以理解,我们将图中三个数据标记为0,1,2.接着往下看
    在这里插入图片描述
    因为需要保持栈中递增的属性,所以栈中只有i一个数据:
    在这里插入图片描述
    但是对于当前元素来说下标为0,1的元素都比他大,所以那么就意味着它可以向左延申扩大矩形:像下图那样
    在这里插入图片描述
    但是我们为了保持栈中的递增属性,并且可以让i可以向左拓展,我们索性修改了i的下标,将他修改为最左边的top下标,所以当我们下次需要以他为基准获取矩形面积时就像这样
    在这里插入图片描述
    所以假设我们数组中的4个数据(实际是5个,最后一个数字用来出栈所有数据)全部访问完时:如下面的方式计算矩形
    在这里插入图片描述
    ps:如果有的同学还是不清楚,可以用自己的编译器调试一下。

    3.求最大区间

    描述:给出一组数字,求一区间,使得区间元素和乘以区间最小值最大,结果要求给出这个最大值和区间的左右端点
    输入:3 1 6 4 5 2
    输出:60
           3 5
    解释:将3到5(6+4+5)这段区间相加,将和与区间内最小元素相乘获得最大数字60
    思路:使用暴力解法求出所有区间,再求出区间的最小值相乘跟新数据,并不是一种很好的算法,所以经过上面俩题的磨         炼,此时我们应该使用一个单调递减栈

    1.设置一个单调递减的栈(栈内0~n为单调递增)
    2.当遇到小于栈顶元素的值,我们开始更新数据,因为当前遇到的值一定是当前序列最小的

    int GetMaxSequence(vector<int>& v)
    {
    	stack<int> st;
    	vector<int> vs(v.size()+1);
    	vs[0] = 0;
    	for (int i = 1; i < vs.size(); i++)
    	{
    			vs[i] = vs[i - 1] + v[i-1];
    	}
    	v.push_back(-1);
    	int top, start, end, ret = 0;
    	for (int i = 0; i < v.size(); i++)
    	{
    		if (st.empty() || v[st.top()] <= v[i])
    		{
    			st.push(i);
    		}
    		else
    		{
    			while (!st.empty() && v[st.top()] > v[i])
    			{
    				top = st.top();
    				st.pop();
    				int tmp = vs[i] - vs[top];
    				tmp = tmp * v[top];
    				if (tmp > ret)
    				{
    					ret = tmp;
    					start = top+1;
    					end = i;
    				}
    			}
    			st.push(top);
    			v[top] = v[i];//与第二题相同的道理,将当前数据的更改最左的top下标,防止出现比当前数据更小的数据
    			//这句在这道题里真的超级难理解,但是只要你有耐心相信你可以理解的
    		}
    	}
    	return ret
    }
    

    总结

    单调栈是帮助我们完成算法的一个数据结构,很多的题中还是单调栈的身影,更多需要单调栈的题就希望读者自己去发现啦,文章如果有什么问题或者建议希望广大读者们可以提出。

    展开全文
  • C++数据结构——

    万次阅读 多人点赞 2018-06-25 21:54:49
    C++数据结构—— 最近计划再复习一遍数据结构,看到一篇博客:https://www.cnblogs.com/QG-whz/p/5170418.html#_label0。 1、(Stack)是一种线性存储结构,它具有如下特点: ...

                                                          C++数据结构——栈

     

                最近计划再复习一遍数据结构,看到一篇博客:https://www.cnblogs.com/QG-whz/p/5170418.html#_label0

    1、栈(Stack)是一种线性存储结构,它具有如下特点:

    (1)栈中的数据元素遵守“先进后出"(First In Last Out)的原则,简称FILO结构。(后进先出的叫法,也是可以的)

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

    2、栈的相关概念:

    (1)栈顶与栈底:允许元素插入与删除的一端称为栈顶,另一端称为栈底。

    (2)压栈:栈的插入操作,叫做进栈,也称压栈、入栈。

    (3)弹栈:栈的删除操作,也叫做出栈。

    3、栈的常用操作为:

    (1)弹栈,通常命名为pop

    (2)压栈,通常命名为push

    (3)求栈的大小

    (4)判断栈是否为空

    (5)获取栈顶元素的值

    4、栈的常见分类:

    (1)基于数组的栈——以数组为底层数据结构时,通常以数组头为栈底,数组头到数组尾为栈顶的生长方向

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

    5、实例分析

           使用标准库的栈时, 应包含相关头文件,在栈中应包含头文件: #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;
    		T 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;
    }

     

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

              解法参考博客:https://blog.csdn.net/cherrydreamsover/article/details/79475925,具体过程如下:

    (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函数。
    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——栈的压入、弹出序列

           参考博客:https://blog.csdn.net/budf01/article/details/76232497,解题思路为:创建一个栈进行压入、弹出操作。具体操作如下: 
    (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,不太好想,mad,笔试那会儿就没想到!)

           以下是我的想法,具体的过程如下:

          (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

    运行结果同上。

    展开全文
  • 数据结构————2016_11_21

    万次阅读 多人点赞 2016-11-21 21:35:58
    //定义栈结构 typedef struct{ int * base; int * top; int stacksize; }SqStack; //初始化 void InitStack(SqStack * s){ s->base=(int *)malloc(stack_init_size*sizeof(int)); if(!s->base) exit(0); ...
    栈源代码(C语言版)

    /**********实现了Pop,Push,Empty,Print,conversion等功能*********/



    #include<stdio.h>
    #include<stdlib.h>
    #define stack_init_size 10
    #define STACKINCREMENT 10
    
    //定义栈结构
    typedef struct{
        int * base;
    	int * top;
    	int stacksize;
    }SqStack;
    //初始化栈
    void InitStack(SqStack * s){
    
        s->base=(int *)malloc(stack_init_size*sizeof(int));
    	if(!s->base)
    		exit(0);
    	s->top=s->base;
    	s->stacksize=stack_init_size;
    	
    }
    //压栈
    void Push(SqStack * s,int e){
    	if(s->top-s->base==s->stacksize){
    	   s->base=(int *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(int));
    	   if(!s->base)
    		   exit(0);
    	   s->top=s->base+s->stacksize;
    	   s->stacksize+=STACKINCREMENT;
    	}
    	*s->top=e;
    	s->top++;
    }
    //弹栈
    int Pop(SqStack * s){
    	int e;
         if(s->top==s->base)
    	 {printf("栈已空!\n");
    	        exit(0);
    	 }
    	 s->top--;
    	 e=*s->top;
    	 return e;
    }
    //判断是否为空
    int EmptyStack(SqStack s){
      if(s.top==s.base)
    	return 1;
      else 
    	  return 0;
    }
    //置空栈   后面没用上。。。
    void ClearStack(SqStack * s){
       s->top=s->base;
    }
    //打印栈
    void PrintStack(SqStack s){
        while(!EmptyStack(s)){
    		s.top--;
    	   printf("%d  ",*s.top);
    	}
    	printf("\n\n");
    }
    //进制转换函数
    void conversion(int N,int d){
    	SqStack M;
    	InitStack(&M);
    	printf("你输入的数值%d转换成%d进制后为:",N,d);
    	while(N){
    	   Push(&M,N%d);
    	   N=N/d;
    	}
       while(!EmptyStack(M)){
          PrintStack(M);
    	  break;
       }
       printf("\n");
    }
    //主函数
    int main(){
    	SqStack M;
    	int x,y,z,i,j;
    	InitStack(&M);
    	printf("——栈已初始化完成——\n\n\n");
    	printf("请输入要操作的序号:\n");
    	printf("1·入栈 2·出栈 3·进制转换 4·退出\n");
    	scanf("%d",&x);
    	while(x!=0){
    	  switch(x){
    	     case 1:printf("请输入要入栈的数值:\n");
    			    scanf("%d",&y);
                    Push(&M,y);
    				PrintStack(M);
    				break;
    		 case 2:printf("出栈的数值为:");
    			    z=Pop(&M);
    				printf("%d\n",z);
    				PrintStack(M);
    				break;
    		 case 3:printf("请输入要转换的数值和进制:\n");
    			    scanf("%d%d",&i,&j);
    				conversion(i,j);
    				break;
    		 case 4:exit(0);
    			    break;
    		 default:printf("输入有误,请重新输入:\n");
    	  }
    	  printf("1·入栈 2·出栈 3·进制转换 4·退出\n");
    	  scanf("%d",&x);
    	}
    	return 0;
    }
    

    程序运行截图


        联系邮箱:xhsgg12302@outlook.com

                                                                                             2016_11_21

    展开全文
  • 结构是一种非常常见的数据结构,并且很多场景下也被用到。其实结构跟数组结构很像,只是数组的基础...数据结构——一、什么二、结构的方法三、用代码实现一个结构(1)创建一个构造函数(2)实现push

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    栈结构是一种非常常见的数据结构,并且在很多场景下也被用到。其实栈结构跟数组结构很像,只是在数组的基础上,对栈结构做了一些限制,本文我们将对其进行详细的介绍。
    在这里插入图片描述

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    一、什么是栈

    上面是说了,相对于数组结构做了一些限制。在使用数组结构的时候,我们可以任意的取出数组内的任何元素,也可以随意在指定位置插入元素,而却对元素的获取插入做了一些限制。

    我们可以形象地把栈理解成一个没有盖子的茶杯,例如下图
    在这里插入图片描述
    杯口的位置叫做栈顶
    杯底的位置叫做栈底

    现在我们往被子里放入一个物体,这个操作叫做入栈,这也就相当于我们向栈内插入一个元素
    在这里插入图片描述
    我们再进行一次入栈操作,结果如下
    在这里插入图片描述
    此时,我们想要从杯子里拿出一个物体,可以很明显的看到,物体1物体2盖住了,所以我们只能先拿到 物体2,所以,我们就把 物体2 取出了,这样的操作成为出栈,结果如下
    在这里插入图片描述
    此时再进行一次出栈操作,就把 物体1 拿出来了,此时栈就为空了,结果如下:
    在这里插入图片描述

    看了上面的讲解,相信你们对栈结构有了很深刻的印象,所以这里我来总结一下:

    • 栈是一种受限的线性数据结构,它对元素的操作遵循的是先进后出,也就是向入栈的元素会比后入栈的元素晚一点取出来。

    二、栈结构的方法

    我们都知道像数组结构,都有一些操作元素的方法,例如在末尾插入元素 、在头部插入元素 、删除指定位置的元素等等,同样的,栈结构也是有它自己的操作元素的方法的,接下来我们就来介绍一下,栈结构常用的操作元素的方法有哪些吧。

    方法 含义
    push() 入栈操作
    pop() 出栈操作
    getTopElement() 返回栈顶的元素,但不会移除栈顶的元素
    isEmpty() 查看栈是否为空
    size() 返回栈内元素的个数
    toString() 以字符串的形式展示栈内的所有元素

    三、用代码实现一个栈结构

    接下来,我们就用JavaScript封装实现一个基于数组的栈结构的类,因为是基于数组实现的栈,所以我们可以把数组的头部看作是栈底,把数组的尾部看作是栈顶

    (1)创建一个构造函数

    首先就是声明一个构造函数Stack,然后并在内部创建一个空数字,用于储存数据元素

    function Stack() {
    	//属性
        this.list = []
    }
    

    (2)实现push()方法

    push()方法就是进行入栈操作,所以我们需要向栈顶(数组的尾部)插入元素

    接下来我们来单独实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //push()方法的实现
        Stack.prototype.push = function (e) {
            this.list.push(e)
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    stack.push(3)
    stack.push(9)
    stack.push(5)
    

    经过上面操作后,栈内的情况是这样的:
    在这里插入图片描述

    (3)实现pop()方法

    pop()方法就是进行出栈操作,所以我们需要取出栈顶的第一个元素(数组的尾部),并返回取出的元素

    接下来我们就来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //pop()方法的实现
        Stack.prototype.pop = function (e) {
            return this.list.pop()
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    //先按 3 9 5 的顺序入栈,再进行出栈操作
    stack.push(3)
    stack.push(9)
    stack.push(5)
    
    stack.pop()        //返回 5
    

    此时栈内的情况是这样的,元素5被取出,此时栈顶第一个为元素9
    在这里插入图片描述

    (4)实现getTopElement()方法

    getTopElement()方法就相当于是查看一下栈顶的元素是什么(查看数组尾部的元素),而不会对栈内元素进行任何的入栈或出栈操作

    我们来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //getTopElement()方法的实现
        Stack.prototype.getTopElement = function () {
            return this.list[this.list.length - 1]
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    //先按 3 9 5 的顺序入栈,再查看一下栈顶元素是什么
    stack.push(3)
    stack.push(9)
    stack.push(5)
    
    stack.getTopElement()     //返回 5
    

    (5)实现isEmpty()方法

    isEmpty()方法就是看看栈内是否有元素(查看数组是否为空),有的话就返回 false,没有就返回 true

    我们来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //isEmpty()方法的实现
        Stack.prototype.isEmpty = function () {
            let size = this.list.length
            if(size === 0) {
                return true
            }
            else {
                return false
            }
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    
    stack.isEmpty()    // true,因为此时还没有插入元素
    
    stack.push(3)
    
    stack.isEmpty()   // false,将 3 入栈了,所以栈不会空,返回false
    

    (6)实现size()方法

    size()方法就是查看栈内有多少元素(查看数组的长度)并返回

    我们来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //size()方法的实现
        Stack.prototype.size = function () {
            return this.list.length
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    
    stack.size()       // 0,因为还没进行过入栈操作
    
    stack.push(4)
    stack.push(7)
    
    stack.size()       //  2,因为栈内有两个元素,所以返回 2
    

    (7)实现toString()方法

    toString()方法就是将栈内的元素用字符串的方式展示出来(将数组转化成字符串)并返回

    我们来实现一下该方法

    function Stack() {
    	//属性
    	this.list = []
    	
        //toString()方法的实现
        Stack.prototype.toString = function () {
            let string = ''
            for(let i in this.list) {
                string += `${this.list[i]} `
            }
            return string
        }
    }
    

    我们来使用一下该方法

    let stack = new Stack()
    
    stack.push(3)
    stack.push(9)
    stack.push(5)
    
    stack.toString()        //   返回 3 9 5
    

    四、栈结构的实战应用

    现在需要通过栈结构实现一个函数,将输入的十进制转化成二进制

    我们都知道,十进制转二进制是将一个数每次都除以2,一直到无法再除以2以后,倒着将每次除以2后获得的余数连接起来,就是正确的二进制数,如下图
    在这里插入图片描述
    所以,我们可以看到,最先获得的余数是最后才被取走的,这是一个很典型的栈结构的例子。每次除得的余数,就对其进行入栈操作,最后再进行多次出栈操作就可以实现十进制转二进制的功能了。

    因此我们来封装一下这样一个函数

    function d2b(number) {
        let stack = new Stack()
    
        while (number > 0) {
    
            stack.push(number % 2)
    
            number = Math.floor(number / 2)
        }
    
        let string = ''
        while (!stack.isEmpty()) {
            string += stack.pop()
        }
    }
    

    我们来使用一下这个函数,看看是否正确

    d2b(100)           //返回 1100100
    

    好了,这个例子的功能函数封装完成了

    五、总结

    栈结构的讲解就到这里了,希望大家对栈结构有了更深一层的理解。下一篇文章我将讲解一下队列

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • 数据结构什么

    千次阅读 2018-06-17 15:26:34
    首先系统或者数据结构栈中数据内容的读取与插入(压入push和 弹出pop)是两回事!插入是增加数据,弹出是删除数据 ,这些操作只能从栈顶即最低地址作为约束的接口界面入手操作 ,但读取栈中的数据是随便的没有接口...
  • 数据结构-和队列

    万次阅读 多人点赞 2012-06-19 12:53:15
    其特殊性在于限定插入和删除数据元素的操作只能线性表的一端进行。如下所示: 结论:后进先出(Last In First Out),简称为LIFO线性表。 的基本运算有六种: 构造空栈:InitStack(S)、 判空: StackEmpty...
  • 数据结构——的详解

    万次阅读 多人点赞 2020-04-20 00:02:43
    和队列是两种重要的线性结构,从数据结构的角度看,和队列也是线性表,其特殊性在于和队列的基本操作是线性表的子集。他们是操作受限的线性表,因此,可称为限定性的数据结构。但从数据类型角度看,他们是和...
  • 数据结构之队列和

    千次阅读 2019-10-23 15:54:14
    数据结构之队列和
  • 数据结构与算法—详解

    千次阅读 多人点赞 2019-08-13 18:51:04
    目录什么设计与介绍数组实现结构设计push插入s 什么 百度百科上,是这么定义的: (stack)又名堆栈,它是一种运算受限的线性表。限定仅表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地...
  • 数据结构——

    千次阅读 2019-03-21 21:36:13
    是一种数据结构,今天我们先来理解下的定义,然后再看几个现实开发运用到的实例。 1. 什么是一个具有“先进后出、后进先出”这种特点的数据结构。 从的结构图可以看出,是一种“操作受限...
  • 系统堆栈的故事+数据结构中的堆和
  • JavaScript数据结构结构

    千次阅读 多人点赞 2021-01-17 16:36:12
    JavaScript数据结构之栈结构前言一、栈结构是什么?二、常见的栈结构使用:**函数调用栈**、**递归等**。三、使用步骤1.创建Stack类2.使用栈总结 ...在栈中插入操作被称为压栈或是入栈,删除操作被称为
  • 数据结构实践项目——

    千次阅读 2015-09-20 09:23:00
    本组项目针对《数据结构基础系列(3):线性表》的1-6课: 1 “和队列”导学 2 的定义 3 的顺序存储结构及其基本运算实现 4 的链式存储结构及其基本运算的实现 5 的应用1-表达式求值 6 的应用2-...
  • 数据结构~07.和队列的基本概念

    万次阅读 热门讨论 2020-07-28 08:26:32
    数据结构学习~07.和队列的基本概念 本文是上一篇文章的后续,详情点击该链接~ 的定义:        是一种只能一端进行插入或删除的线性表。其中,允许插入或删除的一端为栈顶...
  • 数据结构-

    千次阅读 2017-08-13 00:24:25
    栈栈的定义是一种特殊的线性表,仅允许表的一端进行插入和删除运算。这一端被称为栈顶(top),相对地,把另一端称为底(bottom)。向一个插入新元素又称作进栈、入栈或压栈(push),它是把新元素放到栈顶...
  • 数据结构中和堆,计算机系统内存和堆的理解
  • 数据结构

    千次阅读 2015-10-30 19:36:18
    (一)栈的定义及基本运算 (1)栈的定义 ...在栈中进行插入和删除操作的一端称为栈顶(top),相应地,另一端称为栈底(bottom)。不含数据元素的栈称为空栈。 (2)栈的基本算法 初始化栈InitStack(S):创建
  • 数据结构顺序表(的操作问题) x='@'; 在数据结构中什么意义?
  • 数据结构stack

    千次阅读 2017-11-25 16:38:08
    在栈中,元素的添加和删除操作只能表的一端进行,即栈顶。 元素的添加和删除遵循“后进先出”(LIFO)的原则,最后添加的元素总是最先出栈 栈对元素的访问加以限制,仅仅提供对栈顶元素的访问操作 栈是如何
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    常用的数据结构有:数组,,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。 1、数组 数组是可以再内存连续存储多个元素的...
  • 数据结构中和堆(堆栈) 首先在数据结构上要知道堆栈,尽管我们这么称呼它,但实际上堆栈是两种数据结构:堆和。 堆和都是一种数据项按序排列的数据结构就像弹夹,先装进去的最后出来,FILO(First in...
  • 数据结构,我们知道有关于的概念都是逻辑上的,而《汇编语言》一门课,关于的操作就是对内存的操作。以下的都是我学习了王爽的《汇编语言》第三版以及清华大学出版社的《数据结构》第四版的有关...
  • ,是数据结构设计的最重要的思想之一,但是我疑惑的是为什么先进的元素反而要后出。 要是生活我们也是按照的规则来排顺序,这个世界岂不是乱了套了,试想你去银行排队取钱,明明你是第一个去,却等到晚上...
  • 数据结构-队列和什么区别

    千次阅读 2018-10-19 15:44:19
    一、队列与的定义: 队列(Queue):是限定...队列和是两种不同的数据结构。它们有以下区别: (1)操作的名称不同。 队列的插入称为入队,队列的删除称为出队。的插入称为进栈,的删除称为出栈。 (...
  • java数据结构---

    万次阅读 2018-11-01 16:56:53
    是一种特殊的线性表,并且只能一端进行插入和删除操作 本文采用链表来创建 1.创建一个节点的类 package cn.itcast.com.istack; public class Node { public Object data; public Node next; public...
  • java数据结构——

    千次阅读 2018-10-24 09:06:59
    ,队列是比数组和其他数据结构更抽象的结构,主要通过接口对,队列进行定义,而他们的主要实 现机制对用户是不可见的。 的主要机制可以用数组来实现,也可以用链表来实现。优先级队列的内部 实现可以用数组或...
  • 2022年考研数据结构_3 和队列

    万次阅读 2020-12-28 16:37:40
    文章目录3. 和队列3.1 3.1.1 的定义3.1.2 的实现3.1.3 的应用(1)递归(2)四则运算表达式求解①中缀表达式转后缀表达式②后缀表达式的计算3.2 队列3.2.1 队列的定义3.2.2 队列的...是限定仅表尾进行插入
  • Java 数据结构之 Stack()

    万次阅读 2013-03-08 15:40:40
    Stack作为最基本的数据结构JDK代码,也有它的实现,java.util.Stack类是继承了Vector类,来实现了的基本功能。   一、的基本原理   (Stack)是限定仅表尾进行插入或者删除操作的线性表...
  • 一文详解堆栈(一)——数据结构的堆与

    千次阅读 多人点赞 2019-10-15 18:55:26
    前言:我们经常听见一个概念,堆(heap)和(stack),其实在数据结构中也有同样的这两个概念,但是这和内存的堆栈是不一样的东西哦,本文也会说明他们之间的区别的,另外,本文的只是是以C/C++为背景来说明,不同...
  • 数据结构

    万次阅读 多人点赞 2014-12-07 09:36:01
    鉴于CSDN对**版权保护的不作为**以及落后的运营手段,本博客将于近期关闭,并清空全部文章。...原有文章将会经过再次的校对、整理,转移至本人**简书**的[博客空间](https://www.jianshu.com/u/3ec23ef9a408)。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 505,999
精华内容 202,399
关键字:

在数据结构中什么是栈

数据结构 订阅