精华内容
下载资源
问答
  • 栈栈是一个「线性」的数据结构。最重要的特征是「只允许从一端操作数据」。就像一叠书,或者盘子,每次只能从最上边拿,往最上边放。遵循「先进后出」的...特殊情况下,当栈满的时候,再添加一个元素时,需要...

    2f5388810928937023f1e6985d4300bf.png

    栈是一个「线性」的数据结构。栈最重要的特征是「只允许从一端操作数据」。栈就像一叠书,或者盘子,每次只能从最上边拿,往最上边放。

    栈遵循「先进后出」的原则。栈只能从一端操作数据,这一端被称为「栈顶」,另一端被称为「栈底」。栈对数据的操作只有两种,「入栈和出栈」

    看到这里我们就能知道,由于入栈和出栈都在栈顶操作,所以插入或删除一个元素的复杂度为O(1)。

    特殊情况下,当栈满的时候,再添加一个元素时,需要重新分配内存且移动所有的数据,复杂度为O(n)。

    实现一个栈有很多方式,这里通过使用数组实现栈,代码实现:

    class Stack{
      constructor{
        this.stack = []
      }
    
      // 入栈
      push(item) {
        this.stack.push(item)
      }
    
      // 出栈
      pop() {
        this.stack.pop()
      }
    
      // 获取栈长度
      getCount() {
        return this.stack.length
      }
    
      // 查看栈顶元素
      peek() {
        return this.stack[this.getCount() - 1]
      }
    
      // 判断是否为空
      isEmpty() {
        return this.getCount === 0
      }
    }
    

    栈的示意图:

    fad89c00b4518389ccdf9918bcaea472.png

    队列

    队列也是一个线性的存储结构,特点是「只能在一端添加数据,在另一端删除数据」,遵循「先进先出」的原则。

    队列「插入数据的一端叫做队尾」,插入数据的操作叫「入队」「删除数据的一端叫做队头」,删除数据的操作叫做「出队」

    队列的时间复杂度和栈一样分是否已满,当队列未满时,入队复杂度是O(1),出队移除一个数据,剩下的数据前移,所以时间复杂度是O(n);当队列满了之后,需要扩容且移动数据,时间复杂度为O(n)。

    队列在生活中的相似场景为,车站的进出口,只能在进站口进站,出站口出站。队列常见的使用场景是作消息队列等。

    我们还是用数组来实现一个单链队列,代码实现如下:

    class Queue{
      constructor() {
        this.queue = []
      }
      
      // 入队
      enQueue(item) {
        return this.queue.push(item)
      }
        
      // 出队
      deQueue() {
        return this.queue.shift()
      }
        
      // 获取队头
      getHeader() {
        return this.queue[0]
      }
        
      // 获取队列长度
      getlength() {
        return this.queue.length()
      }
        
      // 判断是否为空
      isEmpty() {
        return this.getlength() === 0
      }
    }
    

    为了解决单链队列在出队操作时的复杂度是O(n),引入循环队列,将队列的出队操作复杂度降低到O(1)。

    class SqQueue{
      constructor(length){
        this.queue = new Array(length + 1)
        this.first = 0
        this.last = 0
        this.size = 0
      }
        
      // 判断是否为空
      isEmpty() {
        return this.first === this.last
      }
      
      // 扩容
      resize(length) {
        let q = new Array(length)
        for (let i = 0; i < length; i++) {
          q[i] = this.queue[(i + this.first) % this.queue.length]
        }
        this.queue = q
        this.first = 0
        this.last = this.size
      }
        
      // 入队
      enQueue(item) {
        // 判断是否需要扩容, 如果需要,扩容的原来的二倍
        if (this.first === (this.last + 1) % this.queue.length) {
          this.resize(this.getLength() * 2 + 1)
        }
        this.queue[this.last] = item
        this.size++
        this.last = (this.last + 1) % this.queue.length
      }
        
      // 出队
      deQueue() {
        if (this.isEmpty()) {
          throw Eorror('Queue is Empty')
        }
        let r = this.queue[this.first]
        this.queue[this.first] = null
        this.first = (this.first + 1) % this.queue.length
        this.size--
        // 节省空间
        if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
          this.resize(this.getLength() / 2)
        }
        return r
      }
        
      // 获取队头
      getHeader() {
        if (this.inEmpty()) {
          throw Error('Queue is empty')
        }
        return this.queue[this.first]
      }
        
      // 获取队列的长度
      getLength() {
        return this.queue.length - 1
      }
    }
    

    创建一个循环队列并操作:

    e50445ed92e4652409afd1f2bc9ba2d3.png

    对比

    82fca11e8527de6bc65a292eb71d0632.png

    对比:

    • 栈遵循先进后出的规则;队列遵循先进先出的规则。
    • 插入数据和删除数据都可以实现常数级的时间复杂度。
    • 两种数据结构都可以在元素满了的时候扩容。

    栈和队列相关的面试题

    由于篇幅的问题,面试题的思路和代码还是留给以后的文章。

    跟栈相关的面试题:

    • 有效的括号,一串字符串中的所有括号(){}[],都能正确闭合。
    • 用两个栈实现队列。
    • 实现一个栈,要求入栈出栈、返回最小值,且时间复杂度为O(1)。
    • 一个数组实现两个栈。

    跟队列相关的面试题:

    • 用两个队列实现栈。
    • 二叉树的广度优先遍历。
    • ...
    展开全文
  • 栈与队列--判断栈/队列空/

    千次阅读 2016-06-28 10:24:15
    数组栈 ...完成int IsFull(Stack S)函数,该函数判断栈是否,如果返回1,否则返回0。typedef int ElemType; struct StackRecord; typedef struct StackRecord *Stack; struct StackRecord {

    数组栈
    完成int IsEmpty(Stack S)函数,该函数判断栈是否已空,如果空返回1,否则返回0。
    完成int IsFull(Stack S)函数,该函数判断栈是否已满,如果满返回1,否则返回0。

    typedef int ElemType;
    struct StackRecord;
    typedef struct StackRecord *Stack;
    struct StackRecord
    {
        int Capacity; //栈容量
        int Top; //栈顶,初始为1
        ElemType *Array;
    };
    
    int IsEmpty(Stack S)
    {
        if(S‐>Top==‐1)
        {
            return 1;
        } 
        else
        {
            return 0;
        }
    }
    int IsFull(Stack S)
    {
        if(S‐>Top==S‐>Capacity‐1)
        {
            return 1;
        } 
        else
        {
            return 0;
        }
    }

    链栈
    完成int IsEmpty(Stack S);函数,该函数判断栈S是否为空,空栈返回1,否则返回0,已知S是带头结点的链栈。

    typedef int ElemType;
    struct Node;
    typedef struct Node * PtrToNode;
    typedef PtrToNode Stack;
    struct Node
    {
        ElemType data;
        PtrToNode next;
    };
    
    int IsEmpty(Stack S)
    {
        return S‐>next==NULL?1:0;
    }

    数组队列
    完成int IsEmpty(Queue Q);函数,该函数判断队列Q是否已空,如果已空返回1,否则返回0,其中Q是基于数组的非循环队列。
    完成int IsFull(Queue Q)函数,该函数判断队列Q是否已满,如果已满返回1,否则返回0,其中Q是基于数组的非循环队列。

    typedef int ElemType;
    struct QueueRecord;
    typedef struct QueueRecord * Queue;
    struct QueueRecord
    {
        int Capacity; //队列总容量
        int Front; //队首 初始值为0
        int Rear; //队尾,初始值为1
        int Size; //队列中数据数,初始值为0
        ElemType *Array;
    };
    
    int IsEmpty(Queue Q)
    {
        return Q‐>Size==0;
    }
    int IsFull(Queue Q)
    {
        return Q‐>Rear==Q‐>Capacity‐1?1:0;
    }

    链队列
    完成int IsEmpty(Queue q)函数,该函数判定基于链表的队列q是否为空,空队列返回1,非空队列返回0,其中q是不带头节点的链表队列。

    typedef int ElemType;
    struct node;
    typedef struct node Node;
    struct queue;
    typedef struct queue * Queue;
    struct node
    {
        ElemType data;
        Node * next;
    };
    struct queue
    {
        Node * front; //队首
        Node * rear; //队尾
        int size; //队列中数据数int IsEmpty(Queue q)
    {
        return q‐>size==0?1:0;
    }
    展开全文
  • 顺序栈,遵循先进后出后进先出原则。我在写的时候,宏定义的 firstsize 为创建一个栈时这个栈的初始大小,这里为100。...栈是否为空,print函数用来出栈。 //以下为全部代码 #include "stdio.h" #include "mall...

    顺序栈,遵循先进后出后进先出原则。我在写的时候,宏定义的
    firstsize 为创建一个栈时这个栈的初始大小,这里为100。addsize
    为当栈满时,再想入栈的话每次栈大小的增量,这里用10来代替。
    create函数为创建栈函数。push为入栈函数。empty函数用来判断
    栈是否为空,print函数用来出栈。
    //以下为全部代码

    #include "stdio.h"
    #include "malloc.h"
    #define firstsize 100
    #define addsize 10
    typedef struct{
     int *base;
     int *top;
     int size;
    }Sq;
    
    void create(Sq &s)
    {
     s.base=(int*)malloc(firstsize*sizeof(int));
     if(s.base)printf("create OK!\n");
     s.top=s.base;
     s.size=firstsize;
    }
    
    void push(Sq &s,int e)
    {
     if(s.top-s.base>=s.size)
     {
     s.base=(int*)realloc(s.base,(s.size+addsize)*sizeof(int));
     printf("栈内空间分配成功\n");
     }
     *s.top=e;
     s.top++;
     printf("元素[%d]已入栈!\n",e);
    }
    
    void print(Sq &s)
    {
     if(empty(s))printf("抱歉,栈已满,无法出栈\n");
     else
     {
       s.top--;
       printf("出栈:[%d]\n",*s.top);
      }
    }
    
    int empty(Sq &s)
    {
     if(s.top==s.base||s.top<s.base)
     { printf("栈空\n");
     return 1;}
     else {printf("栈未空\n");
     return 0;}
    }
    
    void main()
    {
    int i; Sq s;
    do
    {
    printf("\n----------------\n1-");
    printf("创建一个栈\n2-判断栈是否为空\n3-入栈\n4-出栈\n0-退出");
    printf("\n----------------\n\n");
    scanf("%d",&i);
    switch(i)
    {
     case 1:create(s);break;
     case 2:empty(s);break;
     case 3:
     {
     int e;
     printf("输入入栈元素:\n");
     scanf("%d",&e);
     push(s,e);
     }break;
     case 4:print(s);break;
     case 0:break;
     default:
     {printf("输入错误,请重新输入\n");
     }continue;
     }
     }while(i!=0);
     printf("程序已退出\n");
    }
    
    
    

    运行结果:sxz

    展开全文
  • 初学

    2017-12-24 11:00:46
    #include using namespace std; class stack { public: stack(int size);//分配内存空间 ~stack(); //回收栈的内存空间 bool stackempty(); //判断栈是否为空 空则返回true 非空...//判断栈是否为满 满则返回true 不满f
    #include<iostream>
    using namespace std;
    class stack
    {
    public:
    stack(int size);//分配内存空间
    ~stack();       //回收栈的内存空间
    bool stackempty(); //判断栈是否为空  空则返回true 非空false
    bool stackfull();//判断栈是否为满   满则返回true 不满flase
    void clearstack();//清空栈
    int stacklength();//已有元素的个数
    bool push(int elem);//入栈
    bool pop(int &elem);//出栈
    void stackper();//遍历栈
    private:
    int *buffer;//栈空间指针
    int msize;//栈容量
    int top;//栈顶/栈中的元素
    };
    stack::stack(int size)//构造函数
    {
    msize=size;
    buffer=new int[msize];
    top=0;
    }


    stack::~stack()//
    {
    delete[]buffer;
    }


    bool stack::stackempty()
    {
    if(0==top)
    {
    return true;
    }
    return false;
    }


    bool stack::stackfull()
    {
    if(top==msize)
    {
    return true;
    }
    return false;
    }


    void stack::clearstack()
    {
    top=0;
    }


    int stack::stacklength()
    {
    return top;

    }


    bool stack::push(int elem)
    {
    if(stackfull())
    {
    return false;
    }
    buffer[top]=elem;
    top++;
    return true;
    }


    bool stack::pop(int &elem)
    {
    if(stackempty())
    {
    return false;
    }
    top--;
    elem=buffer[top];
    return true;
    }


    void stack::stackper()
    {

    for(int i=0;i<top;i++)
    {
    cout<<buffer[i]<<" ";
    }

    }


    int main(void)
    {

    int a,b;
    cin>>a;
    stack *p=new stack(a);
    while(a--)
    {
    cin>>b;
    p->push(b);
    }
    p->stackper();

    }
    展开全文
  • 1--顺序

    2016-07-27 11:53:58
    栈是操作受限的线性表,只允许在栈顶(top)插入删除,不可以在栈底(Bottom)操作,所以是按照后进先出(LIFO)的机制组织数据的,主要的操作有push和pop ...push时,应先判断栈是否为满,若满,则会出现上溢(o
  • 如何判断栈溢出及解决方式

    千次阅读 2019-11-10 00:37:16
    怎么判断栈溢出,栈溢出是否超过整形范围?怎么处理 判断:1、用一个变量记录栈大小 2、重新设置堆栈指针,指向新的堆栈,并设置堆栈两端页面保护页面,一旦堆栈溢出,就会产生保护异常 解决的方法: 1、...
  • 顺序

    2018-05-05 21:48:42
    顺序栈示意图: 顺序栈的特点:先进后出,栈顶进栈顶出。 1. 顺序栈的创建 public Stack(){ this(10); ... public Stack(int size){ this.elem=new int[size];...```2. 判断栈是否为满 ...
  • 的笔记(1)

    2014-11-17 19:51:00
    栈的基本操作有:进栈(栈顶插入),出栈(删除栈顶),建立栈(初始化栈),判断栈是否为满或空,取栈顶元素等运算。 1.InitStrack(S) 初始化栈为空 2.ClearStack(S)把栈置为空 3.IsEmpty(S)判断栈是否为 空...
  • 用Java写一个简单的栈,包括压栈、弹栈、查看栈容量、打印栈内元素及个数、打印栈顶元素等功能 ... // 判断栈是否为满 boolean isFull(); //入栈 void push(Object obj); //出栈 删除并返回栈顶元素 Object ...
  • 和队列

    2020-06-21 01:29:04
    栈 1、栈是一种先进后出的结构 2、栈只允许在一端进行插入和删除操作 3.自己实现栈的基本操作,如下: public class myStackByArrayList { //不考虑扩容 ... //判断栈是否为满 if(size == array.length)
  • 数据结构 与队列

    2019-12-31 16:22:56
    栈与队列 栈 1.定义:仅在表尾进行插入与删除操作的线性表 2.原理:允许插入与删除的一端称为栈顶,另一端称为栈底,不含任何元素称为空栈;属于后入先出结构(Last in First out) ...判断栈是否为满 删除并返...
  • 对于顺序栈,入栈时,首先判断栈是否为满,栈满的条件为:p->top= =MAXNUM-1,栈满时,不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢。 出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作,否则...
  • 【数据结构】

    2017-03-27 08:19:14
    【1】栈的概念栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈), 允许进行操作的一端称为“栈顶”,另一固定端称为“栈底”,当栈中 ...判断栈是否为满 入栈(压栈) 出栈(弹栈) 打印栈的数据 【4】链式栈
  • 顺序的创建与使用

    2019-08-24 10:37:51
    其次是实现各项业务逻辑的分函数:创建栈、销毁栈、判断栈是否为空、判断栈是否为满、入栈、出栈、查看栈顶元素。 创建栈: 使用malloc申请栈空间,初始化栈的长度和栈顶指针。 销毁栈: 当程序运行结束时,需要...
  • 数据结构1-

    2014-06-29 09:01:00
     栈有,判断栈是否为空,判断栈是否为满,出栈,入栈,取栈顶元素,这5个功能,用类实现,就是5个方法,5个成员函数。  为方便起见,栈能容纳元素的最大值设定为固定值。元素为int型。用C++实现如下:   1 ...
  • public interface StackInterface&lt;E&gt; { ...//判断栈是否为满 void clearStack();//清空栈 int stackLength();//已有元素的个数 Object pop() throws Exception;//元素出栈,...
  • 本篇博客遇上篇博客不同,不需要家条件判断栈是否为满,为了提高效率我们可以使用链表的前插法来表示栈,整体使用方法和单链表类似 /*数据结构与算法之 栈的链式存储 实验目的: (1) 实现栈的存储结构设计; (2) 实现栈...
  • 2017-03-15 14:04:00
    一.栈的顺序存储结构 1.操作要点: ... (2)出栈和读栈顶元素操作,先判断栈是否为空,为空时不能操作,否则产生错误,通常栈空时常作为一种控制转移条件。  (3)取栈顶元素与出栈的不同之处是出...
  • 栈 1.概念 栈:一种特殊的线性表,其只允许在固定的一端...进入栈之前,首先要先判断栈是否为满,只有栈没有满的时候才能将新元素继续入栈; 因为用的是顺序表的形式,只要在数组的最后面加入新进来的元素就行; 然
  • 栈和队列 栈 1:定义:仅能在表尾进行插入或者删除的线性表, 表头为栈底 2:同s表示进栈,x代表出栈 。若进栈顺序为1,2,3,4,为了得到出栈顺序1,3,4,2 ...4:在实现顺序栈操作应该判断栈是否为满,出栈前应该判断是...
  • 1.共享:方法:用数组实现,定义一个结构体,结构体中包含2个,其中一个底数组中下标0处,而两外一个底为数组的最大值处。当两个的栈顶相遇时,即栈满。2.最小栈:即:每次取栈顶元素取出来当前...
  • 实验: 编写一个程序实现顺序栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能: ...对于顺序栈,入栈时,首先判断栈是否为满,栈满的条件为:p-&gt;top= =MAXNUM-1,栈满时,不能入栈; 否...
  • 数据结构 主讲人章万静 未满 已满 开始 结束 栈是否已满 求栈顶元素下标top 定义变量 不能进栈 进栈操作 顺序栈进栈 顺序栈进栈 顺序栈进栈操作之前必须判断堆栈是否为满 栈为满则不能进栈栈非满则可以进栈 谢谢观看
  • 数据结构--

    2018-05-25 11:43:00
    创建栈:初始化栈空间,给定一个栈的容量,即栈顶删除栈:回收栈空间内存判断栈是否为空:根据栈中已有元素的个数,判断栈是否为空,为空返回true,不为空返回false判断栈是否已:根据 栈的容量 和 当...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 258
精华内容 103
关键字:

判断栈是否为满