栈|基础

1. 栈与队列的定义及特点

  • 栈与队列是操作受限线性表

限定在表尾进行插入删除操作的线性表。

表尾:栈顶top

表头:栈底bottom

后进先出。

队列

限定在表的一端插入,另一端删除元素的线性表。

插入一端为队尾 rear

删除的一端为队头 front

先进先出。

2.栈的顺序存储

1
2
3
4
5
6
#define MaxSize 50

typedef struct{
ElemType data[MaxSize];
int top; //栈顶指针
}SqStack;

栈空栈满的状态

s.top==0 表示栈空:

  • 入栈,top+1
  • +1后变成1
  • 栈顶指针指向栈顶元素的下一位
  • s.top==MaxSize 表示栈满

s.top==-1表示栈空

  • 只要入栈,top就会+1
  • top+1,变成0
  • 栈顶指针始终指向栈顶元素
  • s.top==MaxSize-1 表示栈满

s.top==MaxSize=n 表示栈空:

  • 只要入栈,top-1到n-1
  • 栈顶指针始终指向栈顶元素
  • s.top==0表示栈满

s.top=MaxSize=n-1 表示栈空

  • 只要入栈,top-1
  • 栈顶指针始终指向栈顶元素的上一位
  • s.top==-1表示栈满

栈满后再入栈,会出现上溢状态。解决方法:用链栈。

栈空后再出栈,会出现下溢状态。下溢是逻辑问题。


代码表示

初始化栈

1
2
3
void InitStack(SqStack &S){//S必须引用
S.top = -1;
}

判断栈是否为空

1
2
3
bool StackEmpty(SqStack S){
return S.top == -1;
}

入栈

1
2
3
4
5
6
7
bool Push(SqStack &S, ElemType x){
if(S.top == MaxSize - 1){
return false;
}
S.data[++S.top] = x;
retrun true;
}

出栈

1
2
3
4
5
6
7
8
bool Pop(SqStack &S,ElemType &x){
if(S.top == -1){
return false;
}

x=S.data[S.top--];
return true;
}

只读取栈顶元素(和上面类似)

1
2
3
4
5
6
7
8
bool GetTop(SqStack &S,ElemType &x){//此处引用是避免内存大量复制
if(S.top == -1){
return false;
}

x=S.data[S.top];
return true;
}

顺序栈的优缺点

  • 申请存储空间过大时,会浪费存储空间。
  • 数据多时,会上溢。

顺序表和链表造成的内存浪费:

  • 顺序表:MaxSize的限制
  • 链表:指针域造成内存浪费

解决方法:最大限度利用一个存储空间————共享栈

共享栈:

底部是固定的,设定两个栈。

一个从左向右走,top0=-1,表示栈空,入栈top增加。

一个从右向左走,top1=MaxSize,表示栈空,入栈top减小。

栈满:两个栈顶指针相遇:top1=top0+1

好处:时间都是O(1),节省存储空间,降低发生上溢的可能。

3.栈的链式存储

链式存储的优势

  • 便于多个栈共享存储空间,提高效率
  • 不存在上溢的情况
  • 插入删除结点方便

规范

  • 采用单链表实现
  • 所有操作在表头执行
  • 链栈没有头节点

代码表示

存储结构

1
2
3
4
typedef struct StackNode{
ElemType data;
struct StackNode *next;
}StackNode,*LinkStack;

入栈

1
2
3
4
5
6
7
8
9
10
11
void Push(LinkStack &S, ElemType e){
//生成新的结点
StackNode *p = (StackNode*)malloc(sizeof(StackNode));
//将新结点数据域设为e
p->data=e;

//将新结点插入栈顶
p->next= S;
//修改栈顶指针为p
S = p;
}

出栈(考虑下溢)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Pop(LinkStack &S,ElemType &e){
//栈空
if(S==NULL){
return false;
}

//将栈顶元素赋给e
e = S->data;

//用p临时保存栈顶元素的空间,以备释放
StackNode *p = S;
//修改栈顶指针
S = S->next;

free(p);

return true;
}