入栈退栈的计算？

一、入栈退栈的计算？

栈是一种数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。 栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。 栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈(PUSH)，删除则称为退栈(POP)。 栈也称为后进先出表(LIFO表)。

例如:有一个数列(23，45，3，7，3，945) 我们先对其进行进栈操作，则进栈顺序为:23，45，3，7，3，945 我们在对其进行出栈操作，则出栈顺序为:945，3，7，3，45，23 进栈出栈就像只有一个口的长筒，先把数据一个个放入筒内，而拿出的时候只有先拿走上边的，才能拿下边的。

二、栈的入栈顺序和出栈顺序的各种可能？

举一个例子吧。

三、顺序存储的栈怎样判别栈空和栈满？

【解答】（1）顺序栈（top用来存放栈顶元素的下标）

判断栈S空：如果S->top==-1表示栈空。

判断栈S满：如果S->top==Stack_Size-1表示栈满。(2)链栈（top为栈顶指针，指向当前栈顶元素前面的头结点）判断栈空：如果top->next==NULL表示栈空。

判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。

四、栈顶和栈底的区别？

区别：使用效果不同，位置不同。

五、进程栈与线程栈的关系？

内核栈、用户栈

32位Linux系统上，进程的地址空间为4G，包括1G的内核地址空间-----内核栈，和3G的用户地址空间-----用户栈。

内核栈，是各个进程在刚开始建立的时候通过内存映射共享的，但是每个进程拥有独立的4G的虚拟内存空间从这一点看又是独立的，互不干扰的（只是刚开始大家都是映射的同一份内存拷贝）

用户栈就是大家所熟悉的内存四区，包括：代码区、全局数据区、堆区、栈区

用户栈中的堆区、栈区即为进程堆、进程栈

进程堆、进程栈与线程栈

1.线程栈的空间开辟在所属进程的堆区与共享内存区之间，线程与其所属的进程共享进程的用户空间，所以线程栈之间可以互访。线程栈的起始地址和大小存放在pthread_attr_t 中，栈的大小并不是用来判断栈是否越界，而是用来初始化避免栈溢出的缓冲区的大小（或者说安全间隙的大小）

2.进程初始化的时候，系统会在进程的地址空间中创建一个堆，叫进程默认堆。进程中所有的线程共用这一个堆。当然，可以增加1个或几个堆，给不同的线程共同使用或单独使用。----一个进程可以多个堆

3、创建线程的时候，系统会在进程的地址空间中分配1块内存给线程栈，通常是1MB或4MB或8MB。线程栈是独立的，但是还是可以互访，因为线程共享内存空间

4.堆的分配：从操作系统角度来看，进程分配内存有两种方式，分别由两个系统调用完成：brk（）和mmap（），glibc中malloc封装了

5.线程栈位置-内存分布测试代码

[cpp] view plain copy

#include <pthread.h>

#include <stdio.h>

#include <unistd.h>

#include <string.h>

#include <errno.h>

#include <malloc.h>

#include <sys/syscall.h>

void* func(void* arg)

{

long int tid = (long int)syscall(SYS_gettid);

printf("The ID of this thread is: %ld\n", tid );

static int a=10;

int b=11;

int* c=(int *)malloc(sizeof(int));

printf("in thread id:%u a:%p b:%p c:%p\n",tid,&a,&b,c);

printf("leave thread id:%ld\n",tid);

sleep(20);

free((void *)c);

}

void main()

{

pthread_t th1,th2;

printf("pid=%u\n",(int)getpid());

func(NULL);

int ret=pthread_create(&th1,NULL,func,NULL);

if(ret!=0)

{

printf("thread1[%d]:%s\n",th1,strerror(errno));

}

ret=pthread_create(&th2,NULL,func,NULL);

if(ret!=0)

{

printf("thread2[%d]:%s\n",th2,strerror(errno));

}

pthread_join(th1,NULL);

pthread_join(th2,NULL);

}

输出：

[le@localhost threadStack]$ ./threadStack_main pid=16433

The ID of this thread is: 16433

in thread id:16433 a:0x60107c b:0x7fffc89ce7ac c:0x1b54010

leave thread id:16433

