栈
定义
只允许在一端插入和删除数据，后进先出的线性表。
栈既可以用数组实现，也可以用链表来实现。
固定大小的栈
由于操作简单，常规的栈时间复杂度和空间复杂度皆为O(1)。
支持动态扩展的栈
支持动态扩容的栈，其底层其实是用一个支持动态扩容的数组支持的，当栈空间满了以后，我们就申请一个更大的数组，将原来的数据迁移过去。
如果忘了数组是如何支持动态扩展的，可以去下文复习一下。
淤白：02 数组（附ArrayList源码分析）​zhuanlan.zhihu.com
支持动态扩展的栈，其时间复杂度平时是O(1)，但当进行扩容的时候，时间复杂度就变为了O(n)，利用摊还分析法，我们可知，其平均情况下的时间复杂度为O(1)。
摊还分析法可以在下文中复习一下。
淤白：01 复杂度分析​zhuanlan.zhihu.com
平时开发过程中，遇到的栈操作可能不多，但其实我们可能一直在用到它。例如函数调用（遇到过StackOverflowError的化，可能记忆犹新）；还有在表达式求值的时候，其实编译器就是通过栈去实现的。面试中，我们可能也会碰到栈的相关问题：括号匹配，用栈实现队列。
队列
定义
允许在一端插入数据，另一端删除数据，先进先出的线性表。
队列和栈类似，也可以使用数组或者链表实现。
顺序队列（数组实现）
相较于栈的一端操作，只需要一个指针，队列的入队出队需要两个指针head和tail的配合。但这里会碰到一个问题，如果每次出队的时候（类比删除数组元素下标为0的元素），都进行数据前移，那时间复杂度就是O(n)了。下图是进行三次出队的情况。
针对这种情况，我们可以用到数组篇聊到的一个方案，延迟前移，只有当入队时发现空间不够了，再进行整体的一个移位，这样均摊下来，时间复杂度也就降下来了。
还有一种解决方案，就是使用循环队列。
循环队列
顾名思义，就是将队尾和队首连起来，即当tail指针指向队尾时，再进行入队操作，会将tail指针指向下标为0的位置。通过循环队列，我们就不需要再考虑数据移位的问题，不过实现起来，需要考虑清楚队空和队满的情况。
在非循环队列中，判断队空用的head == tail，队满用的tail == n。
在循环队列中，判断队空仍然可用head == tail，但是队满不能使用tail == n了，而是要用(tail+1) % n == head，可以画图试一下。
队列在实际开发中，用到的会更多一些，比如支持并发的BlockingQueue阻塞队列，用来实现生产者-消费者模型。还有就是双端队列Deque，支持在队首队尾都可以进行入队出队操作。

原理：
想要一个数组实现两个栈，那么就必须一个栈的栈顶从数组下标为0处开始，另一个栈从数组额最大下标处开始，两个栈相对而生如下图所示：

如何判断栈满？
当两个栈顶标记重合时，表示共享栈已经满了
代码如下：
头文件ShareStack.h
#pragma once

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

typedef char StackType;

typedef struct ShareStack{
    StackType* space;
    size_t size_left;
    size_t size_right;
    size_t max_size;
}ShareStack;

void ShareStackInit(ShareStack* stack); //共享栈的初始化

void ShareStackDestroy(ShareStack* stack); //销毁共享栈


//对左边栈进行操作
void LeftShareStackPush(ShareStack* stack, StackType value);//入栈

void LeftShareStackPop(ShareStack* stack); //出栈

int LeftShareStackTop(ShareStack* stack, StackType* value); //取栈顶元素


//对右边栈进行操作
void RightShareStackPush(ShareStack* stack, StackType value); //入栈

void RightShareStackPop(ShareStack* stack); //出栈

int RightShareStackTop(ShareStack* stack, StackType* value);//取栈顶元素
头文件的实现ShareStack.c：
#include"ShareStack.h"

void ShareStackInit(ShareStack* stack) {
    if(stack == NULL) {
        return;
    }
    stack->max_size = 10;
    stack->size_left = 0;
    stack->size_right = stack->max_size;
    stack->space = malloc(stack->max_size * sizeof(ShareStack));
    return;
}

