2019 September 03 CPP基础

C/CPP与数据结构-第二节 栈tack和队列queue （一）

栈stack

  1. 基本概念：
    1. 栈是一种特殊的线性表
    2. 栈仅能在线性表的一端进行操作
      1. 栈顶(Top)：允许操作的一端
      2. 栈底(Bottom)：不允许操作的一端
    3. 栈的插入操作，叫做进栈，也称压栈、入栈。类似子弹入弹夹
    4. 栈的删除操作，叫做出栈，也有的叫做弹栈。如同弹夹中的子弹出夹

  2. stack的常用操作

     #ifndef _MY_STACK_H_
 #define _MY_STACK_H_
    
 typedef void Stack;
 //创建栈
 Stack* Stack_Create();
 //销毁栈
 void Stack_Destroy(Stack* stack);
 //清空栈
 void Stack_Clear(Stack* stack);
 //进栈
 int Stack_Push(Stack* stack, void* item);
 //出栈
 void* Stack_Pop(Stack* stack);
 //获取栈顶元素
 void* Stack_Top(Stack* stack);
 //获取栈的大小 
 int Stack_Size(Stack* stack);
    
 #endif //_MY_STACK_H_

栈的顺序存储设计与实现

  1. 技术分析：
    1. 可以直接用线性表的顺序存储来实现
    2. 那么是头部插入还是尾部插入呢？
      1. 头部插入，需要把原来的每个结点都要后移一位，耗时，因此尾部插入最好
    3. 弹出、压入栈，就相当于线性表顺序存储删除、加入最后一个节点

  2. 代码示例：

     //seqstack.h文件
 #ifndef _MY_STACK_H_
 #define _MY_STACK_H_
    
 typedef void SeqStack;
    
 SeqStack* SeqStack_Create(int capacity);
    
 void SeqStack_Destroy(SeqStack* stack);
    
 void SeqStack_Clear(SeqStack* stack);
    
 int SeqStack_Push(SeqStack* stack, void* item);
    
 void* SeqStack_Pop(SeqStack* stack);
    
 void* SeqStack_Top(SeqStack* stack);
    
 int SeqStack_Size(SeqStack* stack);
    
 int SeqStack_Capacity(SeqStack* stack);
 #endif //_MY_STACK_H_
    
 //seqstack.c文件
 #define _CRT_SECURE_NO_WARNINGS
 #include<stdlib.h>
 #include<string.h>
 #include<stdio.h>
 #include"seqstack.h"
 #include"seqlist.h"//线性表的顺序存储
    
 //创建栈相当于创建一个线性表
 SeqStack* SeqStack_Create(int capacity) {
    	
 	return SeqList_Create(capacity);;
 }
 //销毁栈相当于销毁一个线性表
 void SeqStack_Destroy(SeqStack* stack) {
    
 	 SeqList_Destroy(stack);
 }
    
 //清空栈相当于清空线性表
 void SeqStack_Clear(SeqStack* stack) {
    
 	 SeqList_Clear(stack);
 }
    
 //栈插入元素，相当于在线性表的尾部添加元素
 int SeqStack_Push(SeqStack* stack, void* item) {
    
 	return SeqList_Insert(stack, item, SeqList_Length(stack));
 }
 //栈弹出元素，相当于从线性表的尾部删除元素
 void* SeqStack_Pop(SeqStack* stack) {
    
 	return SeqList_Delete(stack, SeqList_Length(stack)-1);;
 }
    
 //获取栈顶部元素，相当于获取线性表的尾部元素
 void* SeqStack_Top(SeqStack* stack) {
    
 	return SeqList_Get(stack, SeqList_Length(stack)-1);
 }
 //栈的大小，线性表的长度
 int SeqStack_Size(SeqStack* stack) {
    
 	return SeqList_Length(stack);
 }
    
 //栈的容量，相当于线性表的容量
 int SeqStack_Capacity(SeqStack* stack) {
    	
 	return SeqList_Capacity(stack);
 }
    
 //main.c使用
 #define _CRT_SECURE_NO_WARNINGS
 #include<stdlib.h>
 #include<string.h>
 #include<stdio.h>
 #include"seqstack.h"
    
 void main() {
 	int i = 0;
 	int a[10];
 	SeqStack *stack = NULL;
 	for (i = 0; i < 10; i++)
 	{
 		a[i] = i + 1;
 	}
 	//创建栈
 	stack = SeqStack_Create(10);
 	//往栈中压入数据
 	for ( i = 0; i < 10; i++)
 	{
 		SeqStack_Push(stack, &a[i]);
 	}
 	//栈的属性
 	printf("len:%d \n", SeqStack_Size(stack));
 	printf("capacity:%d \n",SeqStack_Capacity(stack));
    
 	printf("top:%d \n", *((int *)SeqStack_Top(stack)));
    
 	//元素出栈
 	while (SeqStack_Size(stack)>0)
 	{
 		printf("pop:%d \n", *((int *)SeqStack_Pop(stack)));
 	}
 	//销毁栈
 	SeqStack_Destroy(stack);
    
 	system("pause");
 	return;
 }

