题目

为了充分利用空间，顺序栈s0、s1共享一个存储区elem[0, ... , maxSize-1]。试着设计一个共享栈s0、s1以及有关入栈和出栈操作的算法，假设栈中元素是int型。

分析

算法思想：

1)顺序栈栈底固定不变，因此将栈底设在存储区的两端，即s0栈底设在0处,sI栈底设在maxSize-1处，栈顶在0~maxSize-1的范围内变动。当两栈栈顶相遇时为栈满，这样可以尽可能地利用空间。

2) sO的栈项为top0，s0 入栈操作为: top0 先自增1,然后存入元素:出栈操作为:先取出栈项元素，top0再自减1. sI的栈顶为top1, s1入栈操作为: top1 先自减1，然后存入元素:出栈操作为:先取出栈顶元素，topl 再自增1.

图解：



代码

#include<stdio.h>
#include<stdlib.h>

#define maxSize 20

/* 定义共享栈结构体 */
typedef struct {
	int elem[maxSize];// 栈空间
	int top[2];// top[0]为s0栈顶，top[1]为s1栈顶
} SqStack;

/* 初始化栈 */
void initStack(SqStack &st) {
	st.top[0]=-1;// st0栈的栈底是-1
	st.top[1]=maxSize;// st1栈的栈底是maxSize
}

/* 入栈 */
/* &st指的是共享栈；stNo指的是栈的编号，指元素入哪个栈；x指的是要入栈的元素 */
int push(SqStack &st,int stNo,int x) {
	if(st.top[0]+1<st.top[1]) { // 栈不满，则元素可以入栈
		if(stNo==0) { // 元素入st0
			++(st.top[0]);// 栈顶指针先加1
			st.elem[st.top[0]]=x;// 将新的元素压入st0栈中
			return 1;// 入栈成功返回1
		} else if(stNo==1) { // 元素入st1
			--(st.top[1]);// 由于st1栈的栈顶元是从数组尾部开始向前的，所以需要减1
			st.elem[st.top[1]]=x;// 将元素压入st1栈中
			return 1;// 入st1栈成功返回1
		} else {
			return -1;// 输入栈编号有误，返回-1
		}
	} else {
		return 0;// 栈满后元素不能入栈，返回0
	}
}

/* 出栈 */
/* &st指的是共享栈；stNo指的是栈的编号，指元素要出哪个栈；&x接收要栈的栈顶元素 */
int pop(SqStack &st,int stNo,int &x) {
	if(stNo==0) { // 表示st0栈的元素出栈
		if(st.top[0]!=-1) { // st0不空，则可以出栈
			x=st.elem[st.top[0]];// 出栈st0的栈顶元素
			--(st.top[0]);// 栈顶指针减1
			return 1;// 出栈成功返回1
		} else {
			return 0;// 栈空，出栈失败返回0
		}
	} else if(stNo==1) { // 表示st1栈的元素出栈
		if(st.top[1]!=maxSize) { // 栈不空，可以出栈
			x=st.elem[st.top[1]];// 出栈st1的栈顶元素
			++(st.top[1]);// 由于st1栈是从数组尾部开始的，所以需要加1才能表示出栈
			return 1;// 出栈成功返回1
		} else {
			return 0;// 出栈失败返回0
		}
	} else {
		return -1;// 栈编号输入有误，返回-1
	}
}

/* 打印共享栈 */
void printStack(SqStack st) {
	printf("\n");
	for(int i=0; i<=st.top[0]; i++) {
		printf("%d\t",st.elem[i]);
	}
	for(int i=st.top[1]; i<maxSize; i++) {
		printf("%d\t",st.elem[i]);
	}
	printf("\n");
}

int main() {
	SqStack st;// 定义共享栈
	initStack(st);// 初始化栈

	push(st,0,1);// 将元素1压入st0栈
	push(st,0,2);// 将元素2压入st0栈
	push(st,1,6);// 将元素6压入st1栈
	push(st,1,5);// 将元素5压入st1栈
	push(st,1,4);// 将元素4压入st1栈
	printStack(st);

	int x1;
	pop(st,0,x1);// 将st0栈中的栈顶元素出栈
	printStack(st);// 打印当前栈
	int x2;
	pop(st,1,x2);// 将st1栈中的栈顶元素出栈
	printStack(st);

	return 0;
}

运行结果：

重要概念

1. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求栈已存在。

2. 栈是操作受限(或限定仅在表尾部进行插入和删除操作)的线性表，其运算遵循的是先进后出原则。

3. 堆栈是一种操作受限的线性表，它只能在线性表的一端进行插入和删除操作，对栈的访问是按照先进后出的原则进行的。

