精华内容
下载资源
问答
  • 顺序存储进出栈

    2021-02-05 21:53:14
    typedef struct { int data[10]; int top; }Stack; void InitStack(Stack &stack) { stack.top=0; } bool Push(Stack &stack,int e) { if (stack.top>=10) return false;...bool Pop(S
    typedef struct {
    	int data[10];
    	int top;
    }Stack;
    void InitStack(Stack &stack)
    {
    	stack.top=0;
    }
    bool Push(Stack &stack,int e)
    {
      if (stack.top>=10) return false;
      stack.data[stack.top++]=e;//相当于stack.top=e,top++;
      return true; 	
    }
    bool Pop(Stack &stack,int &e)
    {
     if (stack.top==0) return false;
     e=stack.data[--stack.top];//相当于e=数组[top-1],top=top-1;
     return true;
    }
    int main() {
    	Stack A;
    	Push(A,1);
    	Push(A,2);
    	Push(A,3);
    	Push(A,4);
    	int a;
    	cout<<A.top<<endl;
    	Pop(A,a);
    	cout<<A.top<<endl;
    	cout<<a;
    	return 0;
    }
    
    展开全文
  • 由于是一个线性表,即元素只能从栈顶进出栈,所以其存储结构也如同线性表,有顺序存储和链式存储之分 顺序存储表示 顺序存储结构简称为顺序栈,和线性表相类似,用一维数组来存储。 ...

    之前写的:https://mp.csdn.net/postedit/83661447(好多都是参考的这个)

     

    栈的表示

    由于栈是一个线性表,即元素只能从栈顶进出栈,所以其存储结构也如同线性表,有顺序存储和链式存储之分

     

    栈的顺序存储表示

    栈的顺序存储结构简称为顺序栈,和线性表相类似,用一维数组来存储栈。

    根据数组是否可以需要增大,顺序栈又可分为静态顺序栈和动态顺序栈。

     

    #define MaxSize  50   //定义栈中元素的最大个数 

    typedef struct{
        ElemType data[MaxSize];
        int top;        
    //和顺序表相比,这里的top其实和顺序表中的length是等价的 
    }SqStack;

    typedef struct STACK{
        USER_TYPE *stack;
        int maxRoom;  //这里的maxRoom可以用宏定义,也可以自己传入 
        int top;
    }STACK;

    这个是朱老师的图(栈为空时top的值为0)

     

    关于进栈、出栈时是先变栈顶指针还是后变的问题?

     

     

     

     

    //顺序栈的基本操作实现 
    
    #include<stdio.h>
    #include<malloc.h>
    
    typedef unsigned char  boolean;
    #define  TRUE    1
    #define  FALSE   0
    
    typedef int ElemType;
    
    #define MaxSize  50   //定义栈中元素的最大个数 
    
    typedef struct{
    	ElemType *data;
    	int maxSize;   //这里的maxSize可以用宏定义,也可以自己传入 
    	int top;    //栈顶指针
    	//如果用物理线性存储结构实现,则,栈顶和栈底指针实质上是数组下标。
    	//和顺序表相比,这里的top其实和顺序表中的length是等价的 
    }SqStack;
    
    
    boolean initStack(SqStack **stack);    //初始化 构造一个空栈 
    void destroyStack(SqStack **stack);    //销毁栈,栈不再存在 
    
    boolean isStackEmpty(SqStack *stack);  //判栈空
    //朱老师居然用的 boolean isStackEmpty(SqStack stack);  在下佩服 
    boolean isStackFull(SqStack *stack);   //判栈满 
    
    boolean push(SqStack *stack, ElemType x);    //入栈 
    //ElemType pop(SqStack *stack);  不用这种形式出栈
    boolean pop(SqStack *stack, ElemType *x);    //出栈,把取出的值存入x所指的空间 
    
    
    boolean getTop(SqStack *stack, ElemType *x);   //取栈顶元素 
    //朱老师用的是 boolean getTop(SqStack stack, ElemType *x);
    //为什么不用ElemType getTop(SqStack *stack),参见之前写的那个即可
    
    void showData(SqStack *stack);  //这个不是栈的基本要求,是自己为了检验程序加入的 
    
    
    void showData(SqStack *stack){
    	int i;
    	
    	for(i = 0; i < stack->top; i++){
    		printf("%d ", stack->data[i]);
    	} 
    	printf("\n");
    }
    
    //取栈顶元素 
    boolean getTop(SqStack *stack, ElemType *x){
    	if(isStackEmpty(stack)){
    		return FALSE;   //栈空 
    	} 
    	 
    	*x = stack->data[stack->top-1];
    	return TRUE; 	 
    } 
    
    
    
    //出栈 
    /*
    boolean pop(SqStack *stack, ElemType *x){
    	if(isStackEmpty(stack)){
    		return FALSE;   //栈空,如法出栈 
    	} 
    	
    	//*x = stack->data[--top];  //先top--,再出栈 
    	*x = stack->data[--stack->top];
    	
    	return TRUE; 
    } 
    */
    
    //这才是标准的pop,pop就是弹出一个元素,没有必要取弹出的元素,那个getTop函数干的事
    boolean pop(SqStack *stack){
    	if(isStackEmpty(stack)){
    		return FALSE;   //栈空,如法出栈 
    	} 
        stack->top--;
    }
    
    
    //入栈 
    boolean push(SqStack *stack, ElemType x){
    	if(isStackFull(stack)){
    		return FALSE;   //栈满,无法入栈 
    	} 
    	
    	//(*stack).data[top] = x;
    	//top++;
    	//stack->data[top++] = x;   //上面那两句的简化版 
    	stack->data[stack->top++] = x; 
    	
    	return TRUE; 	
    } 
    
    //判栈满 
    boolean isStackFull(SqStack *stack){
    	return stack->top == stack->maxSize;
    	//return (stack->top == stack->maxSize-1);  错误,这样子的话,还有一个位置 
    }
    
    //判栈空
    boolean isStackEmpty(SqStack *stack){
    	return stack->top == 0;
    } 
    
    //销毁栈,栈不再存在 
    void destroyStack(SqStack **stack){
    	if(*stack == NULL || (*stack)->data == NULL){
    		return;
    	}
    	//若前面那个成立(即*stack == 0),说明没有初始化,不再进行后面的运算(如果还要操作的话,就会造成非法内存访问)
    	//若后面那个成立,说明控制头中的data成员为空,没有指向,也就不用释放了 
    	
    	free((*stack)->data);
    	free(*stack); 
    	*stack = NULL;   //!!!让这个指针不再乱指 
    } 
    
    
    //初始化 构造一个空栈 
    boolean initStack(SqStack **stack){
    	if(*stack != NULL){
    		return FALSE;
    	}
    	
    	
    	*stack = (SqStack *)malloc(sizeof(SqStack));   //先申请一个控制头
    	(*stack)->maxSize = MaxSize;
    	(*stack)->top = 0; 
    	(*stack)->data = (ElemType *)malloc(sizeof(ElemType) * MaxSize);
    	
    	return TRUE;
    }
    
    void main(void){
    	SqStack *stack = NULL;
    	ElemType x;
    	
    	initStack(&stack);
    	
    	push(stack, 3);
    	push(stack, 2);
    	//push(stack, 1);
    	showData(stack);
    	
    	pop(stack, &x);
    	printf("pop出来的数为:%d\n", x);
    	showData(stack);
    	
    	printf("栈是否为空:%d\n", isStackEmpty(stack));
    	printf("栈是否为满:%d\n", isStackFull(stack));
    	
    	getTop(stack, &x);
    	printf("栈顶元素为:%d\n", x);
    	
    	destroyStack(&stack);
    } 
    
    
    

     

    展开全文
  • 顺序栈和链式

    2014-01-13 10:50:41
    链表和都属于线性表,只是是一种特殊的线性表,其“只能够从一端(栈顶)进出”,必须遵循“先进后出”的原则。下面,我们简要学习一下顺序栈和链式。 (1)顺序栈  与顺序存储的链表一样,顺序栈也是采用...

        前面已经介绍了“链表”,包括顺序链表和链式链表。链表和栈都属于线性表,只是栈是一种特殊的线性表,其“只能够从一端(栈顶)进出”,必须遵循“先进后出”的原则。下面,我们简要学习一下顺序栈和链式栈。

    (1)顺序栈

            与顺序存储的链表一样,顺序栈也是采用“数组”来存储。其数据结构如下:

    1. #define MAXSIZE 20  
    2. typedef int Elemtype;  
    3. typedef struct  
    4. {  
    5.      Elemtype data[MAXSIZE];  
    6.      int top;  
    7. }sqStack;  

            这里我们看出,栈和链表的数据结构几乎一模一样,只是里面的成员含义不同而已。在顺序链表里面,定义的是一个长度length,表示所能够存储的最大数据的个数,这个值是不能变化的;而顺序栈中定义的是栈顶元素的下标,这个值可以变化。

                      

           对于栈的操作来说,最重要的是“入栈”和“出栈”。这两个操作都必须遵循“FILO”的原则,其具体实现如下:

    1. //入栈  
    2. bool Push(sqStack *S, Elemtype e)  
    3. {  
    4.       if(S->top >= MAXSIZE - 1)  
    5.                 return false;  
    6.       S->top++;    //要细心,不能单独用top,而是引用结构体中的元素  
    7.       S->data[s->top] = e;  
    8.       return true;  
    9. }  
    10. //出栈  
    11. bool Pop(sqStack *S, Elemtype *e)  
    12. {  
    13.       if(S->top == 0)  
    14.              return false;  
    15.        *e = S->data[S->top];  
    16.        S->top--;  
    17.        return true;  
    18. }  

            从上面的知识中,可以知道,顺序栈的操作很方便,但其最大的不足在于,必须事先确定数据存储的最大空间。这里,我们扩展一下知识,下面介绍一下如何做到两个顺序栈共享数据空间。这个方法的基本思想为:数组空间有两个端点,两个栈有两个栈底;让一个栈的栈底位于数组的起始端(下标为0处),让另一个栈的栈底位于数组的末端(下标为N-1处);如果要向栈里面添加元素,那么使栈顶向数组中间移动即可。

             

    数据结构如下:

    1. typedef struct   
    2. {  
    3.       Elemtype data[MAXSIZE];  
    4.       int top1;  
    5.       int top2;  
    6. }sqDoubleStack;  

    入栈操作:

    1. bool Push(sqDoubleStack *S, Elemtype e, int stackNumber)  
    2. {  
    3.       if(S->top1+1 == S->top2)//特别注意,如果栈满了,top1和top2不是相等的,而是两者前后相邻,因此要加1  
    4.            return false;  
    5.       if(stackNumber == 1)  
    6.       {  
    7.               S->top1++;  
    8.               S->data[S->top1] = e;  
    9.               return true;  
    10.       }    
    11.       if(stackNumber == 2)  
    12.       {  
    13.               S->top2++;  
    14.               S->data[S->top2] = e;  
    15.               return true;  
    16.       }      
    17. }  

    (2)链式栈

            链式存储的栈就不会存在“栈满”的现象。因此,在进行入栈、出栈的时候,就不用再判断是否满栈了。在对链式栈进行操作时,始终要把握一点:首先看到的是整个栈,而不每一个结点;对于整个栈,只有两个指标——栈顶指针(top)和栈元素个数(count);这样,我们就能够通过栈顶指针(top)来取到栈顶的一个结点,从而获取其中的数据data,并可以创建指针,移动指针位置,遍历栈中的各个元素。也就是说,我们必须“从栈(top、count),再到结点(data、next)”。

                                                         

    其数据解结构可以定义为:

    1. typedef struct StackNode  
    2. {  
    3.      Elemtype data;  
    4.      struct StackNode * next;  
    5. }StackNode, *LinkStackPtr;  
    6. typedef struct LinkStack  
    7. {  
    8.      LinkStackPtr top;//这里top是一个stack结点类型的指针,指向Stack结点(栈顶)  
    9.      int count;  
    10. }LinkStack;  

    入栈操作:

    1. bool Push(LinkStack *S, Elemtype e)  
    2. {  
    3.       LinkStackPtr tmp = (LinkStackPtr)malloc(sizeof(StackNode));  
    4.       tmp->data = e;  
    5.       tmp->next = S->top;  
    6.       S->top = tmp;  
    7.       S->count++;  
    8.        return true;  
    9. }  

    出栈操作:

    1. bool Pop(LinkStack *S, Elemtype *e)  
    2. {  
    3.       LinkStack p;  
    4.       *e = S->top->data;  
    5.       p = S->top;  
    6.       S->top = S->top->next;  
    7.       free(p);  
    8.       S->count--:  
    9.       return true;  
    10. }  



    展开全文
  • ——顺序存储

    2019-10-06 11:07:20
    顺序存储还是很方便的,因为它只准栈顶进出元素,所以不存在线性表的插入和删除时需要移动元素的问题,但它有个很大的缺陷就是必须事先确定数组存储空间的大小,万一不够用了,就需要编程的手段扩展数组的容量,...

     栈顶指针top指向栈顶元素,初始化的时候栈为空top=-1,出栈和入栈不涉及任何循环所以时间复杂度为O(1)

    栈的顺序存储还是很方便的,因为它只准栈顶进出元素,所以不存在线性表的插入和删除时需要移动元素的问题,但它有个很大的缺陷就是必须事先确定数组存储空间的大小,万一不够用了,就需要编程的手段扩展数组的容量,非常麻烦。

    #include<iostream>
    using namespace std;
    #define TRUE 1
    #define FALSE 0
    #define MaxSize 20
    typedef int Elemtype;
    typedef int Status;
    typedef struct SqStack
    {
    	Elemtype data[MaxSize];
    	int top;
    }SqStack;
    //初始化顺序存储结构的栈
    Status InitStack(SqStack *S)
    {
    	S->top=-1;
    	return TRUE;
    }
    //获取栈顶元素
    Status GetTop(SqStack S,Elemtype *e)
    {
    	if(S.top==-1)
    		return FALSE;
    	*e=S.data[S.top];
    	return TRUE;
    }
    //将元素e进栈,栈顶指针top++
    Status Push(SqStack *S,Elemtype e)
    {
    	if(S->top==MaxSize-1)
    		return FALSE;
    	S->top++;
    	S->data[S->top]=e;
    	return TRUE;
    }
    //将栈顶元素e出栈,栈顶指针top--
    Status Pop(SqStack *S,Elemtype *e)
    {
    	if(S->top==-1)
    		return FALSE;
    	*e=S->data[S->top];
    	S->top--;
    	return TRUE;
    }
    int main()
    {
    	SqStack S;
    	Elemtype e=1;
        InitStack(&S);
        Push(&S,e);
    	Pop(&S,&e);
        cout<<e<<endl;
    	return 0;
    }

     

    展开全文
  • 一开始我是知道这个题目是模拟进出顺序的,但是我当时也只会判断这个出队序列是否可以由原序列通过来完成(我只会Yes和No的输出) 但这个题目偏偏给我整一个进出的全过程,人傻了 但是我作为一个数据结构学...
  • 最近工作中遇到了这样的需求: 我用fastjson序列有序map的时候,tojson方法会让这个map无序,tojsonstring虽然能保留map的结构,不过会让...如果传入的是true就代表保留数据结构的顺序 这时候我们可以吧要序列化的
  • nowcoder 进出栈

    2018-02-01 22:27:38
    n个数进出栈顺序有多少种?假设的容量无限大。 给定一个整数n,请返回所求的进出栈顺序个数。保证结果在int范围内。 测试样例: 1 返回:1 思路 卡特兰数。 代码 class Stack: def get_arrange(self,...
  • 【数据结构】顺序存储结构 C语言实现 (stack),是一种线性存储结构,它有以下几个特点: 中数据是按照&amp;quot;后进先出(LIFO, Last In First Out)&amp;quot;方式进出栈的。 向中添加/删除数据...
  • 顺序存储是很方便的,因为它只准栈顶进出元素,所以不存在线性表插入和删除时需要移动元素的问题。不过它有一一个很大的缺陷,就是必须事先确定数组存储空间大小,万一不够用了,就需要编程手段来扩展数组的容量...
  • 中的元素进出的规则为先入后出,即先进入栈的元素后出栈而后进入的元素先出栈。在对栈栈中的元素进行操作时只能够操作栈顶的元素。 中储存元素的三种状态: 当储存的元素超过了的储存空间则会发生中元素...
  • 进出

    2012-09-23 22:25:00
    【转】[原创] n个元素顺序入栈,出栈顺序有多少种? 数据结构课程 第一次遇到这个题目,还是一年前在新东方一次笔试中,那时还是一个填空题!我晕,我咋知道,好像课堂上没有见过,或许我学数据结构等课程时,...
  • 顺序栈与链式

    2019-07-13 16:28:26
    顺序栈(容量在限)、链式(可以无限容量)。 一般常用于,表达式解析,内存管理(函数的调用提供支持)。 顺序栈: #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define ...
  • 进出栈的方法数

    2018-06-17 01:35:37
    n个数进出栈顺序有多少种?假设的容量无限大。给定一个整数n,请返回所求的进出栈顺序个数。保证结果在int范围内。class Stack {public: int Cmn(int m,int n) { if(m==n||n==0) return 1; else return ...
  • (stack)又名堆栈,它是一种运算...从一个删除元素又称作出栈或退,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素一组不同元素进入中由于进站和出栈的时间不同可能会出现不同顺序,比如3个元素进...
  • 下面我就用两种不同的方式演示对于长度为n的数组进出栈的方式和: 1.递归法 public int catalen(int n){ if(n==1){ return 1; } return catalen(n-1)*2*(2*n-1)/(n+1); } 2.迭代法 public int catalen...
  • 顺序栈 和链栈

    2020-10-18 19:07:56
    由于底固定不变的,而栈顶随进出栈操作动态变化的,因此为了实现对的的操作,必须记住栈顶的当前位置。 顺序栈优缺点: 优点:简单、存储密度高。 确定:即使的长度很长,也还是可能发生上溢。当的容量不...
  • 例如中有三个元素,近顺序是a1、a2、a3,当需要出栈时顺序为a3,a2,a1,所以又称“后进先出”或“先进后出”的线性表,简称“LIFO表”或“FILO表”。 现在使用Python实现进出,直接上代码吧: #模拟...
  • 一、相关定义(顺序存储结构(最常用)) 官方定义:是一个后进先出的线性表,它要求只在表尾进行删除插入操作(特殊线性表,只能在表尾操作) 栈顶:表尾 底:表头 的插入操作:叫做进栈(入栈,压栈)...
  • 火车调度 进出栈算法

    2020-04-06 18:19:54
    火车调度 进出栈算法 假设某火车站采用后进先出的模式。现有n列火车,调度人员给出火车进站的序列,并给出火车出站的序列,判断这个调度要求能否实现,如果能实现写出火车进站、出站的操作序列。 输入:第一行为一...
  • 进出栈序列问题

    2018-08-14 17:13:00
    有n列火车按1到n的顺序从东方左转进站,这个车站是南北方向的,它虽然无限长,只可惜是一个死胡同,而且站台只有一条股道,火车只能倒着从西方出去,而且每列火车必须进站,先进后出。 (某生:不就是个吗?每次...
  • 通过交换字母顺序。给定两个字符串,要求所有的进栈和出栈序列(i表示进栈,o表示出栈),使得字符串2在求得的进出栈序列的操作下,变成字符串1。输出结果需满足字典
  • 顺序栈的原理和使用

    2021-04-10 14:58:35
    进出的一端称为栈顶(top),另一端称为底(base)。可以用顺序存储,也可以用链式存储。 base 指向底,top 指向栈顶。 数据结构的定义 //结构体的定义 typedef struct _SaStack { ElemType* base; //...
  • 火车入站出站利用混洗实现,火车有若干节,在一个车站中转,先入则后出,判断某一个顺序能否实现
  • 数据结构之线性结构--- 顺序储存

    千次阅读 2016-10-08 00:51:00
    中的元素进出的规则为先入后出,即先进入栈的元素后出栈而后进入的元素先出栈。在对栈栈中的元素进行操作时只能够操作栈顶的元素。中储存元素的三种状态: 当储存的元素超过了的储存空间则会发生中元素的...
  • 和队列分别的顺序结构和链式结构 和队列 和队列本身作为特殊的线性表,要记住...进出顺序是在逻辑层面的,只要理解就行,难得是如何用指针来表示这种特点,于是我就此方面进行个总结。 顺序...
  • 解法:直接模拟就好。 //另外我年轻时候做的那题数据范围比较小,原理也不一样。 //对于序列中的任何一个数其后面所有比它小的数应该是倒序的,因此对于任意三个数a,b,c(按顺序),若b<a c<a 则有b>c ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 412
精华内容 164
关键字:

栈进出顺序