void ShareStackDestroy(ShareStack* stack) {
    if(stack == NULL) {
        return;
    }
    stack->max_size = 0;
    stack->size_left = 0;
    stack->size_right = 0;
    free(stack->space);
    stack->space = NULL;
}

void LeftShareStackPush(ShareStack* stack, StackType value) {
    if(stack == NULL) {
        return;
    }
    if(stack->size_left == stack->size_right) {
        return;
    }
    stack->space[stack->size_left] = value;
    stack->size_left++;
    return;
}

void LeftShareStackPop(ShareStack* stack) {
    if(stack == NULL) {
        return;
    }
    if(stack->size_left == 0) {
        return;
    }
    stack->size_left--;
    return;
}

int LeftShareStackTop(ShareStack* stack, StackType* value) {
    if(stack == NULL || value == NULL) {
        return 0;
    }
    if(stack->size_left == 0) {
        return 0;
    }
    *value = stack->space[stack->size_left - 1];
    return 1;
}


void RightShareStackPush(ShareStack* stack, StackType value) {
    if(stack == NULL) {
        return;
    }
    if(stack->size_left == stack->size_right) {
        return;
    }
    stack->size_right--;
    stack->space[stack->size_right] = value;
    return;
}

void RightShareStackPop(ShareStack* stack) {
    if(stack == NULL) {
        return;
    }
    if(stack->size_left == stack->max_size) {
        return;
    }
    stack->size_right++;
    return;
}

int RightShareStackTop(ShareStack* stack, StackType* value) {
    if(stack == NULL || value == NULL) {
        return 0;
    }
    if(stack->size_right == stack->max_size) {
        return 0;
    }
    *value = stack->space[stack->size_right];
    return 1;
}

///
//以下为测试代码
///

void TestShareStack() {
    int ret;
    StackType value;
    ShareStack stack;
    ShareStackInit(&stack);
    printf("LeftStack:\n");
    LeftShareStackPush(&stack, 'a');
    LeftShareStackPush(&stack, 'b');
    LeftShareStackPush(&stack, 'c');
    LeftShareStackPush(&stack, 'd');
    ret = LeftShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect d, actual %c\n", value);
    LeftShareStackPop(&stack);

    ret = LeftShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect c, actual %c\n", value);
    LeftShareStackPop(&stack);

    ret = LeftShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect b, actual %c\n", value);
    LeftShareStackPop(&stack);

    ret = LeftShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect a, actual %c\n", value);
    LeftShareStackPop(&stack);

   ret = LeftShareStackTop(&stack, &value); //对空栈进行取栈顶元素
    LeftShareStackPop(&stack); //对空栈出栈
    printf("ret expect 0, actual %d\n", ret);



    printf("\nRightStack\n");
    RightShareStackPush(&stack, 'A');
    RightShareStackPush(&stack, 'B');
    RightShareStackPush(&stack, 'C');
    RightShareStackPush(&stack, 'D');

    ret = RightShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect D, actual %c\n", value);
    RightShareStackPop(&stack);

    ret = RightShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect C, actual %c\n", value);
    RightShareStackPop(&stack);

    ret = RightShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect B, actual %c\n", value);
    RightShareStackPop(&stack);

    ret = RightShareStackTop(&stack, &value);
    printf("ret expect 1, actual %d\n", ret);
    printf("value expect A, actual %c\n", value);
    RightShareStackPop(&stack);

   ret = RightShareStackTop(&stack, &value); //对空栈进行取栈顶元素
    RightShareStackPop(&stack); //对空栈出栈
    printf("ret expect 0, actual %d\n", ret);

    ShareStackDestroy(&stack);
}

int main()
{
    TestShareStack();
    return 0;
}

本篇文章参考的是《大话数据结构》，感谢作者程杰先生。
一：

两栈共享同一空间，即数组，数组有两个端点，两个栈有两个栈底，

让一个栈的栈底为数组的时段，即下标为0处，另一个栈的栈底为数组的末端，

即数组长度n-1处，这样，两个栈如果增加元素，就是两个端点向中间延伸。



二：如何判断栈满？

1.普通情况下，当top1与top2见面时，为栈满，

即 top1 + 1 = top2;
2.极端情况，若栈2是空栈，栈1的top1等于n-1，就是栈1满了；

