005——栈

目录

栈

栈的定义

栈的性质

栈的应用场景

存储结构：

Ⅰ）采用顺序存储结构实现——顺序栈

Ⅱ）采用链式存储结构实现——链栈-->基于单链表（带头结点）

---

栈

栈的定义

之允许在一端进行插入和删除的线性表

栈的定义

栈的性质

先进后出

栈的应用场景

1.函数调用的实现

2.倒着走的逻辑：如历史记录、撤销等

3.内存中的堆栈

4.STL库中的stack

存储结构：

Ⅰ）采用顺序存储结构实现——顺序栈

比如我们申请一个十个大小的int数组，并随机存储一些数据

#define maxsize 10

这里需要注意：有时候为了方便描述，通常会借用“指针”两个字来称呼那个用于标记的变量

初始化：top=-1;栈顶我们用top指针指示（注意这里的指针不是真的指针），初始化时top=-1

Stack initStack(){Stack s;s.data = (int*)malloc(sizeof(int) * maxsize);if (s.data == NULL) {printf("空间分配失败\n");}s.top = -1;return s;
}

入栈：top++;a[top]=k//或者写成a[++top]=k;

void Push(Stack* s, int k) {if (isFull(s) == 1) {printf("栈满");}else {s->top++;s->data[s->top] = k;}}

出栈：top--;//top--之前的数据在出栈后会变成脏数据，所以不需要理会

void Pop(Stack* s) {if (isEmpty(s) == 1){printf("栈空，不能出栈\n");}else{s->top--;}
}

判满：top==maxsize-1;的时候栈满

int isFull(Stack* s) {if (s->top == maxsize - 1) {return 1;}return 0;
}

判空：top==-1;top指向-1

int isEmpty(Stack* s)
{if (s->top == -1){return 1;}return 0;
}

获取栈顶数据：x = a[top];

int getTop(Stack s)
{if (isEmpty(&s) == 1){printf("栈空，没有数据\n");return -1;//特殊值 }return s.data[s.top];
}

整体代码示例： 

#include<stdlib.h>
#include<stdio.h>
#define maxsize 10
typedef struct {int* data;int top;
}Stack;Stack initStack(){Stack s;s.data = (int*)malloc(sizeof(int) * maxsize);if (s.data == NULL) {printf("空间分配失败\n");}s.top = -1;return s;
}
int isFull(Stack* s) {if (s->top == maxsize - 1) {return 1;}return 0;
}
void Push(Stack* s, int k) {if (isFull(s) == 1) {printf("栈满");}else {s->top++;s->data[s->top] = k;}}
int isEmpty(Stack* s)
{if (s->top == -1){return 1;}return 0;
}
void Pop(Stack* s) {if (isEmpty(s) == 1){printf("栈空，不能出栈\n");}else{s->top--;}
}int getTop(Stack s)
{if (isEmpty(&s) == 1){printf("栈空，没有数据\n");return -1;//特殊值 }return s.data[s.top];
}
int main() {Stack s= initStack();printf("%d\n", getTop(s));Push(&s, 1);printf("%d\n", getTop(s));Push(&s, 2);printf("%d\n", getTop(s));Push(&s, 3);printf("%d\n", getTop(s));Pop(&s);printf("%d\n", getTop(s));}

初始化：top=0;//这个时候top标记的时真正的栈顶元素的上面一个位置

入栈：a[top]=k；top++;//或者写成a[top++]=k;

出栈：top--;

判满：top==maxsize;的时候栈满

判空：top==0;top指向0

获取栈顶数据：x = a[top-1];

Ⅱ）采用链式存储结构实现——链栈-->基于单链表（带头结点）

初始化：初始化一个带头结点的空链表

入栈：直接用头插法，则栈顶一直时首元结点，就直接用头指针做栈顶指针

linkstack initstack()
{linkstack s = (StackNode*)malloc(sizeof(StackNode));if (s == NULL){printf("空间分配失败\n");}s->next = NULL;return s;
}

删除：删除首元结点

linkstack Pop(linkstack top)
{//出栈 删除首元节点 if (isEmpty(top) == 1){printf("栈空，不能出栈\n");}else{StackNode* p = top->next;top->next = p->next;free(p);p = NULL;}return top;
}

判满：链表不需要判满

判空：L->next==NULL;

int isEmpty(linkstack top)
{if (top->next == NULL){return 1;}return 0;
}

 整体代码示例：

#include<stdio.h>
#include<stdio.h>
#include<stdlib.h>
#define maxsize 10 
//链栈---基于带头结点的单链表实现
typedef struct StackNode {int data;struct StackNode* next;
}StackNode, * linkstack;
linkstack initstack()
{linkstack s = (StackNode*)malloc(sizeof(StackNode));if (s == NULL){printf("空间分配失败\n");}s->next = NULL;return s;
}
linkstack Push(linkstack top, int k)
{//入栈 头插法 linkstack s = (StackNode*)malloc(sizeof(StackNode));if (s == NULL){printf("空间分配失败\n");return top;}s->data = k;s->next = top->next;top->next = s;return  top;
}
int isEmpty(linkstack top)
{if (top->next == NULL){return 1;}return 0;
}
linkstack Pop(linkstack top)
{//出栈 删除首元节点 if (isEmpty(top) == 1){printf("栈空，不能出栈\n");}else{StackNode* p = top->next;top->next = p->next;free(p);p = NULL;}return top;
}
int getTop(linkstack top)
{if (isEmpty(top) == 1){printf("栈空，没有数据\n");return -1;//特殊值 }else{return top->next->data;}
}
int main()
{linkstack top = initstack();top = Push(top, 1);printf("%d\n", getTop(top));top = Push(top, 2);top = Push(top, 3);printf("%d\n", getTop(top));top = Pop(top);printf("%d\n", getTop(top));return 0;
}