stack

数据结构汇总之 stack

原文见 仓库

good good study, day day leetcode


  • 堆栈:具有一定操作约束的线性表,只能在一端作插入、删除
  • 具有后入先出的特性(Last In First Out)
  • 顺序存储结构、链式存储结构两种形式

以下是关于stack的总结。

一、栈的顺序存储结构

通常由一个一维数组和一个栈顶元素变量组成

图解如下:





形式一:构造结构体,设top值

0、结构初始化
1
2
3
4
5
#define MaxSize ###
struct StackNode {
ElementType Data[MaxSize];
int top;
};


1、建立空栈
1
2
3
4
5
6
struct StackNode* createStack() {
struct StackNode* s=malloc(sizeof(struct StackNode));
s->top=-1;

return s;
}


2、push操作
1
2
3
4
5
6
void push(struct StackNode* s,ElementType x) {
if (s->top!=MaxSize-1)
return s->Data[++(s->top)]=x;
else
return NULL;
}


3、pop操作
1
2
3
4
5
6
ElementType pop(struct StackNode* s) {
if (s->top!=-1)
return s->Data[(s->top)--];
else
return NULL;
}


4、peek操作
1
2
3
4
5
6
ElementType peek(struct StackNode* s) {
if (s->top!=-1)
return s->Data[s->top];
else
return NULL;
}



形式二:直接声明数组,在函数中构建堆栈

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
//举例020 Valid Parentheses 这一题
bool isValid(char* s) {
int len=strlen(s);
if (*s==NULL) return false;
if (len%2==1) return false;

char stack[1000000];
int top=-1;

while (*s) {
char c=*s;
if (c=='('||c=='{'||c=='[') {
stack[++top]=c;
}
else {
if (c==')'&&top>=0&&stack[top]=='(')
top--;
else if (c==']'&&top>=0&&stack[top]=='[')
top--;
else if (c=='}'&&top>=0&&stack[top]=='{')
top--;
}
s++;
}

return top==-1;
}




二、栈的链式存储结构(链栈)

  • 实际上是一个单链表
  • 插入、删除只能在栈的栈顶进行(栈顶指针不能在链尾!!

图解如下:



形式一:构造ListNode和StackNode

0、结构初始化
1
2
3
4
5
6
7
8
struct ListNode {
ElementType val;
struct ListNode* next;
};
struct StackNode {
int size;
struct ListNode* top;
};


1、建立空栈
1
2
3
4
5
6
struct StackNode* CreateStack() {
struct StackNode* s=malloc(sizeof(struct StackNode));
s->size=0;
s->top=NULL;
return s;
}


2、push操作
1
2
3
4
5
6
7
8
9
10
11
12
13
void push(struct StackNode* s,ElementType x) {
struct ListNode* temp=malloc(sizeof(struct ListNode));
temp->val=x;
temp->next=NULL;

if (s->size==0) s->top=temp;
else {
temp->next=s->top;
s->top=temp;
}

s->size++;
}


3、pop操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ElementType pop(struct StackNode* s) {
struct ListNode* temp;
ElementType tmp;

if (s->size==0) return NULL;
else {
temp=s->top;
s->top=temp->next;
tmp=s->top->val;
free(temp);

s->size--;
return tmp;
}
}


4、取栈顶元素
1
2
3
4
5
6
ElementType peek(struct StackNode* s) {
if (s&&s->top) {
return s->top->val;
}
return NULL;
}



形式二:仅仅构造StackNode(StackNode此时即为一个链表)

0、结构初始化
1
2
3
4
struct StackNode {
ElementType val;
struct ListNode* next;
};


1、建立空栈
1
2
3
4
5
6
struct StackNode* CreateStack() {
struct StackNode* s=malloc(sizeof(struct StackNode));
s->next=NULL

return s;
}


2、push操作
1
2
3
4
5
6
void push(struct StackNode* s,ElementType x) {
struct StackNode* temp=malloc(sizeof(struct StackNode));
temp->val=x;
temp->next=s->next;
s->next=temp;
}


3、pop操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ElementType pop(struct StackNode* s) {
struct StackNode* temp;
ElementType tmp;

if (s->next!=NULL) {
temp=s->next;
s->next=temp->next;
tmp=temp->val;

free(temp);
return tmp;
}
else
return NULL;
}


4、取栈顶元素
1
2
3
4
5
6
7
ElementType peek(struct StackNode* s) {
if (s->next!=NULL) {
return s->next->val;
}
else
return NULL;
}




三、栈的题型归纳

1、用栈处理符号/值/表达式
2、用栈处理链表/数组问题
3、二叉树遍历
4、矩形最大面积(难)
  • 最大矩形面积 [85 Maximal Rectangle]
  • 直方图中最大矩形 [84 Largest Rectangle in Histogram]

5、模拟简易计算器(难)
  • 简易计算器 [224 Basic Calculator]


-------------本文结束感谢您的阅读-------------