栈是一种后进先出(Last In First Out)的线性表。
栈的基本操作只有两个：
- 入栈(push)：即将数据保存在栈顶。进行该操作前，先修改栈顶指针，使其向上移动一个元素位置，然后将数据保存在栈顶指针所指向的位置。
- 出栈(pop)：即将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。
在栈中，只有栈顶元素是可以访问的。
#define MAX_SIZE 100
typedef char ElemType;
typedef struct
{
ElemType data[MAX_SIZE];
int top;
}Stack;
//初始化栈
void initStack(Stack *&S)
{
S=(Stack *)malloc(sizeof(Stack));
S->top=-1;
}
//元素进栈
int push(Stack *&S,ElemType e)
{
if(S->top==MAX_SIZE-1) return 0;
S->top++;
S->data[S->top]=e;
return 1;
}
//出栈
int pop(Stack *&S)
{
if(S->top==-1) return 0;
ElemType e=S->data[S->top];
S->top--;
return e;
}
//输出栈表
void disPlay(Stack *S)
{
int i;
for(i=S->top;i>=0;i--)
printf("%c ",S->data[i]);
}
用两个栈实现队列和用两个队列实现一个栈
题目：用两个栈实现一个队列。队列的生命如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
参考代码
#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;
template <typename T>class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendtail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
//构造函数
template <typename T> CQueue<T>::CQueue(void)
{
}
//析构函数
template <typename T> CQueue<T>::~CQueue(void)
{
}
//插入元素
template <typename T> void CQueue<T>::appendtail(const T& node)
{
stack1.push(node);
}
//删除元素并返回
template <typename T> T CQueue<T>::deleteHead()
{
if(stack2.size()<=0)
{
while(stack1.size()>0)
{
stack2.push(stack1.top());
stack1.pop();
}
}
if(stack2.size()==0)
throw new exception("队列为空");
T head=stack2.top();
stack2.pop();
return head;
}
void main()
{
CQueue<int> queue;
queue.appendtail(1);
queue.appendtail(2);
queue.appendtail(3);
queue.appendtail(4);
int len=4;
while(len>0)
{
cout<<queue.deleteHead()<<endl;
--len;
}
system("pause");
}
2. 使用两个队列实现一个栈
参考代码
#include<iostream>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
template <typename T>class CStack
{
public:
CStack(void){};
~CStack(void){};
void push(const T& node);
T pop();
private:
queue<T> queue1;
queue<T> queue2;
};
//插入元素
template <typename T> void CStack<T>::push(const T& element)
{
if(queue1.size()>0)//如果queue1不为空则往queue1中插入元素
queue1.push(element);
else if(queue2.size()>0)//如果queue2不为空则往queue2中插入元素
queue2.push(element);
else//如果两个队列都为空，则往queue1中插入元素
queue1.push(element);
}
//删除元素
template <typename T> T CStack<T>::pop()
{
if(queue1.size()==0)//如果queue1为空
{
//保证queue2中有一个元素，将其余元素保存到queue1中
while(queue2.size()>1)
{
queue1.push(queue2.front());
queue2.pop();
}
T& data=queue2.front();
queue2.pop();
return data;
}
else//如果queue2为空
{
//保证queue2中有一个元素，将其余元素保存到queue1中
while(queue1.size()>1)
{
queue2.push(queue1.front());
queue1.pop();
}
T& data=queue1.front();
queue1.pop();
return data;
}
}
void main()
{
CStack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
int len=4;
while(len>0)
{
cout<<stack.pop()<<" ";
--len;
}
system("pause");
}
3. 利用一个栈倒序另外一个栈中的数
参考代码
#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;
template <typename T> void ReverseOrder(stack<T> &s1,stack<T> &s2)
{
s1.push(5);
s1.push(4);
s1.push(3);
s1.push(2);
s1.push(1);
int sortNum=0;
int oriStackSize=s1.size();
while(sortNum<oriStackSize)
{
int temp=s1.top();
s1.pop();
while(s1.size()-sortNum>0)
{
s2.push(s1.top());
s1.pop();
}
//首元素存入s1
s1.push(temp);
++sortNum;
while(!s2.empty())
{
s1.push(s2.top());
s2.pop();
}
}
cout<<"逆序栈输出："<<endl;
while(!s1.empty())
{
cout<<s1.top()<<endl;
s1.pop();
}
}
void main()
{
stack<int> s1;
stack<int> s2;
ReverseOrder(s1,s2);
system("pause");
}
4. 铁轨
某城市有一个火车站，铁轨铺设如图所示。有n节车厢从A方向驶入车站，按进站顺序编号1～n。现让这些火车按照某种特定的顺序进入B方向的铁轨并驶出车站。 为了重组车厢，可以借助中转站C。C是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，一旦从A移入C，就不能再回到A了；一旦从C移入B，就不能回到C了。换句话说，在任意时刻，只有两种选择：A→C和C→B。请编程判断判断：按给定的出站顺序，火车能否出站。
参考代码
#include <iostream>
#include <stack>
using namespace std;
const int N=100;
int main()
{
int n,i;
stack<char > stack;
cin>>n;
int num[N];
for(i=1;i<=n;i++)
cin>>num[i];
int A=1,B=1,ok=1;
while(B<=n)
{
if(A==num[B])
{
A++;
B++;
}
else if(!stack.empty() && stack.top()==num[B])
{
stack.pop();
B++;
}else if(A<=n)
{
stack.push(A);
A++;
}else
{
ok=0;
break;
}
}
if(ok==1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
5. 进制转换
参考代码
void conversion(int N,int d)
{
stack<int > stack;
while(N)
{
stack.push(N%d);
N=N/d;
}
while(!stack.empty())
{
cout<<stack.top()<<" ";
stack.pop();
}
}
6. 括号匹配 （栈）
参考代码
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool judge_bracket(string str)
{
int i;
char ch;
stack<char > stack;
for(i=0;i<str.length();i++)
{
switch(ch=str[i])
{
case '(': stack.push(ch);
break;
case ')': if(stack.top()=='(')
stack.pop();
else
return false;
break;
case '[': stack.push(ch);
break;
case ']': if(stack.top()=='[')
stack.pop();
else
return false;
break;
case '{': stack.push(ch);
break;
case '}': if(stack.top()=='{')
stack.pop();
else
return false;
break;
default : break;
}
}
return true;
}
int main()
{
string str;
cin>>str;
if(judge_bracket(str)) cout<<"匹配成功!"<<endl;
else cout<<"匹配不成功!"<<endl;
return 0;
}