栈的链式存储设计与实现

  1. 技术分析
    1. 同栈的顺序存储相似，栈的链式存储也可以用线性表的链式存储来做
    2. 那么是头部插入还是尾部插入呢？
      1. 尾部插入需要遍历到尾部然后再插入，比较耗时
      2. 因此采用头部插入最好
    3. 注意点：
      1. 由于栈的节点跟链表的节点数据类型不一样，因此需要将栈的节点适配成链表的节点
      2. 注意内存管理

  2. 代码实现

     //linkstack.h文件
 #ifndef _MY_LINKSTACK_H_
 #define _MY_LINKSTACK_H_
    
 typedef void LinkStack;
    
 LinkStack* LinkStack_Create();
    
 void LinkStack_Destroy(LinkStack* stack);
    
 void LinkStack_Clear(LinkStack* stack);
    
 int LinkStack_Push(LinkStack* stack, void* item);
    
 void* LinkStack_Pop(LinkStack* stack);
    
 void* LinkStack_Top(LinkStack* stack);
    
 int LinkStack_Size(LinkStack* stack);
    
 #endif //_MY_LINKSTACK_H_
    
 //linkstack.c文件
 #define _CRT_SECURE_NO_WARNINGS
 #include<stdlib.h>
 #include<string.h>
 #include<stdio.h>
 #include"linkstack.h"
 #include"LinkList.h"
    
 //用于适配链表节点
 typedef struct _tag_LinkStack
 {
 	LinkListNode *node;
 	void *item;
    
 }TLinkStack;
    
    
 //创建一个栈相当于创建一个线性表
 LinkStack* LinkStack_Create() {
    
 	return LinkList_Create();
 }
    
 void LinkStack_Destroy(LinkStack* stack) {
 	//先释放栈中的所有节点
 	LinkStack_Clear(stack);
 	//再释放句柄
 	LinkList_Destroy(stack);
 }
    
 void LinkStack_Clear(LinkStack* stack) {
 	while (LinkList_Length(stack)>0)
 	{
 		TLinkStack *tem = (TLinkStack*) LinkStack_Pop(stack);
 	}
 	return;
 }
    
    
 //向栈中添加元素，相当于向线性链表插入元素
 int LinkStack_Push(LinkStack* stack, void* item) {
 	int ret = 0;
 	//注意点！！！：栈节点转换为链表节点 
 	TLinkStack *tem = NULL;
 	tem = malloc(sizeof(TLinkStack));
 	tem->item = item;
 	ret = LinkList_Insert(stack, (LinkListNode*)tem, 0);
    	
 	if (ret != 0)
 	{
 		printf("func LinkList_Insert() err:%d \n ", ret);
 		free(tem);
 	}
 	return ret;
 }
    
 //重栈中弹出元素相当于线性链表中删除0号位置元素
 void* LinkStack_Pop(LinkStack* stack) {
 	TLinkStack *tem = NULL;
 	void *item = NULL;
 	tem =(TLinkStack*) LinkList_Delete(stack, 0);
 	if (tem == NULL)
 	{
 		return NULL;
 	}
 	item = tem->item;
 	//内存管理
 	free(tem);
    
 	return item;
 }
    
 //获取栈顶元素相当于获取线性链表的0号位置元素
 void* LinkStack_Top(LinkStack* stack) {
 	TLinkStack *tem = NULL;
 	tem = (TLinkStack*)LinkList_Get(stack, 0);
 	if (tem == NULL)
 	{
 		return NULL;
 	}
 	return tem->item;
 }
    
 int LinkStack_Size(LinkStack* stack) {
    
 	return LinkList_Length(stack);
 }
    
 //main.c文件
 #define _CRT_SECURE_NO_WARNINGS
 #include<stdlib.h>
 #include<string.h>
 #include<stdio.h>
 #include"linkstack.h"
    
    
 void main() {
 	int a[5];
 	LinkStack *stack = NULL;
 	for (int  i = 0; i < 5; i++)
 	{
 		a[i] = i + 1;
 	}
 	stack = LinkStack_Create();
 	//压栈
 	for (int  i = 0; i < 5; i++)
 	{
 		//将栈的节点转换为链表的节点
 		LinkStack_Push(stack, &a[i]);
 	}
 	//栈的属性
 	printf("len: %d \n", LinkStack_Size(stack));
 	printf("top: %d \n",*((int *)LinkStack_Top(stack)));
    
 	//出栈
 	while (LinkStack_Size(stack)>0)
 	{
 		printf("pop: %d \n", *((int *)LinkStack_Pop(stack)));
 	}
    
 	//销毁
 	LinkStack_Destroy(stack);
    
 	system("pause");
 	return;
 }

