Implement Stack Using LinkedList

用一个循环链表。每次pop掉linkedlist的tail之前都进行一遍遍历寻找tail之前的结点。

#include <string>
#include <list>
#include <iostream>
using namespace std;

class ll_stack{
  struct listNode{
    int val;
    listNode* next;
    listNode(int x): val(x), next(NULL) {}
  };
public:
  listNode *tail;
  ll_stack() {
    tail = NULL;
  };
  void push(int x) {
    cout << "pushing in " << x << endl;
    listNode* node = new listNode(x);
    if ( tail == NULL ) {
      tail = node;
      node->next = node;
      return;
    }
    listNode* next = tail->next;
    tail->next = node;
    node->next = next;
    tail = node;
    return;
  }
  bool empty() { return ( tail == NULL ); }
  int top() { return tail->val; }
  void pop() {
    cout << "poping out " << endl;
    if ( tail == NULL ) return;
    listNode* target = tail, *p = tail;
    if ( p->next == target ) {
      delete target;
      tail = NULL;
      return;
    }
    while ( p->next != target ) p = p->next;
    listNode *next = tail->next;
    p->next = next;
    tail = p;
    delete target;
    return;
  }
};
int main()
{
  ll_stack *s = new ll_stack();
  s->push(1);
  s->push(2);
  s->push(3);
  while ( ! s->empty() ) {
    cout << s->top() << endl;
    s->pop();
  }
  return 0;
}