[C++知识库]栈与队列OJ题

1、栈与队列的实现

//队列
ListNode*BuyListNode(LTDataType x)
{
	ListNode *node = (ListNode*)malloc(sizeof(ListNode));
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

ListNode*ListCreate()
{
	ListNode*head = (ListNode*)malloc(sizeof(ListNode));
	head->next = head;
	head->prev = head;
	return head;
}

void ListPrint(ListNode * pHead)
{
	assert(pHead);
	ListNode*cur = pHead->next;
	while (cur != pHead)
	{
		print("%d->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void ListDestroy(ListNode*pHead)
{
	ListNode * cur = pHead -> next;
	while (cur != pHead)
	{
		ListNode*next = cur->next;
		free(cur);
		cur = next;
	}
	free(pHead);
}

void ListPushBack(ListNode*pHead, LTDataType x)
{
	assert(pHead);
	ListInsert(pHead, x);
}

void ListPushFront(ListNode*pHead, LTDataType x)
{
	assert(pHead);
	ListInsert(pHead->next, x);
}
void ListPopBack(ListNode *pHead)
{
	assert(pHead);
	ListErase(pHead->prev);
}
void ListPopFront(ListNode *pHead)
{
	ListErase(pHead->next);
}
void ListInsert(ListNode*pos, LTDataType x)
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	pos->prev = newnode;
}
void ListErae(ListNode*pos)
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}
//栈
void CheckCapacity(Stack*ps)
{
	if (ps->size >= ps->capacity)
	{
		ps->capacity *= 2;
		ps->array = (STDataType*)realloc(ps->arry, ps->capacity*sizeof(STDataType));
	}
}

void StackInit(Stack*ps)
{
	ps->array = (STDataType*)calloc(DEFTACKSIZE, sizeof(STDataType));
	ps->capacity = DEFSTACKSIZE;
	ps->size = 0;
}

void StackPushStack*ps,STDataType x)
{
	CheckCapacity(ps);
	ps->array[ps->size] = x;
	ps->size++;
}
void StackPop(Stack*ps)
{
	if (ps->size == 0)
	{
		return;
	}
	ps->size--;
}
STDataType StackTop(Stack*ps)
{
	if (ps->size == 0)
	{
		return(STDataType)0;
	}
	return ps->array[ps->size - 1];
}
int StackEmpty(Stack*ps)
{
	return ps->size == 0;
}
int StackDestory(Stack*ps)
{
	if (ps->array)
	{
		free(ps->array);
		ps->array = NULL;
		ps->size = 0;
		ps->capacity = 0;
	}
}

QueueNode*BuyQueueNode(QuDataType x)
{
	QueueNode*cur = (QueueNode*)malloc(sizeof(QueueNode));
	cur->_data = x;
	cur->_next = NULL;
	return cur;
}
void QueueInit(Queue *q)
{
	q->_front = NULL;
	q->_rear = NULL;
}
void QueuePush(Queue*q, QuDataType x)
{
	QueueNode*cur = BuyQueueNode(x);
	if (q->_front == NULL)
	{
		q->_front = q->_rear = cur;
	}
	else
	{
		q->_rear->_next = cur;
		q->_rear = cur;
	}
}
void QueuePop(Queue*q)
{
	if (q->_front == NULL)
	{
		return;
	}
	QueueNode*tmp = q->_front->_next;
	free(q->_front);
	q->_front = tmp;
}
QuDataType QueueFront(Queue*q)
{
	return q->_front->_data;
}
QuDataType QueueBack(Queue*q)
{
	return q->_rear->_data;
}
int QueueEmpty(Queue *q)
{
	return q->_front = NULL;
}

int QueueSize(Queue*q)
{
	QListNode*cur;
	int count = 0;
	for (cur = q->_front; cur; cur = cur->next)
	{
		count++;
	}
	return count;
}

void QueueDestory(Queue*q)
{
	if (q->_front == NULL)
	{
		return;
	}
	while (q->_front)
	{
		QueuePop(q);
	}
}

栈与队列搭建基础框架如上，在实现基础的搭建之后便可以利用结构的特点按照需求完成别的程序设计。
2、给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
c语言

char pairs(char a)
{
	if (a == '}')return'{';
	if (a == ']')return'[';
	if (a == ')')return'(';
	return 0;
}
bool isValid(char *s)
{
	int n = strlen(s);
	if (n % 2 == 1)
	{
		return false;
	}
	int stk[n + 1], top = 0;
	for (int i = 0; i < n; i++)
	{
		char ch = pairs(s[i]);
		if (ch)
		{
			if (top == 0 || stk[top - 1] != ch)
			{
				return false;
			}
			top--;
		}
		else
		{
			stk[top++] = s[i];
		}
	}
	return top == 0;
}```
c++
```cpp
class Solution
{
public:
	bool isValid(string s)
	{
		int n = s.size();
		if (n % 2 == 1)
		{
			return false;
		}
		unordered_map<char, char>pairs =
		{
			{ ')', '(' },
			{ ']', '[' },
			{ '}', '{' },
		};
		Stack<char>str;
		for (char ch : s)
		{
			if (pairs.count(ch))
			{
				if (stk.empty() || stk.top() != pairs[ch])
				{
					return false;
				}
				stk.pop();
			}
			else
			{
				stk.puch(ch);
			}
		}
		return stk.empty();
	}
};

根据栈的特性，在对栈的遍历过程中，在遇到右括号之后取栈顶的左括号，闭合，若不是相同类型，或则栈中没有左括号则字符串无效，返回时false。
3、用队列实现栈
c语言：

#define LEN 20
typedef struct queue
{
	int *data;
	int head;
	int rear;
	int size;
}Queue;
typedef struct
{
	Queue *queue1, *queue2;
}MyStack;

Queue *initQueue(int k)
{
	Queue*obj = (Queue*)malloc(size(Queue));
	obj->data = (int *)malloc(k*sizeof(int));
	obj->head = -1;
	obj->rear = -1;
	obj->size = k;
	return obj;
}

void enQueue(Queue *obj, int e)
{
	if (obj->head == -1)
	{
		obj->head = 0;
	}
	obj->rear = (obj->rear + 1) % obj->size;
	obj->data[obj->rear] = e;
}

int deQueue(Queue *obj)
{
	int a = obj->data[obj->head];
	if (obj->head == obj->rear)
	{
		obj->rear = -1;
		obj->head = -1;
		return a;
	}
	obj->head = (obj->head + 1) % obj->size;
	return a;
}
int isEmpty(Queue *obj)
{
	return obj->head == -1;
}
MyStack *myStackCreate()
{
	MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
	obj->queue1 = initQueue(LEN);
	obj->queue2 = initQueue(LEN);
	return obj;
}
void myStackPush(MyStack *obj, int x)
{
	if (isEmpty(obj->queue1))
	{
		enQueue(obj->queue2, x);
		eles
		{
			enQueue(obj->queue, x);
		}
	}
}
int myStackPop(MyStack*obj)
{
	if (isEmpty(obj->queue1))
	{
		while (obj->queue2->head != obj->queue1->rear)
		{
			enQueue(obj->queue1, dequeue(obj->queue1));
		}
		return deQueue(obj->queue2);
	}
	while (obj->queue1->head != obj->queue1->rear)
	{
		enQueue(obj->queue2, deQueue(obj->queue1));
	}
	return deQueue(obj->queue1);
}

int myStackTop(MyStack *obj)
{
	if (isEmpty(obj->queue1))
	{
		return obj->queue2->data[obj->queue2->rear];
	}
	return obj->queue1->data[obj->queue1->rear];
}

bool myStackEmpty(MyStack *obj)
{
	if (obj->queue1->head == -1 && obj->queue2->head == -1)
	{
		return ture;
	}
	return false;
}

void myStackFree(MyStack *obj)
{
	free(obj->queue1->data);
	obj->queue1->data = NULL;
	free(obj->queue1);
	obj->queue1()NULL;
	free(obj->queue2->data);
	obj->queue2->data = NULL;
	free(obj->queue2)=NULL;
	free(obj);
	obj = NULL;
}

c++:

class MyStack
{
public:
	queue<int> queue1;
	queue<int> queue2;
	MyStack()
	{
	}
	void puch(int x)
	{
		queue2.push(x);
	while (!= queue1.empty())
	{
		queue2.push(queue1.front());//元素X入栈
		queue1.pop();
	}
	swap(queue1, queue2);
}
int pop()//移除栈顶元素
{
	int r = queue1.front();
	queue1.pop();
	return r;
}
int top()//获取栈顶元素
{
	int r = queue1.front();
	return r;
}
bool empty()//查看返回栈是否为空
{
	return queue1.empty();
}
};

把握栈和队列的特点，栈是一种先进后出的数据结构，元素从顶端入栈，然后从顶端出栈，队列是一种先进后出的数据，元素从后端入队，然后从前端出队。
4、用栈实现队列
c++

class MyQueue
{
private:
	stack<int>inStack, outStack;
	void in2out()
	{
		while (!isStack.empty())
		{
			outStack.push(isStack.top());
			inStack.pop();
		}
	}
public:
	MyQueue(){}
	void push(int x)
	{
		inStack.push(x);
	}
	int pop()
	{
		if (outStack.empty())
		{
			in2outout();
		}
		int x = outStack.pop();
		return x;
	}
	int peek()
	{
		if (outStack.empty())
		{
			in2out();
		}
		return outStack.top();
	}
	bool empty()
	{
		return inStack.empty() && outStack.empty();
	}
}

将一个栈当作输入栈，用于压入push传入的数据，另一个栈当作输入栈，用于pop和peek操作，当输出栈为空之后将输入栈全部数据依次弹出压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往对尾的顺序。