链接列表堆栈弹出方法

Question

我想创建一个链接列表堆栈与流行和推送功能。 Push方法正在工作，但Pop不是。我无法弄清楚它的价值在哪里返回，我认为它应该在解决这个问题时起作用（对于可怜的措词抱歉）。

这里是我的代码：

class Program 
{ 

    int nextFree; 
    int End; 
    int Start; 
    Names[] Stack; 
    Names greg = new Names(); 
    Names matt = new Names(); 
    Names jack = new Names(); 
    Names fred = new Names(); 

    public struct Names 
    { 
     public Int32 pointer; 
     public string data; 
    } 

    static void Main(string[] args) 
    { 

     Program prog = new Program(); 
     do 
     { 
      prog.DisplayMenu(); 
     } 
     while (true); 
    } 

    public void DisplayMenu() 
    { 
     Int32 userInput = 0; 

     Console.WriteLine("Linear Stack"); 
     Console.WriteLine("1: Add to stack"); 
     Console.WriteLine("2: Delete from stack"); 
     userInput = Int32.Parse(Console.ReadLine()); 


     switch (userInput) 
     { 
      case 1: 
       this.Push(); 
       break; 
      case 2: 
       this.Pop(); 
       break; 
     } 

    } 

    public Program() 
    { 
     Stack = new Names[6]; 

     greg.data = "Greg"; 
     greg.pointer = 1; 

     matt.data = "Matt"; 
     matt.pointer = 2; 

     jack.data = "Jack"; 
     jack.pointer = 3; 

     fred.data = "Fred"; 
     fred.pointer = -1; 

     Stack[0] = greg; 
     Stack[1] = matt; 
     Stack[2] = jack; 
     Stack[3] = fred; 
     nextFree = 4; 
     End = 5; 
     Start = 0; 
    } 


    public string Pop() 
    { 

     string value = string.Empty; 

     if (nextFree == -1) 
     { 
      Console.WriteLine("Stack is empty"); 
      Console.ReadLine(); 
     } 
     else 
     { 
      Names thisNode = Stack[End]; 
      int temp = End; 
      End = thisNode.pointer; 
      thisNode.pointer = nextFree; 
      nextFree = temp; 
     } 
     this.ListAllNames(); 
     return value; 
    } 

    public void Push() 
    { 
     if (nextFree >= Stack.Length) 
     { 
      Console.WriteLine("Stackoverflow, to many elements for the stack"); 
      Console.ReadLine(); 
     } 
     else 
     { 
      Console.WriteLine("Enter a name to be added"); 
      string input = Console.ReadLine(); 
      Stack[nextFree].data = input; 
      Stack[nextFree].pointer = End; 
      End = nextFree; 
      nextFree++;  
     } 
      this.ListAllNames(); 
    } 


    public void ListAllNames() 
    { 
     foreach (Names name in Stack) 
     { 
      Console.WriteLine("Name:" + name.data); 
     } 
    } 



} 
} 

Answer 1

我强烈建议你阅读Eric Lippert's Immutable Stack文章。它会给你一些关于实现的非常有趣的提示。

下面的代码从它：

public interface IStack<T> : IEnumerable<T> 
{ 
    IStack<T> Push(T value); 
    IStack<T> Pop(); 
    T Peek(); 
    bool IsEmpty { get; } 
} 

public sealed class Stack<T> : IStack<T> 
{ 
    private sealed class EmptyStack : IStack<T> 
    { 
     public bool IsEmpty { get { return true; } } 
     public T Peek() { throw new Exception("Empty stack"); } 
     public IStack<T> Push(T value) { return new Stack<T>(value, this); } 
     public IStack<T> Pop() { throw new Exception("Empty stack"); } 
     public IEnumerator<T> GetEnumerator() { yield break; } 
     IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } 
    } 
    private static readonly EmptyStack empty = new EmptyStack(); 
    public static IStack<T> Empty { get { return empty; } } 
    private readonly T head; 
    private readonly IStack<T> tail; 
    private Stack(T head, IStack<T> tail) 
    { 
     this.head = head; 
     this.tail = tail; 
    } 
    public bool IsEmpty { get { return false; } } 
    public T Peek() { return head; } 
    public IStack<T> Pop() { return tail; } 
    public IStack<T> Push(T value) { return new Stack<T>(value, this); } 
    public IEnumerator<T> GetEnumerator() 
    { 
     for(IStack<T> stack = this; !stack.IsEmpty ; stack = stack.Pop()) 
      yield return stack.Peek(); 
    } 
    IEnumerator IEnumerable.GetEnumerator() {return this.GetEnumerator();} 
} 

Answer 2

你不是很面向对象的。由于尼古拉斯·沃斯指出：

对象=数据+算法

您需要封装的东西，像这样：

public class LinkedListStack<T> 
{ 
    /// <summary> 
    /// indicates whether or not the stack contains data 
    /// </summary> 
    public bool HasData { get { return this.Top != null ; } } 

    /// <summary> 
    /// The topmost stack frame 
    /// </summary> 
    private Node Top { get ; set; } 

    /// <summary> 
    /// constructor 
    /// </summary> 
    public LinkedListStack() 
    { 
    this.Top = null ; 
    return ; 
    } 

    /// <summary> 
    /// constructor: initializes the stack with the provied contents. 
    /// </summary> 
    /// <param name="data"></param> 
    public LinkedListStack(IEnumerable<T> data) : this() 
    { 
    if (data == null) throw new ArgumentNullException("data") ; 
    foreach (T datum in data) 
    { 
     Push(datum) ; 
    } 
    } 

    /// <summary> 
    /// remove the top item from the stack and return it 
    /// </summary> 
    /// <returns></returns> 
    public T Pop() 
    { 
    if (this.Top == null) throw new InvalidOperationException("Can't pop an empty stack!"); 
    Node top = this.Top ; 
    this.Top = top.Next ; 
    return top.Payload ; 
    } 

    /// <summary> 
    /// push an item onto the stack 
    /// </summary> 
    /// <param name="datum"></param> 
    public void Push(T datum) 
    { 
    this.Top = new Node(datum , this.Top) ; 
    return ; 
    } 

    /// <summary> 
    /// private helper class (our stack frame) 
    /// </summary> 
    private class Node 
    { 
    public Node Next ; 
    public T Payload ; 
    public Node(T payload) : this(payload,null) 
    { 
     return ; 
    } 
    public Node(T payload , Node next) 
    { 
     this.Next = next ; 
     this.Payload = payload ; 
     return ; 
    } 
    } 

}