队列和栈专题

写篇文章，总结一下栈和队列

栈

栈是一种特殊的线性表，遵循先进后出的原则，只可以对栈顶元素进行操作。
主要包括压栈，出栈，查看栈顶元素三种操作。

C语言数组实现顺序栈

//数组实现顺序栈
typedef struct zhan {
	char data[100];
	int top;
}zhan;
void initzhan(zhan *a)
{
	a->top = -1;
}
void push(zhan* a, char b) {
	a->data[++a->top] = b;
}
char pop(zhan* a) {
	return a->data[a->top--];
}
char gettop(zhan* a) {
	return a->data[a->top];
}

C语言指针实现顺序栈

//指针实现顺序栈
typedef struct stack {
	int* top;
	int* base;
}stack;
void initstack(stack* a) {
	a->base = (int*)malloc(sizeof(int)*100);//最大空间为100
	a->top = a->base;
}
void pushstack(stack* a, int b)
{
	*a->top = b;
	a->top++;
}
int popstack(stack* a) {
	a->top--;
	return *a->top;
}

C语言实现链栈

//链栈的实现
typedef struct stack {
	int data;
	struct stack *next;
}stack;
void initstack(stack*a) {
	//stack* p;
	//a = p = (stack*)malloc(sizeof(stack));
	//a->next = NULL;
}
void pushstack(stack* a,int b) {
	stack* p;
	p = (stack*)malloc(sizeof(stack));
	p->data = b;
	p->next = a->next;
	a->next = p;
}
int popstack(stack * a)
{
	stack* p;
	int b;
	p = a->next;
	b= p->data;
	a->next = p->next;
	free(p);
	return b;
}

C++的栈

#include<stack>
初始化
出栈
压栈
取栈顶元素

队列

C++的队列

队列实现栈

来自leetcode的一道题目。
挺有启发性的，如何用两个队列实现一个栈。

class MyStack {
public:
    /** Initialize your data structure here. */
    queue<int> queue1;
    queue<int> queue2;
    MyStack() {
     
    }
    
    /** Push element x onto stack. */
    void push(int x) {
       //queue2做辅助队列，用来翻转queue1,同理，一个队列也可以实现 
      while(!queue1.empty()){
        int a=queue1.front();
        queue1.pop();
        queue2.push(a);
      }
      queue1.push(x);
      while(!queue2.empty()){
        int a=queue2.front();
        queue2.pop();
        queue1.push(a);
      }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
     int a= queue1.front();
     queue1.pop();
     return a;
    }
    
    /** Get the top element. */
    int top() {
     return queue1.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
   return queue1.empty();
    }
};

栈实现队列

来自leetcode的另一个题目，用两个栈实现一个队列。

class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> a;
    stack<int> b;
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
     while(!a.empty()){
         int c=a.top();
         a.pop();
         b.push(c);
     }
     a.push(x);
     while(!b.empty()){
         int c=b.top();
         b.pop();
         a.push(c);
     }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int c=a.top();
        a.pop();
          return c ;
    }
    
    /** Get the front element. */
    int peek() {
        
         return a.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
      return a.empty();
    }
};