4. 向栈中压入元素的操作是先进栈，后退栈。

5. 当两个栈共享一存储区时，栈利用一维数组stack(1，n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为0，top[2]为n+1，栈满时为top[1]+1=top[2]。

6. 两个栈共享空间时栈满的条件为两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。

7. 在进行入栈运算时应先判断栈是否满；在进行出栈运算时应先判断栈是否为空；当栈中元素为n个，作进栈运算时发生上溢时，则说明该栈的最大容量为n。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享的一片连续的空间时，应将两个栈的栈底分别设置在内存空间的两端，这样只有当两栈顶指针值相减的绝对值为1(或两栈顶指针相邻)时才产生溢出。

8. 多个栈共享时，最好使用链式存储结构作为存储结构。

9. 队列又称作先进先出表。

10. 队列的特点是先进先出。

11. 在具有n个元素的非空队列中插入一个或者删除一个元素的操作时间复杂度为O(1)

12. 循环队列是一种顺序(物理)结构。

13. 循环队列的目的时为了解决假溢出时大量移动数据元素。

14. 区分循环队列的满与空，只有两种方法，它们是牺牲一个存储单元，设标记(设计数器等方法)。

15. 用循环队列表示队列的长度为n，若只设头指针，则出队和入队的时间复杂度分别是O(1)和O(n)；若只设置尾指针，则出队和入队的时间复杂度分别是O(1)和O(1)。

栈的应用篇2：共享栈的应用

描述：本篇为共享栈的另一应用，试想如何能提高栈的空间利用率，共享栈便不失为一个好的想法，两个栈共享一个内存空间，动态操作数据，以下为具体过程：

基本设计思想：

顺序栈的栈底固定不动，我们将其设置在存储区的两端，假设s0为0处，s1设置在maxSize-1处，栈顶在0~maxSize-1活动，当两栈栈顶相遇便为栈满；s0的栈顶为top[0],进栈时规定先自增，再存入元素，出栈时先取元素，指针再自减1；s1入栈时top先自减，再存入元素，出栈时先取元素，指针再自增1。



#include<stdio.h>
#include <iostream> 
using namespace std;
#define MAXSIZE 100

//定义栈的结构体
typedef struct
{
    //栈的数据
    int data[MAXSIZE];
    //top[0],top[1]分别表示栈1和栈2的栈顶坐标
    int top[2];
}Sqstack;
//入栈操作
int push(Sqstack &st,int stNo,int x) //stNo为栈编号
{
    if(top[0]+1 < top[1])//栈不满，元素入栈
    {
        if(stNo == 0) 
        {
            ++(st.top[0]);
            st.data[st.top[0]]=x;
            return 1; //入栈成功
        }
        else if(stNo == 1)
        {
            --(st.top[1]);
            st.data[st.top[1]]=x;
            return 1; //入栈成功
        }
        else return -1;
    }
    else return 0; //栈满后元素不能入栈
}
//出栈操作
int pop(Sqstack &st,int stNo,int &x) //stNo为栈编号
{
    if(stNo == 0)//st0元素入栈
    {
        if(st.top[0] != -1)
        {
            x = st.data[st.top[0]];
            --(st.top[0]);
            return 1; //出栈成功
        }
        else return 0; //st0栈空，出栈失败
    }
    else if(stNo == 1)
    {
        if(st.top[1] != MAXSIZE) //st1不空，可以出栈
        {
            x = st.data[st.top[1]];
            ++(st.top[1]);
            return 1; //出栈成功
        }
        else return 0; //s0栈空，出栈失败
    }
    else return -1;
}

每个jvm实例都有方法区和一个堆（hasone method area and one heap）。这两个区域被jvm中的线程共享。当JVM加载了一个class文件后，则class中的参数、类型等信息会存储在方法区中。程序运行时所有创建的对象存储在堆中。
         当每一个新线程启动时会有自己的程序计数器pcregister (program counter)和栈，如果线程调用方法，则程序计数器表明下一条执行的指令。线程栈存储线程的方法调用状态（包括局部变量、和被调用的参数、返回值、中间结果）。上面所说本地方法（见下图）调用相独立，本地方法调用存储在独立的本地方法栈中，或其他独立的内存区域。



         每个线程都有一个程序计数器，也就是会说每创建一个线程时就会创建一个程序计数器，JVM中所说的程序技术器区域就是所有线程程序计数器取得总称。
         栈区域是由栈桢组成，每个栈桢就是每个调用的方法的栈。当方法调用结束时JVM会POPS栈，即抛弃此方法的栈桢。