特点

  • 根据存储结构不同分为顺序栈与链栈, 顺序栈:顺序存储; 链栈:链式存储
  • 是限定在表尾进行插入和删除的线性表
  • 表尾端为栈顶,表头端为栈底
  • 修改遵循后进先出

I. 分类–顺序栈

操作

(插入图片)

1.存储结构
1
2
3
4
5
6
#define MAXSIZE 100
typedef struct{
SElemType *base; //栈底指针,指向栈底元素
SElemType *top; //栈顶指针
int stacksize; //栈可用的最大容量
}SqStack;
2.初始化

步骤:

a. 为顺序栈分配一个最大容量MAXZISE的数组空间

b. 栈顶指针top初始化为栈底指针base,表示空栈

c. stacksize设为栈的最大容量MAXSIZE

1
2
3
4
5
6
7
8
Status InitStack(SqStack &S)
{
S.base = new SElemType[MAXSIZE]; //动态分配最大容量为MAXSIZE的数组
if(!S.base) exit(EOVERFLOW);
S.top = S.base; //空栈
S.stacksize = MAXSIZE;;
return OK;
}
3.入栈

步骤:

a. 判断栈容量是否已满

b. 将插入的元素压入栈顶,栈顶指针加1

1
2
3
4
5
6
7
8
9
Status Push(SqStack &S, SElemType e)
{
if(S.top-S.base==S.stacksize)
return ERROR;
// *S.top++ = e;
*S.top = e;
S.top++;
return OK;
}
4.出栈

步骤:

a. 判断栈是否为空

b. 先将栈顶指针减1,再将要出栈的元素赋给栈顶指针所指的值,栈顶元素出栈

1
2
3
4
5
6
7
8
9
Status Pop(SqStack &S, SElemType &e)
{
if(S.top==S.base)
return ERROR;
S.top--;
e = *S.top;
//e = *--S.top;
return OK;
}
5.取栈顶元素

步骤:

a. 若非空,返回栈顶指针的值,栈顶指针保持不变

1
2
3
4
5
6
7
8
Status GetTop(SqStack &S)
{
if(S.top!=S.base)
{
return *(S.top-1);
}
return OK;
}
6.完整实现(java)
1
2


II. 分类–链栈

1.存储结构
1
2
3
4
typedef struct StackNode{
ElemType data;
struct StackNode *next;
}StackNode, *LinkStack;
2.初始化

步骤:

a. 构造一个空栈,不用设头结点,直接将栈顶指针置空

1
2
3
4
5
Status InitStack(LinkStack &S)
{
S = NULL;
return 0;
}
3.入栈

步骤:

a. 为入栈元素分配空间,并用新指针结点指向

b. 新结点值设为e

c. 新结点插入栈顶,修改栈顶指针为p

1
2
3
4
5
6
7
8
9
Status Push(LinkStack &S, ElemType e){

LinkStack p = new StackNode; //生成新结点
p->data = e;
p->next = S; //插到栈顶
S = p; //修改栈顶指针为p

return OK;
}
4.出栈

步骤:

a. 判断是否为空

b. 将栈顶元素赋给e,临时保存栈顶元素空间,以备释放

c. 修改栈顶指针,指向新元素

d. 释放原栈顶元素空间

1
2
3
4
5
6
7
8
9
Status Pop(LinkStack &S, ElemType &e){
if(S==NULL) return ERROR;
LinkStack p = new StackNode;
e = S->data;
p = S; //p临时保存栈顶元素空间,以备释放
S = S->next;
delete p;

return OK;
5.取栈顶元素
1
2
3
4
5
Status GetTop(LinkStack &S)
{
if(S!=NULL)
return S->data;
}
6.完整实现(java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//链栈类代码
package stack;
import java.lang.NullPointerException;

public class LinkStack {
private Element base;
private Element top;

class Element{
public Object data;
public Element next;
}

//初始化
void initStack(){
top = new Element();
base = new Element();

top.data = null;
top.next = null;
base.data = null;
base.next = null;
}

//入栈
void push(Object o){
Element e = new Element();
e.data = o;
//empty stack
if(top.next==base){
e.next = base;
top.next = e;
}else{
e.next = top.next;
top.next = e;
}
}

//出栈
void pop(){
if(top.next==base){
System.out.println("栈中没有元素");
}else {
System.out.println("出栈:" + top.next.data);
top.next = top.next.next;
}
}

//print
void print(){
System.out.println("打印栈:\n");
Element temp = top;
while(temp.next!=base){
System.out.println(temp.next.data + "\t");
temp = temp.next;
}
System.out.println();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//链栈测试代码
package stack;

public class LinkStackMain {
public static void main(String[] args){
LinkStack ls = new LinkStack();
ls.initStack();

ls.push(1);
ls.push(2);
ls.push(3);
ls.push(4);
ls.print();

ls.pop();
ls.pop();
ls.print();

ls.pop();
ls.pop();
ls.print();
ls.pop();
}
}

顺序栈与链栈的区别

  • 存储结构
    • 顺序栈:顺序存储
    • 链栈: 链式存储
    • 链栈通常不会出现栈满情况,链栈动态分配内存,不浪费内存;顺序栈使用固定大小数组保存数据,容易浪费内存
  • top指针区别
    • 顺序栈:指向栈顶的空白元素处,top-1才是指向栈顶元素
    • 链栈:指向栈顶实在的元素
  • 入栈
    • 顺序栈需要判断栈是否满,链栈不用
  • 出栈
    • 都需要判断栈是否空,链栈需要释放栈元素的空间

评论