一、栈

栈就是后进先出的线性表。

  • 表尾叫做==栈顶==，表头叫做==栈底==

1. 顺序存储

（1） 结构体定义

#define MAXSIZE 100
typedef struct
{
	ElemType *base; // 栈底指针
	ElemType *top; // 栈顶指针
	int stacksize; // 栈大小
}SqStack;
  • base始终指向栈底，若base == NULL，则说明为空栈
  • top为栈顶指针，起初栈中没有元素时指向栈底，每添加一个元素，top也++，top始终指向最后一个元素的上一个位置

    （2） 初始化空栈

    Status InitStack(SqStack &S)
    {
    	S.base = new ElemType[MAXSIZE]; // 分配内存
    	if (!S.base) exit(OVERFLOW); // 内存分配失败
    	S.top = S.base; // 栈中无元素，栈顶指针和栈底指针相等
    	S.stacksize = MAXSIZE;
    	return OK;
    }

    （3） 入栈

    思路： 就是先判断栈是否满，没满就在栈顶插入一个新元素，最后不要忘了把栈顶指针+1
    Status Push(SqStack &S, ElemType e)
    {
    	if (S.top - S.base == S.stacksize) return ERROR; // 栈满，插入失败
    	*S.top ++ = e;
    	return OK;
    }
    *S.top ++ = e;

    等价于

    *S.top = e; // 栈顶元素赋为e
    *S.top ++; //  栈顶指针+1

（4） 出栈

思路： 看看栈是不是空的，不是空的就让栈顶指针—就好啦

Status Pop(SqStack &S, ElemType &e)
{
	if (S.top == S.base) return ERROR; // 栈空，没有能删的
	e = *-- S.top;
	return OK;
}

e = *-- S.top;

等价于

*S.top --; // 栈顶指针-1
e = *S.top; //  栈顶元素赋为e

（5）取栈顶元素

思路： 没有思路

ElemType GetTop(SqStack S)
{
	if (S.top != S.base) return *(S.top - 1); // 栈顶指针不变
}

2. 链式存储

（1） 结构体定义

typedef struct StackNode
{
	ElemType data;
	struct StackNode *next;
}StackNode, *LinkStack;
  • 不需要单独设置头结点，因为第一个元素不需要改变

    （2） 初始化空栈

    Status InitStack(LinkStack &S)
    {
    	S = NULL;
    	return OK;
    }

    （3） 入栈

    思路： 建立一个新的结点，接到链表的后面就好啦，记得修改栈顶指针
    Status Push(LinkStack &S, ElemType e)
    {
    	p = new StackNode; // 分配空间
    	p->data = e; // 赋值
    	p->next = S; // 新结点插入栈顶
    	S = p; // 修改栈顶指针
    	return OK;
    }

    （4） 出栈

    思路： 看看是不是空栈，不是空栈就修改栈顶指针，释放原来栈顶的空间
    Status Pop(LinkStack &S, ElemType &e)
    {
    	if (S == NULL) return ERROR; // 栈空
    	e = S->data; // 存要删去的值
    	p = S; // 记录要删去的结点
    	S = S->next; // 修改栈顶指针
    	delete p; // 释放空间
    	return OK;
    }

    （5） 取栈顶元素

    ElemType GetTop(LinkStack S)
    {
    	if (S) return S->data;
    }

    二、队列

    队列就是先进先出的线性表。
  • 插入的那一端叫做==队尾==，删除的那一端叫做==队头==

    1. 顺序存储

    （1） 结构体定义

    #define MAXSIZE 100;
    typedef struct
    {
    	ElemType *base;
    	int front; // 头指针：指向队头元素位置
    	int rear; // 尾指针：指向队尾元素的下一个位置
    }SqQueue;
  • 在使用时一般选择循环队列，每在队头删除一个元素，就让front = （front + 1） % MAXSIZE ， 每在队尾插入一个元素，就让rear = （rear + 1）% MAXSIZE，解决假溢出问题
  • 为便于判断队空队满，一个循环队列只用MAXSIZE - 1个位置
    • 当front == rear + 1时：队满
    • 当front == rear 时：队空

      （2） 初始化空队

      Status InitQueue(SqQueue &Q)
      {
      	Q,base = new ElemType[MAXSIZE]; // 分配一整个数组的内存
      	if (!Q.base) exit(OVERFLOW); // 分配内存失败
      	Q.front = Q,rear = 0; // 初始化头尾指针
      	return OK;
      }

      （3） 求队列长度

      思路： 头指针和尾指针的差值就是长度，差值可能为负数就加上MAXSIZE
      int QueueLength(Squeue Q)
      {
      	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
      }

      （4） 入队

      思路： 看看是不是队满，没满就把新元素放到rear的位置，然后让rear ++
      Status EnQueue(SqQueue &Q, ElemType e)
      {
      	if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
      	Q.base[Q.rear] = e; // 赋值
      	Q.rear = (Q.rear + 1) % MAXSIZE; // 更新尾指针
      	return OK;
      }

      （5） 出队

      思路： 看看是不是队空，不空就记录一下马上删的元素也就是队头front的元素，然后让front++
      Status DeQueue(SqQueue &Q, ElemType &e)
      {
      	if (Q.front == Q.rear) return ERROR;
      	e = Q.base[Q.front];
      	Q.front = (Q.front + 1) % MAXSIZE;
      	return OK;
      }

      （6） 取队头元素

      思路： 没有思路
      ElemType GetHead(SqQueue Q)
      {
      	if (Q.front != Q.rear) // 说明非空队
      		return Q.base[Q.front];
      }

      2. 链式存储

      是长这个样子滴，front 和 rear 不存数值

（1） 结构体定义

typedef struct QNode
{
	ElemType data;
	struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
	QueuePtr front; // 队头指针
	QueuePtr rear; // 队尾指针
}LinkQueue;

（2） 初始化空队

思路： 构造一个单独的结点

Status InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = new QNode;
	Q.front->next = NULL;
	return OK;
}

（3） 入队

思路： 分配一个结点空间接到队伍后面，不要忘记修改尾指针

Status EnQueue(LinkQueue &Q, ElemType e)
{
	p = new QNode;
	p->data = e;
	p->next = NULL;
	Q.rear->next = p; // 修改尾指针
	Q.rear = p;
	return OK;
}

（4） 出队

思路： 先看看是不是空队，不是就记录下要删掉的结点，修改头指针，最后判断下删掉的是不是队列中最后一个元素，是的话也修改一下尾指针

Status DeQueue(LinkQueue &Q, ElemType &e)
{
	if (Q.front == Q.rear) return ERROR;
	p = Q.front->next; // 记录队头
	e = p->data; // 记录队头数据
	Q.front->next = p->next; // 修改头指针
	if (Q.rear == p) Q.rear = Q.front;
	delete p;
	return OK;
}

（5）取队头元素

ElemType GetHead(LinkQueue Q)
{
	if (Q.front != Q.rear) // 如果队列不空
		return Q.front->next->data;
}