当栈1为空时，top2等于0时，为栈2满。
三：

代码：
/*
 
本篇文章参考的是《大话数据结构》，感谢作者程杰先生。

*/

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

#include "bigtalk_data_structure.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 

typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


/* 两栈共享空间结构 */
typedef struct 
{
	SElemType data[MAXSIZE];
	int top1;	/* 栈1栈顶指针 */
	int top2;	/* 栈2栈顶指针 */
}SqDoubleStack;


static Status visit(SElemType c)
{
	printf("%d ",c);
	return OK;
}

/*  构造一个空栈S */
static Status InitStack(SqDoubleStack *S)
{ 
	S->top1=-1;
	S->top2=MAXSIZE;
	return OK;
}

/* 把S置为空栈 */
static Status ClearStack(SqDoubleStack *S)
{ 
	S->top1=-1;
	S->top2=MAXSIZE;
	return OK;
}

/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
static Status StackEmpty(SqDoubleStack S)
{ 
	if (S.top1==-1 && S.top2==MAXSIZE)
		return TRUE;
	else
		return FALSE;
}

/* 返回S的元素个数，即栈的长度 */
static int StackLength(SqDoubleStack S)
{ 
	return (S.top1+1)+(MAXSIZE-S.top2);
}

/* 插入元素e为新的栈顶元素 */
static Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
	if (S->top1+1==S->top2)	/* 栈已满，不能再push新元素了 */
		return ERROR;	
	
	if (stackNumber==1)			/* 栈1有元素进栈 */
		S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */
	else if (stackNumber==2)	/* 栈2有元素进栈 */
		S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */

	return OK;
}

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
static Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{ 
	if (stackNumber==1) 
	{
		if (S->top1==-1) 
			return ERROR; /* 说明栈1已经是空栈，溢出 */
		*e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
	}
	else if (stackNumber==2)
	{ 
		if (S->top2==MAXSIZE) 
			return ERROR; /* 说明栈2已经是空栈，溢出 */
		*e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
	}
	return OK;
}

static Status StackTraverse(SqDoubleStack S)
{
	int i;
	i=0;
	while(i<=S.top1)
	{
		visit(S.data[i++]);
	}
	
	i=S.top2;
	while(i<MAXSIZE)
	{
		visit(S.data[i++]);
	}
	printf("\n");
	return OK;
}

//栈:两栈共享空间
void test_main_4_5()
{
	printf("[%s:%d]:[yang] ******************* 我是分割线******************* \n",__FUNCTION__,__LINE__);	

	int j;
	SqDoubleStack s;
	int e;
	if(InitStack(&s)==OK)
	{
		for(j=1;j<=5;j++)
			Push(&s,j,1);
		
		for(j = MAXSIZE;j >= MAXSIZE-2; j--)
			Push(&s,j,2);
	}
	
	printf("栈中元素依次为：");
	StackTraverse(s);

	printf("当前栈中元素有：%d \n",StackLength(s));

	printf("[%s:%d]:[yang] ******************* 我是分割线******************* \n",__FUNCTION__,__LINE__);	

	Pop(&s,&e,2);
	printf("弹出的栈顶元素 e=%d\n",e);
	printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));

	printf("栈中元素依次为：");
	StackTraverse(s);
	printf("[%s:%d]:[yang] ******************* 我是分割线******************* \n",__FUNCTION__,__LINE__);	


	for(j = 6;j <= MAXSIZE-2; j++)
		Push(&s,j,1);
	
	printf("栈中元素依次为：");
	StackTraverse(s);
	
	printf("栈满否：%d(1:否 0:满)\n",Push(&s,100,1));
	

	printf("[%s:%d]:[yang] ******************* 我是分割线******************* \n",__FUNCTION__,__LINE__);	

	ClearStack(&s);
	printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
	
	#if 0

	#endif

    return 0;
}





打印：
[main:14]:[yang] ***************************************** 
[test_main_4_5:125]:[yang] ******************* 我是分割线******************* 
栈中元素依次为：1 2 3 4 5 18 19 20 
当前栈中元素有：8 
[test_main_4_5:144]:[yang] ******************* 我是分割线******************* 
弹出的栈顶元素 e=18
栈空否：0(1:空 0:否)
栈中元素依次为：1 2 3 4 5 19 20 
[test_main_4_5:152]:[yang] ******************* 我是分割线******************* 
栈中元素依次为：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
栈满否：0(1:否 0:满)
[test_main_4_5:164]:[yang] ******************* 我是分割线******************* 
清空栈后，栈空否：1(1:空 0:否)

