c栈

c语言实现栈

栈的理解

栈遵从（first in last out）原则，从栈顶弹出的元素是最后放入栈的元素。函数中递归的调用就利用了栈的数据结构。使用数组或链表可以模拟这一数据结构。

栈的实现

数组实现栈

虽然但是，c++stl里面都是有这些函数的，手写一遍只是为了了解底层的实现。

#include<stdio.h>
#define MAX_SIZE 101
int a[MAX_SIZE];
int top=-1;
void Push(int x)      //入栈
{
	if(top=MAX_SIZE-1)
	{
		printf("error");
		return;
	}
	top++;
	a[top]=x;
	
}
int Top(){
	return a[top];
}
void pop()                      //弹出栈顶元素
{
	if(top==-1)
	{
		printf("error");
		return;
	}
	else top--;
	
 } 
int main()
{
	Push(2);
	Push(3);
	pop();
}

链表实现栈

#include <stdio.h>
#include<string.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* next;
};
struct Node* top=NULL;
void Push(int x)
{
	struct Node* temp=(struct Node*)malloc(sizeof(struct Node)); 
	temp->next=top;
	temp->data=x;
	top=temp;
}
void Pop()
{
	struct Node* temp=top;
	if(top==NULL) return;
	top=top->next;
	free(temp);
}
void Print()
{
	struct Node* temp;
	temp=top;
	while(temp!=NULL)
	{
		printf("%d ",temp->data);
		temp=temp->next;
		
	}
}
int main()
{
	Push(1);
	Push(2);
	Push(3);
	Push(4);
	Pop();
	Print();
}

利用栈反转字符串

使用#include”stack” 内置函数

#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
void Reverse(char*c,int n)
{
	stack<char> S;                         //创建一个栈 S
	for(int i=0;i<n;i++)
	{
		S.push(c[i]);
	}
	for(int i=0;i<n;i++)
	{
		c[i]=S.top();
		S.pop();
		
	}
 } 
 int main()
 {
 	char c[100];
 	scanf("%s",c);
 	Reverse(c,strlen(c));
	 printf("%s",c); 
 }

利用栈反转一个链表

#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
struct Node{
	int data;
	struct Node* next;
};
struct Node* head; 
void Reverse(){
	if(head==NULL) return;
	stack<struct Node*> S;
	Node* temp=head;
	while(temp!=NULL)
	{
		S.push(temp);       //按链表顺序入栈 栈顶为链表最后一节点 
		temp=temp->next; 
		
	}
	temp=S.top();     //设置最后一个节点为head 
	head=temp;
	S.pop();            //弹栈 栈顶为链表前一个节点 
	while(!S.empty()){
		temp->next=S.top();     //改变指向 
		S.pop();                //弹栈 
		temp=temp->next;        //temp 前移 
	}
}

经典面试题，检查括号匹配

这让我想起来学校出的羊了个羊，也可以用栈实现,本质上都是使用了栈先入后出的结构特点。

#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool ArePair(char opening,char closing)
{
	if(opening == '(' && closing == ')') return true;
	else if(opening == '{' && closing == '}') return true;
	else if(opening == '[' && closing == ']') return true;
	return false;
}
bool AreParanthesesBalanced(string exp)
{
	stack<char>  S;
	for(int i =0;i<exp.length();i++)
	{
		if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
			S.push(exp[i]);                                                   //入栈 
		else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
		{
			if(S.empty() || !ArePair(S.top(),exp[i]))
				return false;
			else
				S.pop();
		}
	}
	return S.empty() ? true:false;            //总有人喜欢三目运算符 
}

int main()
{
	
	string expression;
	cout<<"Enter an expression:  "; 
	cin>>expression;
	if(AreParanthesesBalanced(expression))
		cout<<"Balanced\n";
	else
		cout<<"Not Balanced\n";
}