栈的应用

  1. 就近匹配
    1. 几乎所有的编译器都具有检测括号是否匹配的能力

    2. 如何实现编译器中的符号成对检测？

       #include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0;
    3. 算法思路
      1. 从第一个字符开始扫描
      2. 当遇见普通字符时忽略，
      3. 当遇见左符号时压入栈中
      4. 当遇见右符号时从栈中弹出栈顶符号，并进行匹配
      5. 匹配成功：继续读入下一个字符
      6. 匹配失败：立即停止，并报错
      7. 结束：
        1. 成功: 所有字符扫描完毕，且栈为空
        2. 失败：匹配失败或所有字符扫描完毕但栈非空
    4. 当需要检测成对出现但又互不相邻的事物时,可以使用栈“后进先出”的特性,栈非常适合于需要“就近匹配”的场合
  2. 中缀表达式和后缀表达式
    1. 计算机的本质工作就是做数学运算，那计算机可以读入字符串9 + (3 - 1) * 5 + 8 / 2并计算值吗？
    2. 后缀表达式与中缀表达式
      1. 波兰科学家在20世纪50年代提出了一种将运算符放在数字后面的后缀表达式对应的，我们习惯的数学表达式叫做中缀表达式===》符合人类思考习惯
      2. 中缀表达式符合人类的阅读和思维习惯
      3. 后缀表达式符合计算机的“运算习惯”
      4. 如何将中缀表达式转换成后缀表达式？
    3. 中缀转后缀算法：
      1. 遍历中缀表达式中的数字和符号
      2. 对于数字：直接输出
      3. 对于符号：
        1. 左括号：进栈
        2. 运算符号：与栈顶符号进行优先级比较
          1. 若栈顶符号优先级低：此符合进栈 （默认栈顶若是左括号，左括号优先级最低）
          2. 若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
        3. 右括号：将栈顶符号弹出并输出，直到匹配左括号
      4. 遍历结束：将栈中的所有符号弹出并输出

    4. 下面示例如下：（可以手动试一下）

       5 + 4=> 5 4 +  
 1 + 2 * 3 => 1 2 3 * +  
 8 + ( 3 – 1 ) * 5 => 8 3 1 – 5 * +
    5. 那么计算机是如何基于后缀表达式计算的呢？
      1. 遍历后缀表达式中的数字和符号
      2. 对于数字：进栈
      3. 对于符号：
        1. 从栈中弹出右操作数
        2. 从栈中弹出左操作数
        3. 根据符号进行运算
        4. 将运算结果压入栈中
      4. 遍历结束：栈中的唯一数字为计算结果 结果为18

      5. 举例： 8 3 1 – 5 * + 

                   栈值   弹出右  弹出左   计算压栈   
 第一次遍历  831   -1     3-1     2
 第二次遍历  82    *5     2*5     10
 第三次遍历  810   +10    8+10    18
 遍历结束    18
  3. 代码示例：

    1. 就近原则

       #include "stdio.h"
 #include "stdlib.h"
 #include "linkstack.h"
        
 int isLeft(char c)
 {
 	int ret = 0;
        
 	switch(c)
 	{
 	case '<':
 	case '(':
 	case '[':
 	case '{':
 	case '\'':
 	case '\"':
 		ret = 1;
 		break;
 	default:
 		ret = 0;
 		break;
 	}
        
 	return ret;
 }
        
 int isRight(char c)
 {
 	int ret = 0;
        
 	switch(c)
 	{
 	case '>':
 	case ')':
 	case ']':
 	case '}':
 	case '\'':
 	case '\"':
 		ret = 1;
 		break;
 	default:
 		ret = 0;
 		break;
 	}
        
 	return ret;
 }
        
 int match(char left, char right)
 {
 	int ret = 0;
        
 	switch(left)
 	{
 	case '<':
 		ret = (right == '>');
 		break;
 	case '(':
 		ret = (right == ')');
 		break;
 	case '[':
 		ret = (right == ']');
 		break;
 	case '{':
 		ret = (right == '}');
 		break;
 	case '\'':
 		ret = (right == '\'');
 		break;
 	case '\"':
 		ret = (right == '\"');
 		break;
 	default:
 		ret = 0;
 		break;
 	}
        
 	return ret;
 }
        
 int scanner(const char* code)
 {
 	LinkStack* stack = LinkStack_Create();
 	int ret = 0;
 	int i = 0;
        
 	while( code[i] != '\0' )
 	{
 		if( isLeft(code[i]) )
 		{
 			LinkStack_Push(stack, (void*)(code + i)); //&code[i]
 		}
        
 		if( isRight(code[i]) )
 		{
 			char* c = (char*)LinkStack_Pop(stack);
        
 			if( (c == NULL) || !match(*c, code[i]) )
 			{
 				printf("%c does not match!\n", code[i]);
 				ret = 0;
 				break;
 			}
 		}
        
 		i++;
 	}
        
 	if( (LinkStack_Size(stack) == 0) && (code[i] == '\0') )
 	{
 		printf("Succeed!\n");
 		ret = 1;
 	}
 	else
 	{
 		printf("Invalid code!\n");
 		ret = 0;
 	}
        
 	LinkStack_Destroy(stack); 
        
 	return ret;
 }
        
 void main()
 {
 	const char* code = "#include <stdio.h> int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0; ";
        
 	scanner(code);
 	system("pause");
 	return ;
 }

    2. 中缀转后缀

       #include "stdio.h"
 #include "stdlib.h"
 #include "string.h"
 #include "linkstack.h"
        
 int isNumber(char c)
 {
 	return ('0' <= c) && (c <= '9');
 }
        
 int isOperator(char c)
 {
 	return (c == '+') || (c == '-') || (c == '*') || (c == '/');
 }
        
 int isLeft(char c)
 {
 	return (c == '(');
 }
        
 int isRight(char c)
 {
 	return (c == ')');
 }
        
 int priority(char c)
 {
 	int ret = 0;
        
 	if( (c == '+') || (c == '-') )
 	{
 		ret = 1;
 	}
        
 	if( (c == '*') || (c == '/') )
 	{
 		ret = 2;
 	}
        
 	return ret;
 }
        
 void output(char c)
 {
 	if( c != '\0' )
 	{
 		printf("%c", c);
 	}
 }
        
 //  
 void transform(const char* exp)
 {
 	int i = 0;
 	LinkStack* stack = LinkStack_Create();
        
 	while( exp[i] != '\0' )
 	{
 		if( isNumber(exp[i]) )
 		{
 			output(exp[i]);
 		}
 		else if( isOperator(exp[i]) )
 		{
 			while( priority(exp[i]) <= priority((char)(int)LinkStack_Top(stack)) )
 			{
 				output((char)(int)LinkStack_Pop(stack));
 			}
        
 			LinkStack_Push(stack, (void*)(int)exp[i]);
 		} 
 		else if( isLeft(exp[i]) )
 		{
 			LinkStack_Push(stack, (void*)(int)exp[i]);
 		} 
 		else if( isRight(exp[i]) )
 		{
 			//char c = '\0';
 			while( !isLeft( (char)(int)LinkStack_Top(stack) ) )
 			{
 				output((char)(int)LinkStack_Pop(stack));
 			}
        
 			LinkStack_Pop(stack);
 		}
 		else
 		{
 			printf("Invalid expression!");
 			break;
 		}
        
 		i++;
 	}
        
 	while( (LinkStack_Size(stack) > 0) && (exp[i] == '\0') )
 	{
 		output((char)(int)LinkStack_Pop(stack));
 	}
        
 	LinkStack_Destroy(stack);
 }
        
 int main()
 {
 	transform("8+(3-1)*5");
        
 	printf("\n");
 	system("pause");
 	return 0;
 }

    3. 后缀计算

       #include <stdio.h>
 #include "LinkStack.h"
        
 int isNumber3(char c)
 {
 	return ('0' <= c) && (c <= '9');
 }
        
 int isOperator3(char c)
 {
 	return (c == '+') || (c == '-') || (c == '*') || (c == '/');
 }
        
 int value(char c)
 {
 	return (c - '0');
 }
        
 int express(int left, int right, char op)
 {
 	int ret = 0;
        
 	switch(op)
 	{
 	case '+':
 		ret = left + right;
 		break;
 	case '-':
 		ret = left - right;
 		break;
 	case '*':
 		ret = left * right;
 		break;
 	case '/':
 		ret = left / right;
 		break;
 	default:
 		break;
 	}
        
 	return ret;
 }
        
 int compute(const char* exp)
 {
 	LinkStack* stack = LinkStack_Create();
 	int ret = 0;
 	int i = 0;
        
 	while( exp[i] != '\0' )
 	{
 		if( isNumber3(exp[i]) )
 		{
 			LinkStack_Push(stack, (void*)value(exp[i]));
 		}
 		else if( isOperator3(exp[i]) )
 		{
 			int right = (int)LinkStack_Pop(stack);
 			int left = (int)LinkStack_Pop(stack);
 			int result = express(left, right, exp[i]);
        
 			LinkStack_Push(stack, (void*)result);
 		}
 		else
 		{
 			printf("Invalid expression!");
 			break;
 		}
        
 		i++;
 	}
        
 	if( (LinkStack_Size(stack) == 1) && (exp[i] == '\0') )
 	{
 		ret = (int)LinkStack_Pop(stack);
 	} 
 	else 
 	{
 		printf("Invalid expression!");
 	}
        
 	LinkStack_Destroy(stack);
        
 	return ret;
 }
        
 int main()
 {
 	printf("8 + (3 - 1) * 5  = %d\n", compute("831-5*+"));
 	system("pause");
 	return 0;
 }

All content is licensed under CC BY-NC-SA

Buit with Jekyll and 3-Jekyll theme • Hosted on Github

Table of Contents