数组模拟栈

题目要求：

编写程序，使用一维数组，模拟栈数据结构。

1、这个栈可以存储java中的任何引用类型的数据。

2、在栈中提供push方法模拟压栈。（栈满了，要有提示信息。）

3、在栈中提供pop方法模拟弹栈。（栈空了，也有有提示信息。）

4、编写测试程序，new栈对象，调用push pop方法来模拟压栈弹栈的动作。


首先是我的想法和思路：

既然是模拟栈，那么就要做到先进后出的功能。栈如何去定位当前元素呢？

通过栈帧index。

所以我需要一个index变量去定位每次栈顶的位置，从而去判断栈是否满了

而且还可以在对数组下标为index的变量操作时达到“先进后出”的目的

接着就是题目中要求的“这个栈可以存储java中的任何引用类型的数据。”

意味着我们这个数组要用的是Obeject类型。

至此大体已出

接下来是我的代码：
首先就是MyStack类，这个类是关于栈的模拟
public class MyStack {
    Object[] elements;
    int index = -1;
    public MyStack(Object[] elements) {
        this.elements = elements;
    }
    public void push(Object object){
    	if(index != elements.length - 1){
    		index++;
    		elements[index] = object;
    		System.out.println("压栈成功");
    	}else{
    		System.out.println("错误：栈满！无法压栈！");
    	}
    }

接下来就是关于测试程序了
测试程序MyStackTest
import java.util.Scanner;
public class MyStackTest {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int length;
        System.out.println("请输入栈的大小：");
        length = input.nextInt(); 
        String[] a1 = new String[length];
        MyStack myStack1 = new MyStack(a1);
        int flag = 0;
        while(flag != 3){
        	    System.out.println("请输入您要进行的操作：1代表push（压栈），2代表pop（弹栈）,3表示停止该操作");
        	    flag = input.nextInt();
        	    if(flag == 1){
        	    	String toInPut;
        	    	System.out.println("请输入您要压入栈的内容");
        	    	toInPut = input.next();
        	    	myStack1.push(toInPut);        	  
        	     }else if(flag == 2){
        	     	myStack1.pop();
        	     }else if(flag == 3){
        	     	break;
        	     }else{
        	        System.out.println("输入不合法！请输入您要进行的操作：1代表push（压栈），2代表pop（弹栈），3表示停止该操作");	    
        	     }
        	   }
        	}
        } 

这就是数组模拟栈。

酒店管理系统的模拟

题目要求

为某个酒店编写程序：酒店管理系统，模拟订房、退房、打印所有房间状态等功能。

1、该系统的用户是：酒店前台。

2、酒店使用一个二维数组来模拟。“Room[][] rooms;”

3、酒店中的每一个房间应该是一个java对象：Room

4、每一个房间Room应该有：房间编号、房间类型、房间是否空闲.

5、系统应该对外提供的功能：

可以预定房间：用户输入房间编号，订房。

可以退房：用户输入房间编号，退房。

可以查看房间的状态：用户输入某个指令应该可以查看所有房间状态。



想法和思路：

该题目较为简单，主要思想就是去实现每个功能

题目已经给了要求：用一个Room类和二维数组去实现。

Room类主要是存储每个房间的信息：例如门牌号，是否空闲等

而二维数组则是去存储每个房间。

接下来只需实现即可

我的代码：
首先是实现各个功能以及Room类
注意，这里最好是吧Room类和功能实现分开写，但是我合并了，以后不要这样
public class Room {
    static Room[][] rooms = new Room[3][10];
    int roomId;
    int floor =0,number = 0;
        boolean flag = false;
    String roomStyle;

    public static void Initialization(){
        int k,p;
        for(k = 0;k < 3;k++){
            for(p = 0;p < 10;p++){
                rooms[k][p] = new Room();
            }
        }
    }

    public void setRoomId(int roomId) {
        this.roomId = roomId;
    }

    public Room(){}


