[关闭]
@yudesong 2017-06-24T14:51:58.000000Z 字数 4465 阅读 612

栈

栈 yudesong 2017/6/24

栈是一种后进先出(Last In First Out)的线性表。

栈的基本操作只有两个：
1. 入栈(push)：即将数据保存在栈顶。进行该操作前，先修改栈顶指针，使其向上移动一个元素位置，然后将数据保存在栈顶指针所指向的位置。
2. 出栈(pop)：即将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。
在栈中，只有栈顶元素是可以访问的。

  1. #define MAX_SIZE 100
  2. typedef char ElemType;
  3. typedef struct
  4. {
  5.     ElemType data[MAX_SIZE];
  6.     int top;
  7. }Stack;
  8. //初始化栈
  9. void initStack(Stack *&S)
  10. {
  11.     S=(Stack *)malloc(sizeof(Stack));
  12.     S->top=-1;
  13. }
  14. //元素进栈
  15. int push(Stack *&S,ElemType e)
  16. {
  17.     if(S->top==MAX_SIZE-1) return 0;
  18.     S->top++;
  19.     S->data[S->top]=e;
  20.     return 1;
  21. }
  22. //出栈
  23. int pop(Stack *&S)
  24. {
  25.     if(S->top==-1) return 0;
  26.     ElemType e=S->data[S->top];
  27.     S->top--;
  28.     return e;
  29. }
  30. //输出栈表
  31. void disPlay(Stack *S)
  32. {
  33.     int i;
  34.     for(i=S->top;i>=0;i--)
  35.     printf("%c ",S->data[i]);
  36. }
面试题1：用两个栈实现队列和用两个队列实现一个栈

题目：用两个栈实现一个队列。队列的生命如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。

参考代码

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<stack>
  4. using namespace std;
  6. template <typename T>class CQueue
  7. {
  8. public:
  9.     CQueue(void);
  10.     ~CQueue(void);
  11.     void appendtail(const T& node);
  12.     T deleteHead();
  13. private:
  14.     stack<T> stack1;
  15.     stack<T> stack2;
  17. };
  19. //构造函数
  20. template <typename T> CQueue<T>::CQueue(void)
  21. {
  22. }
  24. //析构函数
  25. template <typename T> CQueue<T>::~CQueue(void)
  26. {
  27. }
  29. //插入元素
  30. template <typename T> void CQueue<T>::appendtail(const T& node)
  31. {
  32.     stack1.push(node);
  33. }
  35. //删除元素并返回
  36. template <typename T> T CQueue<T>::deleteHead()
  37. {
  38.     if(stack2.size()<=0)
  39.     {
  40.         while(stack1.size()>0)
  41.         {
  42.             stack2.push(stack1.top());
  43.             stack1.pop();
  44.         }
  45.     }
  46.     if(stack2.size()==0)
  47.         throw new exception("队列为空");
  48.     T head=stack2.top();
  49.     stack2.pop();
  50.     return head;
  51. }
  53. void main()
  54. {
  55.     CQueue<int> queue;
  56.     queue.appendtail(1);
  57.     queue.appendtail(2);
  58.     queue.appendtail(3);
  59.     queue.appendtail(4);
  60.     int len=4;
  61.     while(len>0)
  62.     {
  63.         cout<<queue.deleteHead()<<endl;
  64.         --len;
  65.     }
  67.     system("pause");
  68. }
2. 使用两个队列实现一个栈

参考代码

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<stack>
  4. #include<queue>
  5. using namespace std;
  7. template <typename T>class CStack
  8. {
  9. public:
  10.     CStack(void){};
  11.     ~CStack(void){};
  12.     void push(const T& node);
  13.     T pop();
  14. private:
  15.     queue<T> queue1;
  16.     queue<T> queue2;
  18. };
  20. //插入元素
  21. template <typename T> void CStack<T>::push(const T& element)
  22. {
  23.     if(queue1.size()>0)//如果queue1不为空则往queue1中插入元素
  24.         queue1.push(element);
  25.     else if(queue2.size()>0)//如果queue2不为空则往queue2中插入元素
  26.         queue2.push(element);
  27.     else//如果两个队列都为空，则往queue1中插入元素
  28.         queue1.push(element);
  30. }
  32. //删除元素
  33. template <typename T> T CStack<T>::pop()
  34. {
  35.     if(queue1.size()==0)//如果queue1为空
  36.     {
  37.         //保证queue2中有一个元素，将其余元素保存到queue1中
  38.         while(queue2.size()>1)
  39.         {
  40.             queue1.push(queue2.front());
  41.             queue2.pop();
  42.         }
  43.         T& data=queue2.front();
  44.         queue2.pop();
  45.         return data;
  46.     }
  47.     else//如果queue2为空
  48.     {
  49.         //保证queue2中有一个元素，将其余元素保存到queue1中
  50.         while(queue1.size()>1)
  51.         {
  52.             queue2.push(queue1.front());
  53.             queue1.pop();
  54.         }
  55.         T& data=queue1.front();
  56.         queue1.pop();
  57.         return data;
  58.     }
  60. }
  62. void main()
  63. {
  64.     CStack<int> stack;
  65.     stack.push(1);
  66.     stack.push(2);
  67.     stack.push(3);
  68.     stack.push(4);
  70.     int len=4;
  71.     while(len>0)
  72.     {
  73.         cout<<stack.pop()<<" ";
  74.         --len;
  75.     }
  77.     system("pause");
  78. }
