首页 > 代码库 > 判断一个字符串是否为回文-链队(新建,进队,出队),链栈(新建,进栈,出栈)

判断一个字符串是否为回文-链队(新建,进队,出队),链栈(新建,进栈,出栈)

回文:字符对称排列的字符串,例如ABCBA

思路:根据队:先进先出和栈: 先进后出的原则,进行比较出队和出栈的字符是否相等。如果相等,则为回文。

创建控制台应用程序。

  1         #region 字符节点类 
  2         class CharNode
  3         {
  4             public char Char    //字符
  5             {
  6                 get;
  7                 set;
  8             }
  9             public CharNode Next   //下一节点
 10             {
 11                 get;
 12                 set;
 13             }
 14             public CharNode(char Char,CharNode next)
 15             {
 16                 this.Char = Char;
 17                 this.Next = next;
 18             }
 19         }
 20 
 21         #endregion
 22 
 23         #region 链队类 
 24         /// <summary>
 25         /// 链队
 26         /// </summary>
 27         class CharQueue
 28         {
 29             CharNode front;  //队头
 30             CharNode rear;   //队尾
 31             /// <summary>
 32             /// 进队 
 33             /// </summary>
 34             /// <param name="Char">节点字符</param>
 35             public void In(char Char)
 36             {
 37                 if(rear==null)
 38                 {
 39                     rear= new CharNode(Char, null);      //创建队头节点
 40                     front = rear;
 41                 }
 42                 else
 43                 {
 44                     rear.Next = new CharNode(Char, null);     //创建队尾
 45                     rear = rear.Next;
 46                 }
 47             }
 48 
 49             /// <summary>
 50             /// 出队
 51             /// </summary>
 52             /// <returns></returns>
 53             public char? Out()
 54             {
 55                 if(front==null)
 56                 {
 57                     return null;
 58                 }
 59 
 60                 char Char = front.Char;
 61                 front = front.Next;
 62                 if (front == null)
 63                     rear = null;
 64 
 65                 return Char;
 66 
 67             }
 68 
 69         }
 70         #endregion
 71 
 72         #region 链栈类
 73         public class CharStack
 74         {
 75             CharNode top;
 76             /// <summary>
 77             /// 进栈
 78             /// </summary>
 79             /// <param name="Char">节点字符</param>
 80             public void Push(char Char)
 81             {
 82               
 83                 if(top==null)
 84                 {
 85                     top = new CharNode(Char, null);
 86                 }
 87                 else
 88                 {
 89                     top = new CharNode(Char, top);
 90                 }
 91             }
 92             /// <summary>
 93             /// 出栈
 94             /// </summary>
 95             /// <returns></returns>
 96             public char? Pop()   //?代表可以返回null
 97             {
 98                 if (this.top == null)
 99                     return null;
100                 else
101                 {
102                     char Char = top.Char;
103                     top = top.Next;
104                     return Char;
105                 }
106             }
107         }         
108 
109         #endregion
110         static void Main(string[] args)
111         {
112             Console.WriteLine("pls input one string:");
113             string str = Console.ReadLine();
114             CharStack stack = new CharStack();   //实例化栈
115             CharQueue queue = new CharQueue();   //实例化队 
116 
117             char? charStack, charQueue;
118 
119             foreach(char Char in str)   
120             {
121                 queue.In(Char);     //进队
122                 stack.Push(Char);   //进栈
123             }
124 
125             do
126             {
127                 charQueue = queue.Out();  //出队
128                 charStack = stack.Pop();   //出栈
129 
130                 if (charQueue != charStack)
131                     break;
132             }
133             while (charQueue != null && charStack != null);
134 
135             if(charQueue!=null||charStack!=null)
136             {
137                 Console.WriteLine("{0} is not 回文",str);
138             }
139             else
140             {
141                 Console.WriteLine("{0} is 回文 ",str);
142             }
143 
144             Console.ReadLine();
145             
146         }
View Code