利用栈的数据结构_利用c语言数据结构对链栈赋值 - CSDN
  • ![图片说明](https://img-ask.csdn.net/upload/201510/12/1444656527_14215.png) 为何结果是stack?pop(s,x)的用法是什么? O(∩_∩)O谢谢
  • 前言:我们经常听见一个概念,堆(heap)和(stack),其实在数据结构中也有同样的这两个概念,但是这和内存的堆栈是不一样的东西哦,本文也会说明他们之间的区别的,另外,本文的只是是以C/C++为背景来说明,不同...

    前言:我们经常听见一个概念,堆(heap)和栈(stack),其实在数据结构中也有同样的这两个概念,但是这和内存的堆栈是不一样的东西哦,本文也会说明他们之间的区别的,另外,本文的只是是以C/C++为背景来说明,不同的语言在内存管理上面会有区别。本文是第一篇,简要介绍数据结构中的堆与栈。

    一、数据结构中的堆与栈

    数据结构中,堆(heap)与栈(stack)是两个常见的数据结构,理解二者的定义、用法与区别,能够利用堆与栈解决很多实际问题。

    1.1 栈简介
             栈是一种运算受限的线性表,其限制是指只仅允许在表的一端进行插入和删除操作,这一端被称为栈顶(Top),相对地,把另一端称为栈底(Bottom)。把新元素放到栈顶元素的上面,使之成为新的栈顶元素称作进栈、入栈或压栈(Push);把栈顶元素删除,使其相邻的元素成为新的栈顶元素称作出栈或退栈(Pop)。这种受限的运算使栈拥有“先进后出”的特性(First In Last Out),简称FILO

    (1)栈的分类

    栈分顺序栈链式栈两种。栈是一种线性结构,所以可以使用数组或链表(单向链表、双向链表或循环链表)作为底层数据结构。使用数组实现的栈叫做顺序栈,使用链表实现的栈叫做链式栈,二者的区别是顺序栈中的元素地址连续,链式栈中的元素地址不连续。   

    栈的结构如下图所示:
    这里写图片描述

    1.2 堆简介

    (1)堆的简介及性质


           堆是一种常用的树形结构,是一种特殊的完全二叉树,当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。堆的这一特性称之为堆序性

           Heap: 堆。一般也称作Priority Queue(即优先队列)

           因此,在一个堆中,根节点是最大(或最小)节点。如果根节点最小,称之为小顶堆(或小根堆),如果根节点最大,称之为大顶堆(或大根堆)。堆的左右孩子没有大小的顺序。

    堆的应用十分广泛,下面给出一些堆的常见操作:

    1. 上浮 shift_up;
    2. 下沉 shift_down
    3. 插入 push
    4. 弹出 pop
    5. 取顶 top
    6. 堆排序 heap_sort

    关于堆的一些具体实现,本文暂时不给出,后面有时间了再更新

     

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

    2020-04-21 23:25:47
    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;
    		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;
    }

     

    练习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

    运行结果同上。

    展开全文
  • 最近刷数据结构的黑宝书,顺便将数据结构进行下总结,就先从最熟悉的开始吧。 (stack),数据结构中的一种,准确的来说,应该是数据逻辑结构。 的基本特点为: 后进先出,就像生活中我们取放盘子,当一摞盘子...

    最近刷数据结构的黑宝书,顺便将数据结构进行下总结,就先从最熟悉的栈开始吧。


    栈(stack),数据结构中的一种,准确的来说,应该是数据逻辑结构

    栈的基本特点为: 后进先出,就像生活中我们取放盘子,当一摞盘子在桌子上时候,我们总是会取最上边的盘子,同时,我们在放盘子时,也会放在最上面。同样这种机制也在我们浏览网页时也有出现,在我们浏览网页时,左上角的转到上一页就是这种,最近浏览的网站在最上层,当返回时,先取到最上层的地址,这样即实现了逐层后退。

    栈有几个基本的操作

    • push         向栈底添加一个元素     
    • pop           从栈顶取出一个元素
    • peek          复制栈顶元素,但不进行删除
    • size           判定栈中所含元素的个数
    • isEmpty    判断栈是否为空

    因为对树结构还不够熟悉,我们就用简单的数组链表来实现一个栈。


    数组实现

    利用数组实现栈,我们可以设置自定义容量和默认容量,也可以设置自动扩容机制。数组实现机制相对来说更加简单,考虑到栈的操作总是取最近添加的元素,所以,我们以头部作为栈底,尾部作为栈顶,这样向栈内添加元素时,时间复杂度为常数,对于经常对栈顶进行操作,并且栈内数据非常庞大的情况下,效率相对较高。

    下面利用Java代码进行方法实现

    package Stack;
    
    public class ArrayStack {
    	/*
    	 * 该类为使用数组实现的一个栈(Stack)
    	 * 具有成员方法pop,push,peek,isEmpty,size,getMaxElementNumber
    	 * 具有构造方法两种,默认容量和指定容量
    	 * 数组应具有自动扩容能力(可选)
    	 */
    	//该值为栈索引,各项方法均对其进行操作(固定长度数组)
    	private int STACK_ARRAY_INDEX_OF_HANDMOVEMENT = 0;
    	//该值为栈最大容量数
    	public int TOP;
    	
    	private Object[] StackArray;
    	
    	public ArrayStack() {
    		//默认栈容量为15
    		StackArray = new Object[15];
    	}
    	
    	public ArrayStack(int TOP) {
    		//指定栈容量
    		StackArray = new Object[TOP];
    		//返回TOP值,用于后续判断操作
    		this.TOP = TOP;
    	}
    	/*
    	 * 栈推入操作  具有判满功能
    	 */
    	public boolean push(Object element) {
    		//判断栈顶是否满元素,若满,进行扩容,若空进行添加
    		if(StackArray[StackArray.length-1] != null) {
    			/*
    			 * 准备新数组,将原数组数据全部复制进去
    			 * 将原数组删除并扩容 扩容指数为2倍
    			 * 将新数组数据复制进原数组
    			 */
    			Object[] StackArrayNew = new Object[StackArray.length];
    			for(int i = 0;i<=StackArrayNew.length;i++) {
    				StackArrayNew[i] = StackArray[i];
    			}
    			StackArray = new Object[StackArrayNew.length * 2];
    			for(int i = 0;i<=StackArrayNew.length;i++) {
    				StackArray[i] = StackArrayNew[i];
    			}
    			StackArray[STACK_ARRAY_INDEX_OF_HANDMOVEMENT] = element;
    			STACK_ARRAY_INDEX_OF_HANDMOVEMENT++;
    			return true;
    		}else {
    			StackArray[STACK_ARRAY_INDEX_OF_HANDMOVEMENT] = element;
    			STACK_ARRAY_INDEX_OF_HANDMOVEMENT++;
    			return true;
    		}
    	}
    	
    	/*
    	 * 栈取出操作,具有判空功能
    	 */
    	public Object pop() {
    		//判断栈中是否有元素,若有返回Object实例,若无返回提示
    		
    		if(StackArray[0] == null) {
    			return null;
    		}else {
    			Object theReturnResult =                                                
    StackArray[STACK_ARRAY_INDEX_OF_HANDMOVEMENT];
    			StackArray[STACK_ARRAY_INDEX_OF_HANDMOVEMENT] = null;
    			return theReturnResult;
    		}
    	}
    	/*
    	 * 判断栈中元素个数方法
    	 */
    	public int size() {
    		int index = 0;
    		while(StackArray[index] == null) {
    			index++;
    		}
    		return index;  
    	}
    	/*
    	 * 判断是否为空
    	 */
    	public boolean isEmpty() {
    		if(StackArray[0] == null) 
    			return true;
    			return false;
    	}
    	/*
    	 * peek复制栈顶元素
    	 */
    	public Object peek() {
    		//判断栈中是否有元素,若有返回Object实例,若无返回提示
    		if(StackArray[0] == null) {
    			System.out.println("该栈为空");
    			return null;
    		}else {
    			Object theReturnResult = StackArray[STACK_ARRAY_INDEX_OF_HANDMOVEMENT];
    			return theReturnResult;
    		}
    	}
    }

    Ps:该栈内实现了基本的五个操作,并且对基本的操作进行了判空功能。


    链表实现

    在这里就先不进行链表的介绍,等有时间再开一篇链表的总结。

    为了实现起来更加方便,利用单链表即可满足栈的需求。对于链表来说,增删改的操作时间为常数,而因为其引用的特性,遍历的花费十分昂贵,所以我们为了优化栈的性能,尽可能减少遍历链表所浪费的时间,我们将链表表头作为栈顶,这样每次存取操作只需要用头引用取表头数据即可。

    首先我们需要在链表内维护一个节点类

    package MyLinkedList;
    /*
     * 该类为单链表类的节点类,该类只服务于LinkedList类,并不进行对外暴露
     */
    public class SingleLinkedListNode {
    	//该引用为链表中的数据部分,用于存放数据
    	public Object data;
    	//该引用为指向下一个链表,最后一个可循环或者置空
    	public SingleLinkedListNode Next;
    	
    	public SingleLinkedListNode(Object data,SingleLinkedListNode Next) {
    		this.data = data;
    		this.Next = Next;
    	}
    
    	public Object getData() {
    		return data;
    	}
    
    	public void setData(Object data) {
    		this.data = data;
    	}
    
    	public SingleLinkedListNode getNext() {
    		return Next;
    	}
    
    	public void setNext(SingleLinkedListNode next) {
    		Next = next;
    	}
    	
    }

    下面用链表实现

    package MyLinkedList;
    /*
     * 该类为单链表类的节点类,该类只服务于LinkedList类,并不进行对外暴露
     */
    public class SingleLinkedListNode {
    	//该引用为链表中的数据部分,用于存放数据
    	public Object data;
    	//该引用为指向下一个链表,最后一个可循环或者置空
    	public SingleLinkedListNode Next;
    	
    	public SingleLinkedListNode(Object data,SingleLinkedListNode Next) {
    		this.data = data;
    		this.Next = Next;
    	}
    
    	public Object getData() {
    		return data;
    	}
    
    	public void setData(Object data) {
    		this.data = data;
    	}
    
    	public SingleLinkedListNode getNext() {
    		return Next;
    	}
    
    	public void setNext(SingleLinkedListNode next) {
    		Next = next;
    	}
    }

    只实现了几个基本操作,对于size,isEmpty等方法,和数组实现原理相同。


    最后再简单介绍一种较为特殊的栈,该栈为栈中的一个特殊形式,主要用于取消操作,使用数组进行实现,该栈不能进行自动扩容,并且栈满后将从栈低进行元素删除。

    其原理和以上两种栈无差别,只不过在栈满后,先将栈底元素删除,再将栈元素向前移动,最后在栈顶添加元素。

    package Stack;
    
    public class OverFlowStack {
    	/*
    	 * 该栈为栈中的一个特殊形式,主要用于取消操作,使用数组进行实现 
    	 * 该栈不能进行自动扩容,并且栈满后将从栈低进行元素删除
    	 * 该栈具有方法为pop,push,peek,size,isEmpty
    	 */
    
    	// 该值为栈索引,各项方法均对其进行操作(固定长度数组)
    	private int STACK_ARRAY_INDEX_OF_HANDMOVEMENT = 0;
    
    	public int TOP;
    
    	private Object[] OverFlowStack;
    
    	public OverFlowStack() {
    		// 默认栈容量为15
    		OverFlowStack = new Object[15];
    	}
    
    	public OverFlowStack(int TOP) {
    		// 指定栈容量
    		OverFlowStack = new Object[TOP];
    		// 返回TOP值,用于后续判断操作
    		this.TOP = TOP;
    	}
    
    	public boolean push(Object element) {
    		// 首先对栈进行数据判断,如果栈内还有空间,直接添加
    		// 如果栈内已经满数据,从栈底删除最后一个数据并进行数组索引的移动
    		if (OverFlowStack[OverFlowStack.length - 1] == null) {
    			OverFlowStack[STACK_ARRAY_INDEX_OF_HANDMOVEMENT] = element;
    			return true;
    		} else {
    			// 通过while进行对栈内数据移动的操作
    			// 移动次数为INDEX-1
    			int temp = 0;
    			while (temp <= OverFlowStack.length - 1) {
    				OverFlowStack[temp] = OverFlowStack[temp + 1];
    				temp++;
    			}
    			return true;
    		}
    	}
    	/*
    	 * 栈取出操作,具有判空功能
    	 */
    	public Object pop() {
    		//判断栈中是否有元素,若有返回Object实例,若无返回提示
    		
    		if(OverFlowStack[0] == null) {
    			return null;
    		}else {
    			Object theReturnResult = OverFlowStack[STACK_ARRAY_INDEX_OF_HANDMOVEMENT];
    			OverFlowStack[STACK_ARRAY_INDEX_OF_HANDMOVEMENT] = null;
    			return theReturnResult;
    		}
    	}
    	/*
    	 * 判断栈中元素个数方法
    	 */
    	public int size() {
    		int index = 0;
    		while(OverFlowStack[index] == null) {
    			index++;
    		}
    		return index;  
    	}
    	/*
    	 * 判断是否为空
    	 */
    	public boolean isEmpty() {
    		if(OverFlowStack[0] == null) 
    			return true;
    			return false;
    	}
    	/*
    	 * peek复制栈顶元素
    	 */
    	public Object peek() {
    		//判断栈中是否有元素,若有返回Object实例,若无返回提示
    		if(OverFlowStack[0] == null) {
    			System.out.println("该栈为空");
    			return null;
    		}else {
    			Object theReturnResult = OverFlowStack[STACK_ARRAY_INDEX_OF_HANDMOVEMENT];
    			return theReturnResult;
    		}
    	}
    }

    基本内容就总结到这里,如果有错误的地方请留言指出,萌新发文,请大神轻喷。

    本文原创,转载请注明来源。

    QQ   489282384

                             JoryB

    展开全文
  • 的简介 作为一种数据结构,是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来...

        栈的简介

           栈作为一种数据结构,是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

        栈的作用

        1、内存管理中使用的堆栈;

         2、基于桟实现的二叉树的遍历;

         3、在处理需求中的平衡问题:

                (1)判断符号是成对出现的,比如<>,{},[],()等

                (2)判断这个字符串是否是回文字符串,比如:bcb, '123321',等。

        栈的C语言实现:

       demo:判读一个字符串是否是回文字符串,输入bcb, 输出yes

        思路分析:

                (1)首先,读取这行字符串,并且计算这个字符串的长度

                (2)其次,如果一个字符串是回文的话,那么它的一定是对称的,计算出中点。

                        mid =  len / 2  -1

                (3)再次,我们将mid之前的数据全都写入到栈中

                (4)最后,再将写入的数据一词取出,并且和mid之后的数据进行比较,如果可以匹配成功,返回输出yes, 否者输出no

        代码如下:



        栈的python语言实现:

        

    class Node(object):
        # 定位的点的值和一个指向
        def __init__(self, val):
            # 指向元素的值,原队列第二元素
            self.val = val
            # 指向的指针
            self.next = None
    class stack(object):
        # 初始化最开始的位置
        def __init__(self):
            self.top = None
            # 获取栈顶的元素
        def peek(self):
            # 如果栈顶不为空
            if self.top != None:
                # 返回栈顶元素的值
                return self.top.val
            else:
                return None
        # 添加到栈中
        def push(self,n):
            # 实例化节点
            n = Node(n)
            # 顶端元素传值给一个指针
            n.next = self.top
            self.top = n
            return n.val
    
        # 退出栈
        def pop(self):
            if self.top == None:
                return None
            else:
                tmp = self.top.val
                # 下移一位,进行
                self.top = self.top.next
                return tmp
    
    if __name__ == '__main__':
        s = stack()
        s.push(1)
        print(s.pop())
    
    

    展开全文
  • 一、先理解什么是、什么是回文 的性质:先进后出或后进先出的特性,的实现也很简单,只需要一个一维数组和一个指向栈顶的变量top就可以了。我们通过变量top来对进行插入和删除操作。 回文:回文字符串就是...
  • 系列课程包含11个部分,本课为第3部分和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用...
  • 利用栈 转换进制 碰到 大于 10的进制 需要在进栈元素处做相应的处理 /*** // 数制 转换问题 所得商 入栈 计算完毕后 出栈 即为所得 InitStack ( &S) : 栈的初始化 Push ( &S, e) :进栈 Pop (&S ) : 出栈 GetTop...
  • 有趣的数据结构算法9——利用栈完成2进制到8进制的转换解题思路实现代码GITHUB下载连接 刚学习完栈的我想试试栈都可以干嘛,于是找到了一个小应用,利用栈完成2进制到8进制的转换。如果大家还不清楚什么是栈、如何...
  • python数据结构与算法 5的应用之圆括号平衡 主要关心代码的实现, /*平衡圆括号*/ function isBracketBalanced(str) { /* @str:圆括号字符串,比如 "()()" "(()()())" 平衡 "(()" 非平衡, 左括号...
  • 小猪的数据结构辅助教程——3.1 与队列中的顺序标签(空格分隔): 数据结构本节学习路线图与学习要点学习要点 1.与队列的介绍,栈顶,底,入栈,出栈的概念 2.熟悉顺序的特点以及存储结构 3.掌握...
  • 利用栈实现一个简易的计算器 实现了加减乘除运算(没有使用STL) 基本思想: 1.一个数据栈,一个符号栈 2.优先级判断 3.负号和减号的判别与处理 4.括号匹配 代码如下: #include&lt;iostream&gt; #...
  • (Stack),是一种特殊的后进先出线性表,其只能在一端进行插入(插入一般称为压栈、进栈或入栈)和删除(删除一般称为弹、退或出栈)操作,允许进行插入和删除操作的一端称为栈顶,另一端则称为底。,...
  • java实现,利用int类型存储操作数,完善了char类型范围太小的问题,利用递归,完善了括号嵌套使用的问题。 运行结果截图 代码实现: import java.util.Arrays; import java.util.Scanner; public class StackTest{ ...
  • 特性:后进先出(LILO)特殊线性表功能:将数据从一种序列改变为另一种序列2.顺序和顺序表数据成员相同,不同之处:顺序的入栈和出栈操作只允许对当前栈顶进行操作!顺序所有的的操作时间...
  • 编写一个程序,利用栈结构,将二进制数转换为十进制数,
  • 利用栈数据结构特点,将二进制转换为十进制数。 二进制数是计算机数据的存储形式,它是由一串0和1组成的,每个二进制数转换成相应的十进制数方法如下: (XnXn-1……X3X2X1)2 = X1*2^0+X2*2^1+…+Xn*2^(n-1) 一...
  • 利用两种不同的数据结构实现双端,即一个存储空间存放两个不同的 1.利用数组实现双端(两个相向生长) 2.利用双端队列deque实现双端(两个反向生长) 利用两种不同的数据结构实现双端,即一个...
  • 是一种重要的线性结构,通常称,和队列是限定插入和删除只能在表的“端点”进行的线性表。(后进先出) –的元素必须“后进先出”。 –的操作只能在这个线性表的表尾进行。 –注:对于来说,这个表尾...
  • 两种表达式 ...只需一个栈就可以把中缀转后缀,利用栈把表达式中的运算符次序从中序改为后序。栈中只存放运算符和左括号,由于后缀表达式中不存在括号,所以输出的时候将不输出括号。 算法 a...
1 2 3 4 5 ... 20
收藏数 158,365
精华内容 63,346
关键字:

利用栈的数据结构