C高级编程 第十四天

目录

1. 栈的基本概念

2.栈的顺序存储

①初始化栈

②入栈

③出栈

④栈顶

⑤栈大小

⑥栈是否为空

⑦销毁栈

3.栈的链式存储

①初始化栈

②入栈

③出栈

④栈顶

⑤栈大小

⑥栈是否为空

⑦销毁栈

4.栈的就近匹配

---

1. 栈的基本概念

• 先进后出
• 入栈push
• 出栈pop
• 栈顶top
• 栈大小size
• 栈是否为空isEmpty
• 栈不允许遍历行为

2.栈的顺序存储

利用数组模拟出栈，先进后出的数据结构

#define max 1024
//栈的顺序存储struct SStack
{void* data[max];//栈中数组int m_size;		//栈大小
};typedef void* SeqStack;

①初始化栈

//初始化栈
SeqStack init_Stack()
{struct SStack* mystack = malloc(sizeof(struct SStack));if (mystack == NULL){return;}memset(mystack->data, 0, sizeof(void*) * max);mystack->m_size = 0;return mystack;
}

②入栈

//入栈
void push_Stack(SeqStack stack, void* data)
{//本质，数组的尾差if (stack == NULL || data == NULL){return;}struct SStack* mystack = stack;//栈满时if (mystack->m_size == max){return;}mystack->data[mystack->m_size] = data;//尾插mystack->m_size++;//更新栈大小
}

③出栈

//出栈
void pop_Stack(SeqStack stack)
{//数组尾删除if (stack == NULL){return;}struct SStack* mystack = stack;//栈空时if (mystack->m_size == 0){return;}printf("%d\n", mystack->data[mystack->m_size]);free(mystack->data[mystack->m_size-1]);mystack->data[mystack->m_size-1] = NULL;mystack->m_size--;
}

④栈顶

//返回栈顶
SeqStack top_Stack(SeqStack stack)
{//本质 访问数组尾元素if (stack == NULL){return;}struct SStack* mystack = stack;//栈空时if (mystack->m_size == 0){return NULL; }SeqStack a = mystack->data[mystack->m_size - 1];return a;
}

⑤栈大小

//返回栈大小
int size_Stack(SeqStack stack)
{if (stack == NULL){return;}struct SStack* mystack = stack;int mysize = mystack->m_size;return mysize;
}

⑥栈是否为空

//判断栈是否为空
int isEmpty_Stack(SeqStack stack)
{if (stack == NULL){return 1;}struct SStack* mystack = stack;if (mystack->m_size == 0){return 1;}return 0;
}

⑦销毁栈

//销毁
void destroy_Stack(SeqStack stack)
{if (stack == NULL){return NULL;}struct SStack* mystack = stack;if (mystack->data != NULL){free(mystack->data);}free(mystack);mystack = NULL;
}

3.栈的链式存储

链表头节点做栈顶，用于进出数据

struct LinkNode
{//只维护指针域struct LinkNode* next;
};struct LStack
{struct LinkNode pHeader;	//头节点，在栈顶int m_size;		//栈大小
};typedef void* LinkStack;

①初始化栈

//初始化栈
LinkStack init_Stack()
{struct LStack* myStack = malloc(sizeof(struct LStack));if (myStack == NULL){return NULL;}myStack->pHeader.next = NULL;myStack->m_size = 0;return myStack;
}

②入栈

//入栈
void push_Stack(LinkStack stack, void* data)
{//本质是链表的头插if (stack == NULL || data == NULL){return NULL;}struct LStack* myStack = stack;struct LinkNode* myNode = data;myNode->next = myStack->pHeader.next;myStack->pHeader.next = myNode;myStack->m_size++;
}

③出栈

//出栈
void pop_Stack(LinkStack stack)
{if (stack == NULL){return NULL;}struct LStack* myStack = stack;struct LinkNode* myNode = myStack->pHeader.next;//栈空时if (myNode == NULL){return NULL;}printf("%d", myNode->next);myStack->pHeader.next = myNode->next;free(myNode);myNode = NULL;myStack->m_size--;
}

④栈顶

//返回栈顶
LinkStack top_Stack(LinkStack stack)
{//本质 返回链表的第一个元素if (stack == NULL){return NULL;}struct LStack* myStack = stack;int size = myStack->m_size;return size;
}

⑤栈大小

//返回栈大小
int size_Stack(LinkStack stack)
{//本质 返回链表大小if (stack == NULL){return 0;}struct LStack* myStack = stack;struct LinkNode* myNode = myStack->pHeader.next;int size = 0;if (myNode->next == NULL){return size;}else{size++;}
}

⑥栈是否为空

//判断栈是否为空
int isEmpty_Stack(LinkStack stack)
{if (stack == NULL){return 1;}struct LStack* myStack = stack;if (myStack->m_size == 0){return 1;}return 0;
}

⑦销毁栈

//销毁栈
void destroy_Stack(LinkStack stack)
{if (stack == NULL){return NULL;}struct LStack* myStack = stack;free(myStack);myStack = NULL;
}

4.栈的就近匹配

5+5*（6）+9/3*1）-（1+3（）

①从第一个字符开始扫描

②遇见普通字符忽略

③遇见左括号，压入栈中

④遇见右括号，从栈中弹出栈顶符号，并匹配

⑤匹配成功：继续读入下个字符；匹配失败：立即停止，并报错

⑥结束标志：

成功-所有字符扫描完毕，栈为空

失败-匹配失败，或，字符扫描完毕，但栈非空