3. 利用一个栈倒序另外一个栈中的数

参考代码

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<stack>
  4. using namespace std;
  6. template <typename T> void ReverseOrder(stack<T> &s1,stack<T> &s2)
  7. {
  8.     s1.push(5);
  9.     s1.push(4);
  10.     s1.push(3);
  11.     s1.push(2);
  12.     s1.push(1);
  14.     int sortNum=0;
  15.     int oriStackSize=s1.size();
  16.     while(sortNum<oriStackSize)
  17.     {
  18.         int temp=s1.top();
  19.         s1.pop();
  20.         while(s1.size()-sortNum>0)
  21.         {
  22.             s2.push(s1.top());
  23.             s1.pop();
  24.         }
  25.         //首元素存入s1
  26.         s1.push(temp);
  27.         ++sortNum;
  29.         while(!s2.empty())
  30.         {
  31.             s1.push(s2.top());
  32.             s2.pop();
  33.         }
  34.     }
  36.     cout<<"逆序栈输出："<<endl;
  37.     while(!s1.empty())
  38.     {
  39.         cout<<s1.top()<<endl;
  40.         s1.pop();
  41.     }
  43. }
  45. void main()
  46. {
  47.     stack<int> s1;
  48.     stack<int> s2;
  50.     ReverseOrder(s1,s2);
  52.     system("pause");
  53. }
4. 铁轨

某城市有一个火车站，铁轨铺设如图所示。有n节车厢从A方向驶入车站，按进站顺序编号1～n。现让这些火车按照某种特定的顺序进入B方向的铁轨并驶出车站。 为了重组车厢，可以借助中转站C。C是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，一旦从A移入C，就不能再回到A了；一旦从C移入B，就不能回到C了。换句话说，在任意时刻，只有两种选择：A→C和C→B。请编程判断判断：按给定的出站顺序，火车能否出站。

参考代码

  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4. const int N=100;
  5. int main()
  6. {
  7.     int n,i;
  8.     stack<char > stack;
  9.     cin>>n;
  10.     int num[N];
  11.     for(i=1;i<=n;i++)
  12.         cin>>num[i]; 
  13.     int A=1,B=1,ok=1;
  14.     while(B<=n)
  15.     {
  16.         if(A==num[B])
  17.         {
  18.             A++;
  19.             B++;
  20.         }
  21.         else if(!stack.empty() && stack.top()==num[B])
  22.         {
  23.             stack.pop();
  24.             B++;
  25.         }else if(A<=n)   
  26.         {
  27.             stack.push(A);
  28.             A++;
  29.         }else
  30.         {
  31.             ok=0;
  32.             break;
  33.         }
  34.     }
  35.     if(ok==1) cout<<"Yes"<<endl;
  36.     else cout<<"No"<<endl;
  37.     return 0;
  38. }
5. 进制转换

参考代码

  1. void conversion(int N,int d)
  2. {
  3.     stack<int > stack;
  4.     while(N)
  5.     {
  6.         stack.push(N%d);
  7.         N=N/d;
  8.     }
  9.     while(!stack.empty())
  10.     {
  11.         cout<<stack.top()<<" ";
  12.         stack.pop();
  13.     }
  14. }
6. 括号匹配 （栈）

参考代码

  1. #include <iostream>
  2. #include <string>
  3. #include <stack>
  4. using namespace std;
  5. bool judge_bracket(string str)
  6. {
  7.     int i;
  8.     char ch;
  9.     stack<char > stack;
  10.     for(i=0;i<str.length();i++)
  11.     {
  12.         switch(ch=str[i])
  13.         {
  14.         case '(':   stack.push(ch);
  15.                     break;
  16.         case ')':   if(stack.top()=='(')   
  17.                     stack.pop();
  18.                     else
  19.                     return false;
  20.                     break;
  21.         case '[':   stack.push(ch);
  22.                     break;
  23.         case ']':   if(stack.top()=='[')   
  24.                     stack.pop();
  25.                     else
  26.                     return false;
  27.                     break;     
  28.         case '{':   stack.push(ch);
  29.                     break;
  30.         case '}':   if(stack.top()=='{')   
  31.                     stack.pop();
  32.                     else
  33.                     return false;
  34.                     break;
  35.         default :   break;
  36.         }      
  37.     }
  38.     return true;
  39. }
  41. int main()
  42. {
  43.     string  str;
  44.     cin>>str;
  45.     if(judge_bracket(str))  cout<<"匹配成功!"<<endl;
  46.     else cout<<"匹配不成功!"<<endl;
  47.     return 0;
  48. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注