The ID of this thread is: 16461

The ID of this thread is: 16460

in thread id:16461 a:0x60107c b:0x7f6abb096efc c:0x7f6ab40008c0

leave thread id:16461

in thread id:16460 a:0x60107c b:0x7f6abb897efc c:0x7f6aac0008c0

leave thread id:16460

主线程调用func后

[le@localhost threadStack]$ sudo cat /proc/16433/maps

00400000-00401000 r-xp 00000000 fd:02 11666 /home/le/code/threadStack/threadStack_main

00600000-00601000 r--p 00000000 fd:02 11666 /home/le/code/threadStack/threadStack_main

00601000-00602000 rw-p 00001000 fd:02 11666 /home/le/code/threadStack/threadStack_main

01b54000-01b75000 rw-p 00000000 00:00 0 [heap]

7f6abb899000-7f6abba4f000 r-xp 00000000 fd:00 100678959 /usr/lib64/libc-2.17.so

7f6abba4f000-7f6abbc4f000 ---p 001b6000 fd:00 100678959 /usr/lib64/libc-2.17.so

7f6abbc4f000-7f6abbc53000 r--p 001b6000 fd:00 100678959 /usr/lib64/libc-2.17.so

7f6abbc53000-7f6abbc55000 rw-p 001ba000 fd:00 100678959 /usr/lib64/libc-2.17.so

7f6abbc55000-7f6abbc5a000 rw-p 00000000 00:00 0

7f6abbc5a000-7f6abbc70000 r-xp 00000000 fd:00 105796566 /usr/lib64/libpthread-2.17.so

7f6abbc70000-7f6abbe70000 ---p 00016000 fd:00 105796566 /usr/lib64/libpthread-2.17.so

7f6abbe70000-7f6abbe71000 r--p 00016000 fd:00 105796566 /usr/lib64/libpthread-2.17.so

7f6abbe71000-7f6abbe72000 rw-p 00017000 fd:00 105796566 /usr/lib64/libpthread-2.17.so

7f6abbe72000-7f6abbe76000 rw-p 00000000 00:00 0

7f6abbe76000-7f6abbe97000 r-xp 00000000 fd:00 105796545 /usr/lib64/ld-2.17.so

7f6abc073000-7f6abc076000 rw-p 00000000 00:00 0

7f6abc095000-7f6abc097000 rw-p 00000000 00:00 0

7f6abc097000-7f6abc098000 r--p 00021000 fd:00 105796545 /usr/lib64/ld-2.17.so

7f6abc098000-7f6abc099000 rw-p 00022000 fd:00 105796545 /usr/lib64/ld-2.17.so

7f6abc099000-7f6abc09a000 rw-p 00000000 00:00 0

7fffc89b0000-7fffc89d1000 rw-p 00000000 00:00 0 [stack]

7fffc89fe000-7fffc8a00000 r-xp 00000000 00:00 0 [vdso]

ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]

两个子线程启动后

[le@localhost threadStack]$ sudo cat /proc/16433/maps

00400000-00401000 r-xp 00000000 fd:02 11666 /home/le/code/threadStack/threadStack_main

00600000-00601000 r--p 00000000 fd:02 11666 /home/le/code/threadStack/threadStack_main

00601000-00602000 rw-p 00001000 fd:02 11666 /home/le/code/threadStack/threadStack_main

01b54000-01b75000 rw-p 00000000 00:00 0 [heap]

7f6aac000000-7f6aac021000 rw-p 00000000 00:00 0

7f6aac021000-7f6ab0000000 ---p 00000000 00:00 0

7f6ab4000000-7f6ab4021000 rw-p 00000000 00:00 0

7f6ab4021000-7f6ab8000000 ---p 00000000 00:00 0

7f6aba897000-7f6aba898000 ---p 00000000 00:00 0

7f6aba898000-7f6abb098000 rw-p 00000000 00:00 0 [stack:16461]

7f6abb098000-7f6abb099000 ---p 00000000 00:00 0

7f6abb099000-7f6abb899000 rw-p 00000000 00:00 0 [stack:16460]

7f6abb899000-7f6abba4f000 r-xp 00000000 fd:00 100678959 /usr/lib64/libc-2.17.so

