栈和队列

栈和队列的问题

栈

1. 固定长度数组实现栈
   • 代码

     type IFixStack interface {
         Push(value int)
         Pop() int
         Top() int
         Size() int
         Count() int
     }
     
     type FixStack struct {
         values []int
         size int
         count int
     }
     
     func New(count int) *FixStack {
         return &FixStack{values:make([]int, count), size:0, count:count}
     }
     
     func (stack *FixStack) Push(value int) {
         stack.values[stack.size] = value
         stack.size++
     }
     
     func (stack *FixStack) Pop() int {
         stack.size--
         return stack.values[stack.size]
     }
     
     func (stack *FixStack) Top() int {
         return stack.values[stack.size - 1]
     }
     
     func (stack *FixStack) Size() int {
         return stack.size
     }
     
     func (stack *FixStack) Count() int {
         return stack.count
     }

2. 使用队列来实现栈
   • 代码

     (偷个懒, 毕竟C++有现成的队列和栈, 直接拿来用了)

     #include <queue>
     class Stack 
     {
     public:
         Stack();
         void push(int x);
         int pop();
         int top();
         bool empty();
         ~Stack();
     private:
         std::queue<int>* pushQueue;
         std::queue<int>* popQueue;
     };
     
     Stack::Stack()
     {
         this->pushQueue = new std::queue<int>();
         this->popQueue = new std::queue<int>();
     }
     
     void Stack::push(int x)
     {
         this->pushQueue->push(x);
     }
     
     int Stack::pop()
     {
         while (this->pushQueue->size() != 1)
         {
             this->popQueue->push(this->pushQueue->front());
             this->pushQueue->pop();
         }
         int res = this->pushQueue->front();
         this->pushQueue->pop();
         std::queue<int>* tmp = this->popQueue;
         this->popQueue = this->pushQueue;
         this->pushQueue = tmp;
         return res;
     }
     
     int Stack::top()
     {
         while (this->pushQueue->size() != 1)
         {
             this->popQueue->push(this->pushQueue->front());
             this->pushQueue->pop();
         }
         int res = this->pushQueue->front();
         this->popQueue->push(this->pushQueue->front());
         this->pushQueue->pop();
         std::queue<int>* tmp = this->popQueue;
         this->popQueue = this->pushQueue;
         this->pushQueue = tmp;
         return res;
     }
     
     bool Stack::empty()
     {
         return this->popQueue->size() + this->pushQueue->size() == 0;
     }
     
     Stack::~Stack()
     {
         delete this->pushQueue;
         delete this->popQueue;
     }

队列

1. 固定长度的数组实现队列
   • 代码

     type IFixQueue interface {
         Push(value int)
         Pop() int
         Front() int
         Size() int
         Count() int
     }
     
     type FixQueue struct {
         values []int
         count int
         size int
         begin int
         end int
     }
     
     func New(count int) *FixQueue {
         return &FixQueue{values: make([]int, count), size: 0, begin:0, end:0, count:count}
     }
     
     func (queue *FixQueue) Push(value int) {
         if queue.size < queue.count {
             queue.size++
             queue.values[queue.end] = value
             queue.end = (queue.end + 1) % queue.count
         } else {
             queue.values[queue.count] = value
         }
     }
     
     func (queue *FixQueue) Pop() int {
         if queue.size > 0 {
             res := queue.values[queue.begin]
             queue.begin = (queue.begin + 1) % queue.count
             queue.size--
             return res
         } else {
             return queue.values[queue.count]
         }
     }
     
     func (queue *FixQueue) Front() int {
         if queue.size > 0 {
             return queue.values[queue.begin]
         } else {
             return queue.values[queue.count]
         }
     }
     
     func (queue *FixQueue) Size() int {
         return queue.size
     }
     
     func (queue *FixQueue) Count() int {
         return queue.count
     }

2. 使用栈来实现队列
   • 代码

     (偷个懒, 毕竟C++有现成的队列和栈, 直接拿来用了)

     #include <stack>
     class Queue
     {
     public:
         Queue();
         void push(int x);
         int pop();
         int peek();
         bool empty();
         ~Queue();
     private:
         std::stack<int>* pushStack;
         std::stack<int>* popStack;
     };
     
     Queue::Queue()
     {
         this->pushStack = new std::stack<int>();
         this->popStack = new std::stack<int>();
     }
     
     void Queue::push(int x)
     {
         this->pushStack->push(x);
     }
     
     int Queue::pop()
     {
         if (this->popStack->size() == 0)
         {
             while (this->pushStack->size() != 0)
             {
                 this->popStack->push(this->pushStack->top());
                 this->pushStack->pop();
             }
         }
         int res = this->popStack->top();
         this->popStack->pop();
         return res;
     }
     
     int Queue::peek()
     {
         if (this->popStack->size() == 0)
         {
             while (this->pushStack->size() != 0)
             {
                 this->popStack->push(this->pushStack->top());
                 this->pushStack->pop();
             }
         }
         return this->popStack->top();
     }
     
     bool Queue::empty()
     {
         return this->popStack->size() + this->pushStack->size() == 0;
     }
     
     Queue::~Queue()
     {
         delete this->popStack;
         delete this->pushStack;
     }