    public void reserveRoomId(){
        floor = (roomId/100) - 1;
        number = (roomId%100) - 1;
    }

    public void orderRoom(){
        if(rooms[floor][number].flag == true){
            System.out.println("该房间已满！请另换一间！");
        }else{
            rooms[floor][number].flag = true;
            System.out.println("预订成功！您预订的房间号为：" + roomId + "房间位于第" + (floor+1) + "层0" + (number+1) + "号房");
        }
    }

    public void Check_out(){
        if(rooms[floor][number].flag == false){
            System.out.println("该房间本就为空！无法退房！");
        }else{
            rooms[floor][number].flag = false;
            System.out.println("退房成功！" + roomId + "房间已成功退房" );
        }
    }

    public void View_information(){
        System.out.println("将为您打印全部房间信息：");
        int i,j,roomids;
        for(i = 0;i < 3;i++){
            System.out.println("房间号\t\t房间是否满员\t\t房间类型");
            for(j = 0;j < 10;j++){
                if(i == 0){
                    rooms[i][j].roomStyle = "普通房";
                }else if(i == 1){
                    rooms[i][j].roomStyle = "豪华房";
                }else{
                    rooms[i][j].roomStyle = "贵宾房";
                }
                roomids = ((i+1)*100)+(j+1);
                System.out.println(roomids + "\t\t\t" + rooms[i][j].flag + "\t\t\t" + rooms[i][j].roomStyle);
            }
        }
    }
}                

接下来就是测试程序
写到测试程序我就意识到得注意程序的用户交互性
用户可能会有各种输入，那么正确的输入我们得去执行功能
而错误的输入我们则得去提醒用户输入错误以及正确的输入方式
这样可以避免很多麻烦
import java.util.Scanner;
public class HotelTest {
    public static void main(String[] args) {
        int flag = 0;
        int roomId;
        Scanner input = new Scanner(System.in);
        Room.Initialization();
        Room room = new Room();
        System.out.println("欢迎来到why牌酒店管理系统！~");
        System.out.println("本酒店一共有3层楼，每层楼10间房间");
        System.out.println("下面请输入：1（预订房间）；2（退房）；3（查看所有房间信息）；4（退出系统）");
        while(flag != 4){
            flag = input.nextInt();
            if(flag == 1){
                System.out.println("现在是订房界面：");
                System.out.println("请输入房间号：");
                System.out.println("注意：房间号每层尾号从1开始到9结束，例如1层3号房就是：103");
                roomId = input.nextInt();
                if(((roomId/100) >= 1 &&(roomId/100) <=3)&&((roomId%100) >=1&&(roomId%100) <=10)){
                    room.setRoomId(roomId);
                    room.reserveRoomId();
                    room.orderRoom();
                }else{
                    System.out.println("输入房间号错误！注意：房间号每层尾号从1开始到9结束，例如1层3号房就是：103");
                }     
            }else if(flag == 2){
                System.out.println("现在是退房界面：");
                System.out.println("请输入房间号：");
                System.out.println("注意：房间号每层尾号从1开始到9结束，例如1层3号房就是：103");
                roomId = input.nextInt();
                if(((roomId/100) >= 1 &&(roomId/100) <=3)&&((roomId%100) >=1&&(roomId%100) <=10)){
                    room.setRoomId(roomId);
                    room.reserveRoomId();
                    room.Check_out();
                }else{
                    System.out.println("输入房间号错误！注意：房间号每层尾号从1开始到9结束，例如1层3号房就是：103");
                }    
            }else if(flag == 3){
                room.View_information();
            }else if(flag == 4){
                System.out.println("感谢使用why牌酒店管理系统！已关机！");
                break;
            }else{
                System.out.println("输入错误！请输入：1（预订房间）；2（退房）；3（查看所有房间信息）；4（退出系统）");
            }
        }
    }
}                               

入上便是我的程序，功能实现完全没问题，那么是不是就没问题了呢？

并不是。

我的程序的问题
在对比了老师写的程序后，我发现了我现在的问题：
虽然会封装，知道要重写方法（例如toString,equal方法）但是不会去用。
在老师的程序中，强调了无论如何，那怕用不上也要对程序封装
然后提供set和get方法，这点是我以后必须得记住的。

至于老师的代码不予提供，自行寻找。