7f6abba4f000-7f6abbc4f000 ---p 001b6000 fd:00 100678959 /usr/lib64/libc-2.17.so

7f6abbc4f000-7f6abbc53000 r--p 001b6000 fd:00 100678959 /usr/lib64/libc-2.17.so

7f6abbc53000-7f6abbc55000 rw-p 001ba000 fd:00 100678959 /usr/lib64/libc-2.17.so

7f6abbc55000-7f6abbc5a000 rw-p 00000000 00:00 0

7f6abbc5a000-7f6abbc70000 r-xp 00000000 fd:00 105796566 /usr/lib64/libpthread-2.17.so

7f6abbc70000-7f6abbe70000 ---p 00016000 fd:00 105796566 /usr/lib64/libpthread-2.17.so

7f6abbe70000-7f6abbe71000 r--p 00016000 fd:00 105796566 /usr/lib64/libpthread-2.17.so

7f6abbe71000-7f

六、硬件栈和模拟栈的区别？

硬件堆栈：是通过寄存器SPH，SPL做为索引指针的地址，是调用了CALL，RCALL等函数调用指令后硬件自动填充的堆栈！

　　软件堆栈：是编译器为了处理一些参数传递而做的堆栈，会由编译器自动产生和处理，可以通过相应的编译选项对其进行编辑。

七、单栈和双栈的区别？

1.双栈思路。因题目只对时间复杂度有要求，而对空间复杂度无要求。因此我们可以创建两个栈，一个栈用于存储实际数据，另一个栈用于存储最小元素，getMin()方法只需直接返回存储最小元素栈的最顶层元素即可。

双栈思路时间复杂度为O(1)，空间复杂度为O(n)。

2.单栈思路。假设该题对时间复杂度和空间复杂度都要求为O(1)时，我们就可使用该方法实现。单栈顾名思义就是只创建一个栈，我们进行入栈操作时可push()两次，第一次为实际数据，第二次为最小元素(即每个实际数据后面均跟着最小元素)，getMin()方法只需直接返回栈顶元素即可。

八、带链的栈和普通栈区别？

1. 存储结构不同：带链的栈使用链表来实现存储，每个节点包含数据元素和指向下一个节点的指针；而普通栈使用数组或者顺序表等线性结构来存储元素。

2. 长度限制不同：普通栈的长度受到数组或顺序表大小的限制，而带链的栈理论上只受计算机内存的限制。

3. 插入和删除操作不同：在带链的栈中，插入和删除元素时只需要修改指针的指向，而在普通栈中，插入和删除元素时需要移动元素或者重新分配内存空间。

4. 实现方式不同：由于存储结构不同，带链的栈和普通栈的实现方式也不同，需要选择不同的算法和数据结构来解决复杂度和效率的问题。

九、本地方法栈和栈的区别？

本地方法栈和虚拟机栈所发挥的作用是非常相似的,它们之间的区别不过是虚拟机栈是非虚拟机执行Java方法(也就是字节码)服务,而本地方法栈则是为虚拟机执行Native方法服务的。在虚拟机规范中对本地方法栈中方法使用的语言、使用方式与数据结构并没有强制

十、栈的由来？

由来：

“栈”，初见于楚系简帛时代，木表意，篆书像树木之形，表示木棚；戔(戋jiān)表声，戈有伤义，表示搭盖棚子必对木料锯削加工而后用钉子钉牢。声旁简化。后来又在《说文》中发现，“栈”字简体版的楷书从《说文》演变而来。

详细释义

拼音

zhàn

名词

牲口棚

shed

皂栈

四墙其社，覆上栈下，示不得通。——《汉书》

古代用竹木条横排编成车箱的轻便车子

bamboo or wood cart

栈车、栈轸

宾奠币于栈左。——《仪礼·既夕礼》

栈道

plank road built along the face of a cliff

栈山、栈山航海

复从峡度栈以上。——《徐霞客游记·游黄山记》

留宿客商或储存货物的房屋

warehouse;storehouse

栈使、栈伙

姓

动词

（在栈内） 加料精养 

fee

栈羊、栈鹿